全国高等学校パソコンコンクール
プログラミング部門

予選大会問題平成 17 年 9 月 3 日(土)午前 10 時～正午（時間厳守）

全国高等学校パソコンコンクール実行委員会

解答にあたっての注意点

１ 解答方法・ チームで使用できるパソコンは１台限りです。
・ ノート、教科書及び参考書等の紙にかかれたものの持ち込みや閲覧は可能です。
・ 制限時間２時間の間に、フロッピーディスクへの保存及びラベルの貼付まで行ってください。

２ 作成するプログラム
・ 解答する順番は指定しませんので、どの問題から解いてもかまいません。また、全問正解できなくてもかまいません。
・ コンソールアプリケーションを作成してください。ボタンやフォームを使ったビジュアルア
プリケーションではありません。
・ 作成したプログラムはフロッピーディスクに保存して提出します。作成するプログラムのファイル名は半角英字 A＋2 桁の問題番号＋拡張子となります。ソースファイルと実行ファイ
ルをフロッピーディスクに保存してください。
例えば、問題 10 をＣ言語で解答した場合、A10.c と A10.exe をフロッピーディスクに保存します。
・ １つの問題に対する解答プログラムは１つとしてください。複数の解答があった場合は得点となりませんのでご注意ください。たとえば、問題 01 の解答プログラムをＣ言語と BASICの両方で作成しても得点とはなりません。
・ 実数値を出力するプログラムにおいては、特に指定がない限り、切り上げ切り捨て処理は行
わないでください。小数点以下の表示桁数は処理系にまかせてください。

３ データ型・ 特に断りがない限り、問題中にある「整数」、「実数」、「文字」はそれぞれ、コンピュータで自然に扱うことができる整数値、実数値、文字列を言います。

４ 入力
・ 特に断りがない限り、キーボードから入力するプログラムを作成してください。入力フォー
マットは、問題中の入力および入力例を参考にしてください。例えば、入力例に12とあった場合、キーボードの「1」を押して、「Enter」キーを押し、「2」を押して「Enter」
キーを押して入力するという意味です。
・ 特に断りがない限り、不正なデータは入力されませんので、不要なエラー処理を記述する必
要はありません。
・ ファイル名が問題文中に明記されている場合はファイルをオープンして入力するプログラムを作成してください。ファイル名の大文字、小文字は区別し、ファイルはカレントディレク
トリにあるものとします。ファイル名の拡張子が.csv となっているものは、1 行に複数のデータを含み、行のデータが半角のカンマで区切られています。入力フォーマットは問題にある入力および入力例を参考にしてください。たとえば、入力例に
1,2,3
4,5
i

PC 甲子園２００５予選問題

とあった場合、1 行目は三つの数字がカンマ区切りで、2 行目には二つの数字がカンマ区切りで保存されているファイルという意味です。また、ファイルをオープンするタイプの問題では、ファイルは正しく EOF で終了していると仮定してかまいません。
・ 今年度のパソコン甲子園２００５から、入力ファイルはカレントディレクトリに「data+２桁の問題番号+拡張子」というファイル名で保存されているものとして、プログラムではファイル名のみを記述してください。この点が昨年度までとは変更になっていますのでご注意ください。昨年度までは入力ファイルを保存するディレクトリを指定していました。
（c:¥pckosien¥３桁の問題番号+拡張子）

５ 出力
・ プログラムの実行結果を画面に出力するプログラムを作成してください。問題で求められている結果のみを出力し、余計な文字や数字を出力しないようにしてください。
（出力例を参考にしてください。）ただし、プログラミング言語によっては余分な空白が出力されてしまうものがありますので、それについては認めます。入力を促すメッセージプロンプトや「答え=」などというメッセージも必要ありません。たとえば、問題の出力例で123となっている場合、答えのみを一行ずつ改行して出力する、という意味です。
・ 問題毎に記載された出力例は処理系により異なることがありますので注意してください。

６ 不正解となる例
・ ファイル名のつけ方が違う
ファイル名には十分注意してください。ファイル名が異なる場合は採点できなくなりますのでご注意ください。
・ ファイルがそろっていない
競技要領に記載しているファイルが揃っていない場合、採点されませんのでご注意ください。
必ずソースファイルを保存してください。また、十進 BASIC 以外のプログラミング言語で解答を作成した場合、実行ファイルを作成し、保存するのを忘れないでください。
例）A01.c はフロッピーディスクに保存したが、A01.exe を保存しなかった場合。
・ 出力形式が違う
問題の出力例を確認してください。出力形式が異なる場合は採点できなくなりますのでご注意ください。
例１）1 行に 1 つずつ改行して出力するべきところを、カンマで区切って出力した。
例２）1 行に 1 つずつ改行して出力するべきところを、空白で区切って 1 行に出力した。
・ 終了しない
プログラムは必ず終了するように書いてください。
例１）「何かキーを押してください。」というメッセージが出て止まるようなプログラムや、
最後に空行を入力しないと終了しないプログラムは不正解となります。
例２）実行後数分を経過しても答えが出力されないプログラムは暴走しているとみなし、不正解となります。
ii

