全国高等学校パソコンコンクール
プログラミング部門 本選問題
平成２９年１１月３日(平成２９年１１月３日(金祝)
金祝) 午後１時４５分～午後５時４５分

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

1/21

問題１
問題１ 旗を作ろう（３点）

アイヅ放送協会の教育番組(ＡＨＫ教育)では、子ども向けの工作番組「あそんでつくろ」を放送しています。今日のテーマは「自分の旗を作ろう」です。旗は長方形で、真ん中に自分のイニシャルを１文字書きます。

+-------+|.......||...A...|

課題|.......|+-------+

旗の大きさと旗の真ん中に書く文字が与えられたとき、右の図の例のような旗を描くプログラムを作成せよ。

幅９,高さ５,真ん中の文字が Aの旗の図

入力
入力は以下の形式で与えられる。
W H c

１行に旗の幅Wと高さH (3≦W,H≦21)、旗の真ん中に書く文字cが与えられる。ただし、WとHはともに奇数であり、cは英大文字１文字とする。

出力指定された大きさを持ち、指定された文字が真ん中に書かれた旗を出力する。旗の四隅には「+」、横の辺には「-」、縦の辺には「|」、旗の内部（真ん中の文字以外）には「.」を使う。

入出力例
入力例１3 3 B

出力例１+-+|B|+-+

入力例２11 7 Z

出力例２+---------+|.........||.........||....Z....||.........||.........|+---------+

2/21

問題２ Bange Hills Tower（４点）

バンゲ町に新しく建つことになった Bange Hills Tower は、屋上からワカマツ城の天守閣が上から下まで見えるのを売りにしようと考えています。そのためには、以下の図のように、市街地のどの建物にもさえぎられずに、タワーの屋上からワカマツ城の天守閣の下端が見えなければいけません。
タワー屋上
ワカマツ市街地
ワカマツ城建物群

地面
タワー建設予定地

課題
タワー建設予定地と市街地の建物の情報が与えられたとき、タワー屋上からワカマツ城の天守閣が上から下まで見えるために、最低限必要なタワーの高さを計算するプログラムを作成せよ。ただし、ワカマツ城やタワーも含めたすべての建物を、地面と垂直な線分とみなす。このとき、タワーの上端からワカマツ城の下端への視線（図の中の矢印）が、どの建物とも交差しない（建物の上端に接する場合は交差しないと考える）とき、タワーの屋上からワカマツ城の下端が見えると考えて良い。

入力
入力は以下の形式で与えられる。
N t
x1 h1x2 h2:xN hN
１行目に市街地の建物の数N(1≦N≦1000)と、タワー建設予定地の位置t(2≦t≦105)が整数で与えられる。
続くN行に、市街地にある建物の位置xi(1≦xi＜t)と地面からの高さhi(1≦hi≦100)が整数で与えられる。
ただし、これらの位置は、ワカマツ城を原点とする、地面に沿った直線上の座標で与えられる。また、同じ位置に建物は与えられない（i≠jについてxi≠xj）。

出力
高さを１行に実数で出力する。ただし、誤差がプラスマイナス 10-3 を超えてはならない。この条件を満たせば小数点以下何桁表示してもよい。

入出力例
入力例
3 106 44 2
3 2

出力例6.666667※ C++のiostreamのcoutを使う場合、coutを行う前に以下の関数を呼び出せば、常に小数点以下の桁までを出力させることができる。
std::cout.setf(std::ios_base::fixed,std::ios_base::floatfield);
3/21

問題３ 歳の差は。

（５点）

はつみとタクは不思議な縁で出会いました。２人は出会いを記憶に残すために、２人の歳の差を計算しようとします。しかし、歳の差はそれを計算する日付によって変化します。２人は計算を進めていくう
ちに、永遠に月日が過ぎても２人の歳の差が最大何歳離れるかは決まっていることに気づきました。

課題
はつみとタクの誕生日が与えられたとき、２人の歳の差の最大値を報告するプログラムを作成せよ。歳は誕生日になった瞬間に１加算されるとする。また、誕生日がうるう年の２月２９日だった場合、うるう年でない年には３月１日になった瞬間１加算されるとする。

入力
入力は以下の形式で与えられる。
y1 m1 d1
y2 m2 d2
１行目と２行目に、それぞれ、はつみとタクの誕生日を示す年月日が与えられる。yi(1≦yi≦3000)が年、mi(1≦mi≦12)が月、di(1≦di≦Dmax)が日である。ただし、Dmaxは以下の条件を満たす。


与えられた年がうるう年でなく月が2月のときは28。
与えられた年がうるう年で月が2月のときは29。
与えられた月が4,6,9,11月のときは30。
それ以外の月は31。

西暦年が4で割り切れる年はうるう年だが、100で割り切れる年はうるう年にならない。ただし、400で割り切れる年はうるう年となる。

出力２人の歳の差の最大値を１行に出力する。

入出力例
入力例１1999 9 92001 11 3

出力例１3

この例では、２００２年以降、例えば１０月１日での２人の歳の差は３歳だが、１２月１日での歳の差は２歳になる。
入力例２2008 2 29
2015 3 1

出力例２8

この例では、２０１６年以降の２月２９日に歳の差が８歳になる。

4/21

5/21

問題４
問題４ 電子メトロノーム（６点）

PCK 君は N 台の電子メトロノームで遊んでいる。i 番目のメトロノームは ti 秒間隔で音が一瞬だけ鳴るようにあらかじめ設定されている。PCK 君はすべてのメトロノームを同時に起動した。
PCK 君は、音が鳴る間隔がバラバラでも、すべてのメトロノームの音が同時に鳴る瞬間が一定の周期で訪れることに気が付いた。この現象をもっと楽しむために、PCK 君はいくつかのメトロノームの鳴る間隔を調整することで、すべてのメトロノームの音が同時に鳴る周期を短くしようとしている。ただし、メトロノームの音が鳴る間隔は増やすことしかできない。

課題
メトロノームの数とそれぞれにあらかじめ設定された秒単位の間隔 ti を入力とし、i 番目のメトロノームの音が鳴る間隔をある負でない整数 di だけ増やすことで、全てのメトロノームの音が同時に鳴る周期を最も短くしたときの、di の合計の最小値を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N
t1
t2:tN
１行目に、メトロノームの数N(1≦N≦105)が与えられる。続くN行に、各メトロノームにあらかじめ設定された間隔ti(1≦ti≦104)が整数で与えられる。

時間制限
入力に対して、実行時間が２秒を超えてはならない。

出力最小値を１行に出力する。

入出力例
入力例１3368

出力例１3

間隔がそれぞれ 3, 6, 8 のメトロノームを一斉に起動すると、24 秒ごとにすべてのメトロノームの音が同時に鳴る。1 つ目のメトロノームの間隔を 1 秒、2 つ目の間隔を 2 秒長くすると、その周期は最も短い 8 秒となる。

6/21

入力例２21010

出力例２0

間隔が 10,10 のメトロノームを同時に起動すると、10 秒ごとにすべてのメトロノームの音が同時に鳴り、これが最小の周期である。

7/21

問題５ 朝昼晩ごはん（７点）

あなたは食堂を経営しており、１日３回だけ食事を提供します。食堂を訪れようとしている客は、朝ごはん、昼ごはん、晩ごはんを受け取ることができる時間帯が決まっています。あなたがこの時間帯に含まれるどこかの時刻で食事を提供すれば、客は食事を受け取れます。あなたは３つの食事を提供する時刻を工夫して、できるだけ多くの客が朝、昼、晩ごはんのすべての食事を受け取れるようにしたいと思っています。

課題それぞれの客が朝ごはん、昼ごはん、晩ごはんを受け取ることができる時間帯が与えられる。あなたが、３つの食事を提供する時刻を決めることができるとき、朝、昼、晩ごはんをすべて受け取ることができる客の最大人数を出力するプログラムを作成せよ。ただし、食事を提供する時刻が、客が食事を受け取れる時間帯の開始時刻か終了時刻と同じ場合は、その客は食事を受け取れるものとする。

入力
入力は以下の形式で与えられる。
N
ast1 aet1 hst1 het1 bst1 bet1
ast2 aet2 hst2 het2 bst2 bet2：
astN aetN hstN hetN bstN betN
１行目に、客の人数N(1≦N≦50)が与えられる。続くN行にi番目の客の、朝ごはんを受け取ることができる時間帯の開始時刻astiと終了時刻aeti、昼ごはんを受け取ることができる時間帯の開始時刻hstiと終了時刻heti、晩ごはんを受け取ることができる時間帯の開始時刻bstiと終了時刻betiが与えられる。
ただし、各時間帯について、開始時刻よりも終了時刻が後となるように与えられる。また、hstiはaetiより後の時刻で、bstiはhetiより後の時刻である。各時間帯は午前０時をまたがない。
各時刻は以下の形式で与えられる。
h m
この時刻はh(0≦h≦23)時 m(0≦m≦59)分を示す。

時間制限
入力に対して、実行時間が６秒を超えてはならない。

出力
朝、昼、晩ごはんをすべて受け取ることができる客の最大人数を、1 行に出力する。