PC 甲子園２００５予選問題

問題０１

四角すいの表面積（ ６点）

1 辺が x の正方形を底面とする、高さ h の四角すいの表面積 S を出力して終了するプログラムを作成して下さい。ただし、頂点と底面の中心を結ぶ線分は底面と直交しているとします。また、 x 、 h は 100 以下の正の整数とします。

入力
x （整数）h （整数）

出力
S （実数）

入力例１
6
4

出力例１
96.000000

入力例２
7
9

出力例２
184.192459

1

PC 甲子園２００５予選問題

問題０２

ビデオテープの残り時間（ ６点）

標準録画で 120 分のビデオテープがあります。テープを完全に巻き戻した状態でビデオデッキのカウンタを
00:00:00 にし、標準録画モードで録画したところ、あるカウンタ値になりました。このカウンタ値（時、分、秒）を入力し、残りのテープの長さ（録画可能時間）を求め、時：分：秒の形式で出力して終了するプログラムを作成して下さい。
ただし、2 時間（120 分）以内の入力とします。なお、テープ残量は標準録画モードと 3 倍録画モードの場合の２通りを計算し、出力例のように時、分、秒とも 2 桁ずつ出力します。また”05”のように 10 の位が 0 の場合は、”0”を必ずつけてください。

入力
時（整数）
分（整数）
秒（整数）

出力
テープの残りを標準録画した場合の録画可能時間 時:分:秒（半角コロン区切り）
テープの残りを３倍録画した場合の録画可能時間 時:分:秒（半角コロン区切り）

入力例
1
30
0

出力例
00:30:00
01:30:00

2

PC 甲子園２００５予選問題

問題０３

ＢＭＩ（ ６点）

肥満は多くの成人病の原因として挙げられています。過去においては、一部の例外を除けば、高校生には無縁なものでした。しかし、過度の受験勉強等のために運動不足となり、あるいはストレスによる過食症となることが、非現実的なこととはいえなくなっています。高校生にとっても十分関心を持たねばならない問題になるかもしれません。
そこで、あなたは、保健室の先生の助手となって、生徒のデータから肥満の疑いのある生徒を探し出すプログ
ラムを作成することになりました。
方法は BMI(Body Mass Index)という数値を算出する方法です。BMI は次の式で与えられます。
BMI =体重(kg )
(身長(m)) 2

BMI=22 が標準的で、25 以上だと肥満の疑いがあります。ファイルに格納されている、各々の生徒の体重、身長の情報から BMI を算出し、25 以上の生徒の学籍番号を画面に出力して終了するプログラムを作成してください。なお、肥満の疑いのある生徒がいない場合は、”該当なし”と出力して終了するようにしてください。
入力データのファイル名は data03.csv とします。

入力
学籍番号（整数）,体重（実数）,身長（実数）（1 件目のデータ））
学籍番号（整数）,体重（実数）,身長（実数）（2 件目のデータ）

出力
BMI が 25 以上の生徒の学籍番号（複数ある場合、改行してすべて表示）または 該当なし

入力例
1001,50.0,1.60
1002,60.0,1.70
1003,70.0,1.80
1004,80.0,1.70
1005,90.0,1.60

出力例
1004
1005

3

PC 甲子園２００５予選問題

問題０４三角定規で宝探し（ ６点）

１／２

蔵を片付けていたら、先祖の宝のありかへの行き方を記した古文書が見つかりました。この古文書にはおおよ
そ次のような事が書かれていました。
1.まず、町外れの井戸から、真東に 1m の地点に立ち、まっすぐ井戸の方向を向け。
2.右回りに 90 度向きを変え、1m 直進したら、まっすぐ井戸の方向を向け。
3.右回りに 90 度向きを変え、1m 直進したら、まっすぐ井戸の方向を向け。
4.

〃

5.

〃

6.

：

2 行目以降は、全く同じことが書かれていました。あなたは、宝を探そうと思いましたが、厄介なことに気がつきました。昔と違い建物が邪魔をしていて、まっすぐ井戸の方向をむこうにも井戸が見えなかったり 1m 直進しようにも直進できなかったりします。さらに、この古文書ときたら、1000 行近くあり、古文書どおりの作業をすることは、かなりの時間と体力が要ります。しかしながら、幸運なことに、あなたはコンピュータを利用することができます。
古文書に書かれている行数 n を入力して、宝の位置（最後に立った場所）を出力して終了するプログラムを作成してください。ただし、 n は 2 以上 1000 以下の正の整数とします。