8/21

入出力例
入力例
51 0 2 0 3 30 4 30 6 0 7 02 30 3 0 4 0 5 0 5 30 6 30
1 30 2 30 4 30 5 0 6 30 7 02 30 3 0 5 0 6 0 6 30 7 0
1 0 2 0 3 0 3 30 4 0 5 0

出力例
39/21

問題６問題６ 市松模様

（８点）

あなたは W×H 個のマスから成る方眼紙を持っており、それぞれのマスは白か黒で塗られている。あな
たは、この方眼紙に対して「任意の２つの行を入れ替える操作」「任意の２つの列を入れ替える操作」
をそれぞれ好きな回数だけ、好きな順序で行うことができる。あなたはこの方眼紙で市松模様を作りたいと思っている。市松模様とは、以下のように白と黒の正方形を交互に配した模様である（下の図は W=5,H=5 の場合である）。

課題
方眼紙の情報を入力とし、その方眼紙で市松模様が作れるかどうか判定するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
W H
c1,1 c1,2 … c1,Wc2,1 c2,2 … c2,W:
cH,1 cH,2 … cH,W
１行目に方眼紙の横方向のマスの数 W(2≦W≦1000)と縦方向のマスの数 H(2≦H≦1000)が与えられる。
続く H 行に i 行 j 列目のマスの色を表す整数 ci,j が与えられる。ci,j が 0 のとき白、1 のとき黒色のマスを表す。

出力
市松模様を作れる場合は「yes」、作れない場合は「no」と１行に出力する。

入出力例
入力例１3 21 1 00 0 1

出力例１yes

入力例２2 20 01 1

出力例２no10/21

問題７問題７ おみくじ

（９点）

アイヅ赤ベコ神社には、変わったおみくじがあります。おみくじには、２桁以上の数が書いてあります。
ただし、この神社では 0 は縁起の悪い数字とされているので、各桁は 1 から 9 までの数字です。
このおみくじから次のようにして、願い事が何年後にかなうか占うことができます。おみくじに書かれた数を１か所以上で切ります。切り分けられた数のうち最大と最小のものの差が、願い事がかなうまでにかかる年数になります。あなたが数をどのように切り分けるかによって、かなうまでの年数が変わります。たとえば、おみくじに書かれた数が 11121314 のとき、これを 1,11,21,3,14 のように切り分ければ 21-1=20 年になります。11,12,13,14 のように切り分ければ 14-11=3 年になります。
何も考えずに切った場合、どれだけ早くかなえられるかは運次第ですが、運に頼らずに願い事がかなうまでの最小の年数をプログラムで求めることもできます。

課題
おみくじに書かれている数が与えられたとき、願い事がかなうまでの最小の年数を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
n１行に正の整数nが与えられる。ただし、nの各桁は1から9の数字からなり、桁数は2以上100,000以下である。

時間制限
入力に対して、実行時間が２秒を超えてはならない。

出力
願い事がかなうまでの最小の年数を１行に出力する。

入出力例
入力例１11121314

出力例１3

入力例２123125129

出力例２6

入力例３119138

出力例３511/21

問題８問題８ オノガワ湖調査

（１０点）
１０点）

アイヅ探検隊は、アイヅ自然保護区の調査を計画している。この調査では、調査開始地点から調査終了地点まで、最短の距離で到達したい。ただし、途中でオノガワ湖の沿岸に立ち寄らなければならない。
また、オノガワ湖は沿岸に沿って歩くことはできても、湖に入ることはできない。

課題
調査開始地点と終了地点、凸多角形によって表されるオノガワ湖の領域があたえられたとき、アイヅ探検隊が通るべき最短経路の距離を求めるプログラムを作成せよ。ただし、オノガワ湖では沿岸（領域を構成する辺や点）を通るだけで、内側に入ってはいけない。

入力
入力は以下の形式で与えられる。
xs ysxg yg
N
x1 y1
x2 y2
:

xN yN
１行目に調査開始地点xs,ys(0≦xs,ys≦104)、２行目に調査終了地点xg,yg(0≦xg,yg≦104)がすべて整数で与えられる。続く１行に、オノガワ湖の領域を構成する頂点の個数N(3≦N≦100)が与えられる。続くN行に、領域を構成する頂点の座標xi,yi(0≦xi,yi≦104)が、領域の重心の周りに反時計回りに整数で与えられる。
ただし、入力は以下の制約を満たすものとする。

調査開始地点と終了地点は、領域内部にも領域の境界上にもない。

調査開始地点と終了地点は、同じ座標をもたない（xs≠xg または ys≠yg）。

同じ座標をもつ頂点は与えられない（i≠jについて、xi≠xj または yi≠yj）。

領域の面積は０より大きい。
領域を構成する頂点のうち、どの３点も１直線上にはない。

出力
アイヅ探検隊が通るべき最短経路の距離を出力する。ただし、誤差がプラスマイナス 10-3 を超えてはならない。この条件を満たせば小数点以下何桁表示してもよい。

12/21

入出力例
入力例１0 04 041 12 13 31 2

出力例１4.472136

入力例２4 40 041 13 13 31 3

出力例２6.32455

13/21

問題９問題９ 抽選ボックス（１２点）

アイヅ祭りの一角で抽選会が行われている。抽選ボックスの中には、何種類かのボールが入っている。
それぞれの種類のボールには同じ整数が書いてある。抽選ボックスには一つの整数 T が書かれている。
あなたは、２つの整数 A、B を宣言した上で、ボックスの中から最大 M 個のボールを取り出すことができる。取り出したボールに書かれた整数の和を S とすると、S を T で割った余りが A 以上、かつ、S を Tで割った値（小数点以下は切り捨て）が B 以上のとき、素敵な景品をもらうことができる。

課題
ボールの種類の数、各種類のボールに書かれている整数、取り出すことができるボールの最大数、抽選
ボックスに書かれている整数、２つの整数 A、B からなる宣言が与えられたとき、各宣言に対して景品が得られる可能性があるかを判定するプログラムを作成せよ。ただし、どの種類のボールも M 個以上存在するものとする。ボールを１つも取り出さなくても景品がもらえる場合があることに注意せよ。

入力
入力は以下の形式で与えられる。
N M T
a1
a2:
aN
Q
A1 B1
A2 B2:AQ BQ
1 行目にボールの種類の数 N(1≦N≦105)と、取り出すことができるボールの最大数 M(1≦M≦105)と、抽選ボックスに書かれている整数 T(1≦T≦1000)が与えられる。続く N 行に i 種類目のボールに書かれた整数 ai(1≦ai≦109)が与えられる。続く 1 行に宣言の数 Q(1≦Q≦105)が与えられる。続く Q 行に i 番目の宣言を表す２つの整数 Ai(0≦Ai＜T)、Bi(0≦Bi≦109)が与えられる。

時間制限
入力に対して、実行時間が３秒を超えてはならない。

出力
各宣言に対して、景品がもらえる可能性がある場合は「yes」、ない場合は「no」と１行に出力する。

14/21

入出力例
入力例
3 2 783652 23 2
4 16 16 0

出力例
yesno
yesno
yes

15/21

問題１０
問題１０ パーティ

（１２点）
１２点）

アカベ高校のあるクラスでは、クラスメイトの友達関係を使って、「知り合い」という関係を次のように定めている。
• A さんと B さんが友達なら、A さんと B さんは知り合いである。
•A さんと B さんが友達で、B さんと C さんが知り合いなら、A さんと C さんも知り合いである。

また、「仲間」であるという関係を次のように定めている。
• A さんと B さんが知り合いであって、現在友達である誰か２人のクラスメイトが友達でなくなったとしてもなお A さんと B さんが知り合いであるなら、A さんと B さんは仲間である。
このクラスに最近転校してきた PCK 君は、クラスの人たちを招待してパーティを開こうと考えている。
パーティにより多くの人を招待したいと思い、招待リストを作成した。そのとき、PCK 君が転校してくる前の友達関係を利用して、次のような条件をおいた。
T さんが招待リストに入っているとき、• T さんと仲間である U さんは招待リストに入っている。
• U さんが T さんと仲間ではない場合、U さんが T さんと友達であるか、U さんが T さんの仲間の誰かと友達であるなら、U さんはリストに入っていない。
PCK 君は、この条件を満たす最大人数のクラスメイトを招待リストに入れた。

課題
クラスメイトの人数 N と友達関係が与えられたとき、PCK 君が作ったリストに入っている人の数を求めるプログラムを作成せよ。クラスメイトにはそれぞれ 0 から N-1 までの番号が割り当てられているものとする。

入力
入力は以下の形式で与えられる。
N M
s1 t1
s2 t2
:
sM tM
１行目にクラスメイトの人数 N(2≦N≦105)と友達関係の数 M(1≦M≦2×105)が与えられる。続く M 行に友達関係を表すクラスメイトの番号 si,ti(0≦si,ti≦N-1)が与えられる(si≠ti)。これらはクラスメイトsi とクラスメイト ti が友達であることを表す。ただし、同じ人どうしの友達関係は２回以上与えられない。

時間制限
入力に対して、実行時間が２秒を超えてはならない。