入力
古文書の行数 n (整数）

出力
町外れの井戸から東に x (m)，北に y (m)が宝の位置（最後に立った場所）として、x （実数）y （実数）

小数点以下第 2 位まで出力してください。小数点以下第３位は切り上げ、切り捨ていずれでも正解とします。

入力例１
3

出力例１
0.29
1.71

4

PC 甲子園２００５予選問題

問題０４三角定規で宝探し（ ６点）

２／２

入力例２
6

出力例２
-2.31
0.80

参考
n =2, 3, 4, 5, 6 の場合の宝の位置(0.00 0.00)

町はずれの井戸5

PC 甲子園２００５予選問題

問題０５

ランレングス（ ６点）

文字列が連続した場合、ある規則で文字を置き換え文字列を短くすることができます。たとえば、AAAA という文字列の場合、@4A と表現すれば 1 文字分圧縮されます。この規則で圧縮された文字列を入力してもとの文字列に復元して終了するプログラムを作成してください。ただし、復元した文字列に＠文字は出現しないものとします。
原文の文字列は半角の英大文字、英小文字、数字、記号であり 100 文字以内、連続する文字は 9 文字以内
です。

入力
文字列

出力
復元した文字列

入力例１
ab@5C1@8050

出力例１
abCCCCC10000000050

入力例２@99+1=1@90

出力例２999999999+1=1000000000

6PC 甲子園２００５予選問題

問題０６

魔方陣（ ７点）

n × n の正方形のマス目の中に数字の１から n 2 が一つずつ入っていて、縦のどの列のマス目の和も、横のどの列のマス目の和も対角線のマス目の和も等しいものを魔方陣といいます。
一辺のマスの個数が奇数の魔方陣の作り方には以下の方法があります。
１．中央のマス目のちょうど一つ下のマス目に１をいれる。
２．次の数字を右斜め下のマス目にいれる。
ただし、数字をいれようとしたマス目が正方形からはみ出している場合、既に数字が埋まっている場合は以下の方法に従って数字を入れるマス目を探す。
・ 右にはみ出した場合には、同じ行の左はしに、左にはみ出した場合には、同じ行の右はしに、下にはみ出した場合には、同じ列の一番上に数字をいれる。
・ 数字をいれようとしたマス目が埋まっているときには、その埋まっているマス目の左斜め下のマス目にいれる。
３．すべてのマス目が埋まるまで２を繰り返す。
この方法に従って、一辺のマス目の個数 n を入力として、その大きさの魔方陣を出力して終了するプログラムを作成して下さい。ただし、 n は３以上１５以下の奇数とします。マス目に入る各数字は右詰５桁で出力してください。

入力n （正の整数）

出力n × n の魔方陣

入力例
5

出力例
11

24

7

20

3

4

12

25

8

16

17

5

13

21

9

10

18

1

14

22

23

6

19

2

15

7

PC 甲子園２００５予選問題

問題０７

凸多角形の面積（ ７点）

凸 n 角形（すべての頂点の内角が 180 度未満である多角形、要するにへこんでいない多角形のこと）の頂点の座標をファイルから読んで、その面積を画面に出力して終了するプログラムを作成してください。頂点には辺のつながりの順序に従って頂点 1、頂点 2、頂点 3、‥‥頂点 n という名前がついています。
ただし、 n は 3 以上 20 以下とします。また、次の、三角形の 3 辺の長さ a , b , c から面積 S を求める公式を使ってもかまいません。
z=a+b+c, S = z ( z − a)( z − b)( z − c)2

入力データのファイル名は data07.csv とします。

入力
頂点 1 の x 座標, 頂点 1 の y 座標（全て実数）
頂点 2 の x 座標, 頂点 2 の y 座標（全て実数）.
.
.
頂点 n の x 座標, 頂点 n の y 座標（全て実数）

出力
S （実数）

入力例
0.0,0.0
0.0,1.0
1.0,1.0
2.0,0.0
1.0,-1.0

出力例
2.5000008PC 甲子園２００５予選問題

問題０８

３乗根（ ７点）

x 3 = q の解は漸化式 xn +1 = xn −q
xn3 − qを計算していくことで近似的に求めることができます。 x1 に正の数
2
2
3xn

3

x 23 − q

3x1

3x 22

をいれ、 x2 = x1 − x1 −2 q 、 x 3 = x 2 −、… と計算します。

この計算をしながら、｜ x 3 − q ｜の値が、十分小さくなったところで、計算をやめ、最後に計算した xn を
x 3 = q の近似解とします。

この方法に従って、入力された正の整数 q に対し、 q の３乗根の近似値を出力して終了するプログラムを作成
してください。ただし、「十分小さくなった」という判定は｜ x 3 − q ｜＜ 0.00001 q を用いてください。

入力
q （整数）

出力x （実数）

入力例
15

出力例
2.4662129PC 甲子園２００５予選問題

問題０９

平面上の対称の位置（ ７点）

平面上の異なる 3 点 P1 ( x1 , y1 ), P2 ( x 2 , y 2 ), Q( x q , y q ) の座標の組をファイルから読み込んで、それぞれの組について、点 P1 点 P2 を通る直線を対称軸として点 Q と線対称の位置にある点 R ( x, y ) を出力して終了するプログ
ラムを作成してください。なお、点 Q は、その対称軸上にないものとします。
入力データのファイル名は data09.csv とします。
P2 ( x 2 , y 2 )Q( x q , y q )R (x, y )P1 ( x1 , y1 )入力
x1 , y1 , x 2 , y 2 , xq , y q (1 件目のデータ：全て実数）：（2 件目のデータ：全て実数）

出力xy （1 件目のデータに対する出力：全て実数空白区切り）:（2 件目のデータに対する出力：全て実数空白区切り）

入力例
1.0,0.0,-1.0,0.0,1.0,1.0
1.0,0.0,0.0,-1.0,3.0,0.0
0.0,1.0,0.0,-1.0,1.0,1.0

出力例
1.000000 -1.000000
1.000000 2.000000-1.000000 1.000000

10PC 甲子園２００５予選問題

問題１０

メリーゴーランド（ ７点）
遊園地にあるメリーゴーランドはご存じでしょう。大きな円盤の上に馬や馬車などの乗り物が固定されていて、円盤が回転すると同時に乗り物が上下に揺れる、
定番の遊具です。ある遊園地のメリーゴーランドは、４人乗りの馬車が２台、２人乗りの車２台、１人乗りの馬が４台、計８台の乗り物が図１のような順序で備えられています。そして、遊園地においでのお客様は、図１に示す乗り場０～７のどこかで待つようになっています。

この遊園地のメリーゴーランドは、かならず乗り物が乗り場にぴったりと合う位置に停止します。そして、０～７のそれぞれで待っているお客さ
まは、目の前にとまった乗り物に乗ることになっています。急いで他の乗り場へ移動してそこから乗るということはできません。効率よく、お客さまにたのしんでいただくためには、メリーゴーランドの停止する位置をうまく調整して、乗れないお客さまをできるだけ少なくするようにしなければなりません。
乗り場０～７で待っているお客さまの人数をファイルから読み込んで、それぞれについてどの位置にどの乗り物が来るように止めれば乗れな
いお客さまが最も少なくなるかを出力して終了するプログラムを作成してください。なお、乗れなくなるお客さまが最小となるとめ方が何通りもある
場合は、そのうちの一つだけ出力するようにしてください。
入力データのファイル名は data10.csv とします。

図1

入力
乗り場 0,1,2,・・・,7 で待っているお客様の人数をそれぞれ p 0 , p1 ,・・・, p 7 とすると、
p 0 , p1 , p 2 , p 3 , p 4 , p 5 , p 6 , p 7 （1 件目のデータ：全て整数）：（2 件目のデータ：全て整数）

出力
メリーゴーランドの乗り物の馬車を 4、車を 2、馬を 1 で表すこととします。乗り場 0,1,2・・・・,7 にとめる乗り物を、それぞれ c 0 , c1 ,・・・, c 7 とすると、
c 0 c1c2

c3

c 7 （1 件目のデータに対する出力：1 又は 2 又は 4

空白区切り）：（2 件目のデータに対する出力：1 又は 2 又は 4

空白区切り）

：

：

c4

c5

c6

入力例
2,3,1,4,0,1,0,1
4,2,3,2,2,2,1,1

出力例
1 4 1 4 1 2 1 2
4 1 4 1 2 1 2 1
11PC 甲子園２００５予選問題

問題１１

元号変換（ ７点）

１／２

西暦で表された年月日を、元号を用いた和暦に変換し、その年月日を出力して終了するプログラムを作成してください。入力は例に示すように 3 つの整数であり、順に西暦年、月、日です。これを、出力例に示すように変換してください。なお、明治以前の年月日が入力された場合は「明治以前」と表示してください。
各年号の最初の年は「元年」ではなく「１年」と出力することとします。
元 号

期

間

明 治

1868. 9. 8～1912. 7.29

大 正1912. 7.30～

1926.12.24

昭 和

1926.12.25～

1989. 1. 7

平 成

1989. 1. 8

～

入力
年（整数）
月（整数）
日（整数）

出力
元号 年月日

入力例１
2005
9
3

出力例１
平成 17 年 9 月 3 日

入力例２
1868
12
2

出力例２
明治 1 年 12 月 2 日

12PC 甲子園２００５予選問題

問題１１

元号変換（ ７点）

２／２

入力例３
1868
9
7

出力例３
明治以前

13

PC 甲子園２００５予選問題

問題１２

サーチエンジン（ ７点）

インターネットの検索エンジン、例えば、Google などでは、世界中のウェブページを自動で収捨して分類し、巨大なデータベースを作成します。また、ユーザが入力した検索キーワードを解析して、データベース検索のための問い合わせ文を作成します。
いずれの場合も、効率的な検索を実現するために複雑な処理を行っていますが、とりあえずの基本は全て文章からの単語の切り出しです。
ということで、文章からの単語の切り出しに挑戦してください。今回は以下の通り、単語区切りが明確な英語の文章を対象とします。
・対象となる文章 ： 改行を含まない 1024 文字以下の英語の文章

・

区 切 り 文 字 ： いずれも半角で空白、ピリオド、カンマのみ

・

切 り 出 す 単 語 ： 3 から 6 文字の単語（2 文字以下や 7 文字以上の単語は無視）

入力データのファイル名は data12.txt とします。

入力
区切り文字及び英数字で構成される英文１行（すべて半角）出力
空白文字１文字（半角）で区切られた単語

入力例１
Rain, rain, go to Spain.

出力例１
Rain rain Spain

入力例２
Win today’s preliminary contest and be qualified to visit University of Aizu.

出力例２
Win and visit Aizu

14

PC 甲子園２００５予選問題

問題１３

ヨセフのおいも（ ７点）
昔、ヨセフのおイモというゲームがありました。 n 人が参加しているとしましょう。参加者は中心を向いて円陣を組み、1 から順番に番号が振られます。アツアツのおイモがひとつ、参加者 n （左の図は
n =30 の場合で、内側の大きい数字の 30）に渡されます。おイモを渡された参加者は右隣の参加者にそのおイモを渡します。 m 回目に渡された人は右隣の人に渡して円陣から抜けます(左の図では
m =9 の場合を表しています)。 m 回渡す毎に一人ずつぬけ、最後に残った人が勝者となり、おイモをいただきます。 n , m が決まってから、実際におイモを渡し始める前にどこにいたら勝てるかわかるといいですよね。
左の図は 30 人の参加者で 9 人ごとに抜けるというルールでこのゲームをした場合を書き表しています。内側の大きい数字が参加者に振られた番号、外側の小さい数字が抜ける順番です。それによると、9,18,27,6,16,26 という順番で円陣から抜け出し、最後には 21 が残ることになります。すなわち 21 が勝者となります(小さい数字が 30 になっています)。ゲーム参加者数 n と円陣から抜け出す参加者の間隔 m を入力し、勝者の番号を出力して終了するプログラムを作成してください。ただし、 m < n <1000 とします。

入力
ゲーム参加者数 n （整数）
円陣から抜け出す参加者の間隔 m （整数）出力
勝者となりおイモをいただく人の番号（整数）

入力例１
41
3

出力例１
31

入力例２
30
9

出力例２
21
15

PC 甲子園２００５予選問題

問題１４

市中パトロール（ ７点）

１／２

文久２（1862）年、会津の殿様が京都守護職を命ぜられました。京都守護職とは治安の悪化した幕末の京都を守る大切な役目です。幕府や他の藩と分担して市中をパトロールしなければなりません。ところがいざ分担ルートを決める段になって、家臣の中でも有名な頑固者の古老から以下のような注文がつきました。
一、武士たる者、スタート地点とゴール地点は厳に守らねばならぬ。

一、一度のパトロールで、二度・三度同じ道を辿るは、武士の面目に関わる。

一、

ただし、交差点は二度以上通るもやむなし。

大変なことになりました。殿様といえどもこの家臣の言い分を無視するわけにはいきません。分担ルートの選択によっては、「武士の面目が立たない」ということになってしまいます。
ということで、スタート地点、ゴール地点、交差点の情報を入力として、上の三つの条件を満たすがどうかを判定するプログラムを作って、殿様に献上してください。
スタート地点を 1、ゴール地点を 2、その他の交差点を 3 以上の整数で表します。1 つの道路は、その道が結ぶ 1 組の交差点番号で表します。なお、交差点の数は 100 以下とし、全ての交差点からスタート地点およびゴール地点への経路がそれぞれ一つ以上あるものとします。
入力データのファイル名は data14.csv とします。

入力a, b 交差点 a と b とをつなぐ道路（ a, b とも自然数、カンマ区切り）
c, d

：
：

出力
OK

武士の面目が立つ場合（三つの条件を満たす場合）

ＮＧ

それ以外の場合（三つの条件を満たさない場合）

16

PC 甲子園２００５予選問題

問題１４

市中パトロール（ ７点）

２／２

入力例１
1,3
3,4
3,5
3,6
4,6
4,7
4,7
5,6
6,7
5,8
5,8
6,8
6,9
7,9
8,9
9,2

出力例１
OK

入力例２
1,3
3,4
3,4
4,2

出力例２
NG

17

PC 甲子園２００５予選問題

問題１５
博

博士の奇妙な数式（ ７点）

１／２

士 : ピーター君、ついにやったよ。

ピ ー タ ー : またですか。今度はどんなくだらない発明ですか。
博

士 : ついに数式を計算機で処理する画期的な方法を思いついたんだ。この表をみてごらん。
通常の記法

博士の「画期的な」記法

1 + 2

1 2 +

3 * 4 + 7

3 4 * 7 +10 / ( 2 - 12 )10 2 12 - /( 3 - 4 ) * ( 7 + 2 * 3 )3 4 - 7 2 3 * + *ピ ー タ ー : はぁ。
博士 : ふっふっふ。これだけでは、未熟者の君には何のことだかわからないだろうねえ。ここからが肝心なんじゃ。

ピ ー タ ー : っていうか・・・。
博士 : 計算機にはスタックというデータ構造があることは君も知っているね。ほれ、「先入れ後出し」のあれじゃよ。

ピ ー タ ー : はい。知ってますが、あの・・・。
博士 : この画期的な記法はあのスタックを使うんじゃ。例えばこの 10 2 12 - / だが、次のように処理する。
処理対象
スタック

博

10

2

12

-

/

↓

↓

↓

↓2-12

↓ 10/-10

10

2

12

-10

-1

・

10

2

10

・

・

・

10

・

・

士 : どうじゃな。括弧も演算子の優先順位も気にする必要がないじゃろう？語順も「10 を 2 から 12 を引いたもので割る。」となり、何となく彼の極東の島国の言葉、日本語と似ておるじゃろうて。
この画期的な発明さえあれば、我が研究室は安泰じゃて。ファファファ。

ピ ー タ ー : っていうか博士。これって日本にいたとき会津大学の基礎コースで習いましたよ。「逆ポーランド記
法」とかいって、みんな簡単にプログラムしてました。
博

士 : ・・・。

ということで、ピーター君に変わって博士に、このプログラムを教える事になりました。「逆ポーランド記法」で書かれた数式を入力とし、計算結果を出力し終了するプログラムを作成してください。

入力
逆ポーランド記法による数式（数と演算記号が空白文字１文字（半角）で区切られた 80 文字以内の文字列。
ただし、数は 10 個以内で全て正の整数）

出力
計算結果（実数）18

PC 甲子園２００５予選問題

問題１５

博士の奇妙な数式（ ７点）

２／２

入力例１
10 2 12 - /出力例１-1.000000

入力例２
3 4 - 7 2 3 * + *

出力例２-13.000000

19PC 甲子園２００５予選問題

問題１６
博

博士の愛した符号（２０点）

１／２

士 : ピーター君、ついにやったよ。

ピ ー タ ー : どうしました、デビッド博士？またくだらない発明ですか？
博

士 : この表だよ、この表。
文字
（空白）

符号
101

文字
C

符号
0101

文字
K

符号
0110

文字
S

符号
00110

’
,

000000

D

0001

L

00100

T

00111

000011

E

110

M10011001

U

10011100-

10010001

F

01001

N

10011110

V

10011101.

010001

G

10011011

O

00101

W

000010?

000001

H

010000

P

111

X

10010010

A

100101

I

0111

Q

10011111

Y

10010011

B

10011010

J

0011000

R

1000

Z

10010000

ピ ー タ ー : なんですか? この表は。
博士 : いいから、言う通りにしてみなさい。まず、お前の名前を紙に書いてごらん。

ピ ー タ ー : はい“PETER POTTER” っと。
博士 : そうしたら、１文字ずつ、この表の「符号」に置き換えるのだよ。

ピ ー タ ー : えーと“P” を「111」にして“E” を「110」して…結構面倒ですね。
111 110 00111 110 1000 101 111 00101 00111 00111 110 1000になりました。なんだか、バーコードみたいですね。
博

士 : よろしい。そうしたら、置き換えた文字列を全部つなげて、５文字ごとに区切ってみなさい。

ピ ー タ ー : はいはい、つなげて区切ると。「11111 00011 11101 00010 11110 01010 01110 01111 10100 0」
こんな感じになりました。けど、最後の「0」だけのやつはどうしますか?
博

士 : ０を付け加えて５文字にしておいてくれ。

ピ ー タ ー : えーと最後が０が1個だけだから０をあと４つ加えてやればいいんですね。できました。
11111 00011 11101 00010 11110 01010 01110 01111 10100 00000
博

士 : 次はこの表を使うのだ。
符号
00000

文字
A

符号
01000

文字
I

符号
10000

文字
Q

符号
11000

文字
Y

00001

B

01001

J

10001

R

11001

Z

00010

C

01010

K

10010

S

11010

00011

D

01011

L

10011

T

11011

(空白)
.

00100

E

01100

M

10100

U

11100

,

00101

F

01101

N

10101

V

11101

-

00110

G

01110

O

10110

W

11110

00111

H

01111

P

10111

X

11111

’
?

ピ ー タ ー : これをどう使うんですか? 今度は符号から文字に置き換えるのか!
博

士 : そうそう。「11111」だったら「?」に、「00011」だったら「D」にとやってゆけばいいんだよ。

ピ ー タ ー : これは単純ですね……えーと「?D-C’KOPUA」になりました。でも意味不明ですよ。
博

士 : 文字数を数えてごらん。

ピ ー タ ー : １０文字ですよ。あっ、「PETER POTTER」は１２文字だったのに２文字減っています。
20

PC 甲子園２００５予選問題

問題１６
博

博士の愛した符号（２０点）

２／２

士 : そう、この表を使えば文字を減らすことができるのだよ。じゃあ今度はこの文章で同じことをやってごらん。
PETER PIPER PICKED A PECK OF PICKLED PEPPERS. A PECK OF PICKLED PEPPERS
PETER PIPER PICKED. IF PETER PIPER PICKED A PECK OF PICKLED PEPPERS, WHERE’S
THE PECK OF PICKLED PEPPERS PETER PIPER PICKED?

ピ ー タ ー : ぎょぎょ、行が分かれていますが、どうするんですか?
博

士 : 紙の都合で３行になってしまったが、改行文字のかわりに空白がある長い１行だと思っておくれ。

ピ ー タ ー : はいはい。行と行の間にあるのは空白だと。しかし面倒だな……。
博士 : だったらプログラムにやらせればいいではないか。

ということで、ピーターの代わりにファイルから読み込んだ文字列を博士の変換方法に従って変換し、変換後の文字列を出力して終了するプログラムを作成してください。
入力データのファイル名はdata16.txtとします。

入力
文字列１行（すべて半角）

出力
変換後の文字列

入力例
PETER POTTER

出力例?D-C’KOPUA

21

PC 甲子園２００５予選問題

問題１７

ひしがた通路での最短経路探索（２０点）

１／２

7
3
8
2
4

8
1

7
5

2

7

0
4

2
7

8

3

4
6

4
1

3

8
2
5

4

4

1
7

5
2

0

4

7

4
6

4
1

3

7
図

0

2

8

8

8

5
4

0
8

7
１

図

２

図１に例示するように整数（0 以上 99 以下）をひしがたに並べます。このような、ひしがたを表すデータをファイ
ルから読み込んで、一番上からスタートして一番下まで次のルールに従って進むとき、通過する整数の和の最大値を出力して終了するプログラムを作成してください。
・ 各ステップで、対角線上の左下か対角線上の右下に進むことができます。
例えば図 1 の例では、図 2 に示すように、7,3,8,7,5,7,8,3,7 を選んで通ったとき、その和は最大の 55（7+3+8+7+5+7+8+3+7=55）となります。
入力データのファイル名は data17.csv とします。

入力
図 1 のひしがたの場合、入力例のようにデータが保存されています。データの行数は、100 行未満です。

出力
ルールに従って通過する整数の和の最大値

22

PC 甲子園２００５予選問題

問題１７

ひしがた通路での最短経路探索（２０点）

２／２

入力例
7
3,8
8,1,0
2,7,4,4
4,5,2,6,5
2,7,4,4
8,1,0
3,8
7

出力例
55

23

PC 甲子園２００５予選問題

問題１８

シールの重なり（２０点）

１／２

1 辺の長さが 10 の正方形の折り紙に半径 1 の円形のシールを n 枚貼ります。シールは重ねて貼ることができます。シールを貼る位置の座標をファイルから読み込んで、折り紙上でもっとも多くシールが重なっている場所
でのシールの枚数を出力して終了するプログラムを作成してください。ただし、 n は 100 以下とします。
入力データのファイル名は data18.csv とします。

入力
折り紙の左下を原点とした x, y 座標を与えます。この x, y を円の中心としてシールを貼ることとします。円の中心が折り紙の外に出ることはありません。
x1 , y1 （1 枚目のシールの中心座標：全て実数）
x 2 , y 2 （2 枚目のシールの中心座標：全て実数）
x 3 , y 3 （3 枚目のシールの中心座標：全て実数）：：
x n , y n （ n 枚目のシールの中心座標：全て実数）

出力
折り紙上で最も多くシールが重なっている場所でのシールの枚数（整数）

入力例
3.14979,8.51743
2.39506,3.84915
2.68432,5.39095
5.61904,9.16332
7.85653,4.75593
2.84021,5.41511
1.79500,8.59211
7.55389,8.17604
4.70665,4.66125
1.63470,4.42538
7.34959,4.61981
5.09003,8.11122
5.24373,1.30066
0.13517,1.83659
7.57313,1.58150

出力例
4
24

PC 甲子園２００５予選問題

問題１８

シールの重なり（２０点）

２／２

参考
入力例のようにシールを貼った図です。円はシール、数字は入力例の行数を表しています。
点(2.3,4.6)では、入力例の 2 行目、3 行目、6 行目、10 行目の 4 枚のシールが重なっています。

6 と 9 のおのおのの中心の距離は 2.01293 なので、シールは重なっていません。1 と 12 のおのおのの中心の
距離は 1.98231 なので、シールは重なっています。
２つの円が接しているとき（おのおのの中心の距離が 2 のとき）は、重なっているものとします。

25

PC 甲子園２００５予選問題

問題１９にじみ（２０点）

１／２

図 1 のような 10×10 のマス目の「布」があり、（1，2）のように X 座標・Y 座標の値の対でマス目を示すことにします。座標値は 0 から始まる整数とします。例えば、図 1 の◎の座標は(1,2)です。
この「布」に染料を少しずつたらして染物を作ります。たらす染料の滴には「大」「中」「小」の 3 サイズがあり、染料の滴の落ちたマス目を中心に図 1 のように周囲も色がつきます。図 1 で☆が中心、○が色のにじむ範囲です。
X 方 向
0
Ｙ

0

方

1

向

2

1

2

3

4

5

6

7

8

9

中
◎

3
4

大

5

○

6
7

○

8

○

○

○

☆

○

○

○

○

小

○

○

○

○

☆

○

○

○

○

9

○

○
○

○

☆

○

○

○
図 １

「布」は、最初は「まっしろ」つまり、どのマス目も色の濃さを示す値が 0 とします。染料の滴が落ちるごとに値が1 ずつ増えていきます。「小」が（1,2）、「中」が（3,2）に落ちた場合、各マス目の値は図 2 の左のようになります。
染料がもったいないので、図 2 の右に示すようなにじむ範囲が布の外にはみ出すような染料の落とし方はしないことになっています。また、同じ場所に複数の染料をたらすこともあります。
Ｘ 方 向
0

1 2

3

4

5

6 7

8 9

Ｙ

0

0

0

0

0

0

0

0

1

1

1

方

1

0

1

1

1

1

0

0

0

1

0

向

2

1

1

2

1

1

0

0

0

0

0

3

0

1

1

1

1

0

0

0

0

0

4

0

0

0

0

0

0

0

0

0

0

:
図 ２
このような作業を何回か繰り返した結果、布にすばらしい模様が浮かび上がりましたが、残念なことに、うっかり作業経過を記録し忘れてしまいました。どうにもさっぱり思い出せませんが、かろうじて、落とした染料の滴数は覚えていました。あなたは、すばらしい染物を再現しなければなりません。すばらしい染物のデータをファイルから読みこんで、どこに、どのような染料をたらしたかを出力して終了するプログラムを作成してください。なお、落とした染料の滴数は 12 以下とします。
入力データのファイル名は data19.csv とします。
26

PC 甲子園２００５予選問題

問題１９にじみ（２０点）

２／２

入力
最初の 1 行に落とした染料の滴数が保存されています。次の行から 10 行に各座標の色の濃さが保存されています。入力例を見てください。

出力
染料の滴の「大」を 3、「中」を 2、「小」を 1 で表し、次のように出力してください。出力行は順不同です。
X 座標,Y 座標,滴の大きさ（全て整数 カンマ区切り）:（全て整数 カンマ区切り）

:

入力例
6
0,0,1,0,0,0,0,0,0,0
0,1,1,1,0,0,0,0,0,0
1,1,1,1,1,1,1,1,0,0
0,1,1,1,1,1,1,1,0,0
0,0,1,1,1,3,1,1,0,0
0,0,1,1,3,1,1,1,0,0
0,0,1,1,1,1,1,1,1,0
0,0,1,1,1,1,1,1,1,1
0,0,0,0,0,0,1,1,1,0
0,0,0,0,0,0,0,1,0,0

出力例
2,2,3
7,7,3
6,3,2
3,6,2
4,4,1
5,5,1

27

PC 甲子園２００５予選問題

問題２０

正方形探索（２０点）

１／２

縦に 10 行、横に 10 列並べられた、合計 100 のマス目があります。いくつかのマス目には印がついています。
各マス目の印の状態をファイルから読み込み、印のついていないマス目だけからなる最大の正方形の辺の長さを出力として表示するプログラムを作成してください。
入力データは 1 行 10 文字から構成され、10 行が与えられます。たとえば以下のようなデータが与えられます。
...*....**..........
**....**..
........*.
..*.......
..........
.*........
..........
....*..***.*....*...
入力データの一行が、一行のマス目を表現します。入力データの文字列のうち、.（ピリオド）は印のついていな
いマス目、*（アスタリスク）は印のついているマス目を示しています。入力データの文字列には、ピリオド、アスタ
リスク、改行以外の文字は含まれません。
上記の例では、下図の 0 で示される正方形が最大となります。
...*....**..........
**....**..
...00000*.
..*00000..
...00000..
.*.00000..
...00000..
....*..***.*....*...
よって、5 と出力すれば正解になります。
なお、すべてのマス目に印がついている場合には、0 を出力してください。
入力データのファイル名は data20.txt とします。

入力
マス目の状態を表現する、ピリオドとアスタリスクからなる文字列

出力最大の正方形の辺の長さ（整数）28

PC 甲子園２００５予選問題

問題２０

正方形探索（２０点）

２／２

入力例１
...*....**..........
**....**..
........*.
..*.......
..........
.*........
..........
....*..***.*....*...

出力例１
5

入力例２
****.******..*.*....
****.*....
*....*....
*....*****..........
****.******..*...*..
****...*..
*..*...*..

出力例２
3

29

PC 甲子園２００５予選問題