出力
PCK 君が招待したクラスメイトの人数の最大値を１行に出力する。

16/21

入出力例入力例１7 80 11 21 32 30 44 54 65 6

出力例１6入力例２3 20 11 2

出力例２217/21

問題１１ 航空写真

（１２点）
１２点）

ヒデヨさんは、縮尺と東西南北の向きが同じ２枚の航空写真を入手しました。２枚とも様々な種類の建物が写っていますが、雲で隠れて地面が見えない場所もあります。２枚目の写真の範囲は、１枚目の写真の範囲に完全に含まれているようなのですが、これらの写真は違う時刻に撮影されていて、雲で隠れている場所が異なるため、１枚目の写真のどこに２枚目の写真の範囲が写っているかすぐにはわかりません。雲の下には何があるかわからないため、当てはまる位置が複数あるかもしれません。

課題
２枚の写真の情報がピクセル単位で与えられたとき、２枚目の写真が１枚目の写真の上に当てはまる可能性のある位置の個数を出力するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
AW AH BW BH
arow1arow2:
arowAH
brow1brow2:
browBH
１行目に１枚目の写真の横方向と縦方向のピクセル数 AW(1≦AW≦700)と AH(1≦AH≦700)、２枚目の写真の横方向と縦方向のピクセル数 BW(1≦BW≦100)と BH(1≦BH≦100)が与えられる(AW≧BW かつ AH≧BH)。
続く AH 行に、１枚目の写真に写っている、上から i 番目にある行のピクセル情報 arowi が与えられる。
続く BH 行に、２枚目の写真に写っている、上から i 番目にある行のピクセル情報 browi が与えられる。
arowi と browi は、それぞれ長さが AW と BW であり、英大文字、英小文字、数字、または「?」からなる文字列である。１文字が１つのピクセルを表し、英大文字と英小文字と数字が建物の種類を、「?」が雲をそれぞれ表す。

時間制限
入力に対して、実行時間が２秒を超えてはならない。

出力位置の個数を１行に出力する。

18/21

入出力例
入力例１
5 5 3 3AF??z
W?p88???Hk
pU?m?
F???c
F??
p?8?H?

出力例１4

入力例２
6 5 4 2aaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaa

出力例２1219/21

問題１２
問題１２ 鉄の棒

（１２点）
１２点）

PCK 君は 1 番から N 番までの番号が付いた N 本のまっすぐな鉄の棒を持っていましたが、運搬中に 1 番目から M 番目までの M 本が折れ曲がってしまいました(0≦M≦N)。折れ曲がった棒は、どれも１箇所で直角に曲がっています。
PCK 君は折れ曲がった棒の中から X 本、まっすぐな棒から Y 本を、2X + Y = 12 を満たすようにそれぞれ選び、それらをすべて使って直方体を１つ作ろうとしています。ただし、棒をつなげるのは、直方体の頂点だけです。PCK 君は、そのようにして作ることのできる直方体の形がいくつあるか数えようとしています。

課題
鉄の棒の本数と長さ、折れ曲がっている位置、直方体を作るのに使う棒の数が与えられたとき、作ることのできる直方体の形がいくつあるか求めるプログラムを作成せよ。ただし、ある直方体 i と別の直方体 j の幅、奥行き、高さをそれぞれ小さい順に並べたものを Ai,Bi,Ci と Aj,Bj,Cj としたとき、Ai=Aj かつBi=Bj かつ Ci=Cj となる直方体は同じ形とみなす。また、どの鉄の棒も十分細いので、太さは無視することができるものとする。

入力
入力は以下の形式で与えられる。
N M X Y
a1a2:
aNb1b2:bM
１行目に、鉄の棒の数 N(6≦N≦6000）と折れ曲がった棒の数 M(0≦M≦N）、直方体を作るのに使う折れ曲がった棒の数 X(0≦X≦6)とまっすぐな棒の数 Y(0≦Y≦12)が与えられる。ただし、2X+Y=12、X+Y≦N、X≦M である。続く N 行に i 番目の鉄の棒の長さを表す整数 ai(1≦ai≦6000)が cm 単位で与えられる。続く M 行に、1 番目から M 番目までの鉄の棒が折れ曲がっている位置を表す整数 bi(1≦bi≦3000)が与えられる。bi は i 番目の鉄の棒が端から bi cm のところで直角に折れ曲がっていることを表す。ただし、1≦ai-bi≦3000 である。

時間制限
入力に対して、実行時間が４秒を超えてはならない。

出力
直方体の形の個数を１行に出力する。

20/21

入出力例
入力例
18 8 3 643出力例
3333222111112233311111111

21/21