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

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

問題１問題１ 柴犬の数（３点）

イヅア公園には、夕方になると柴犬と散歩する人たちがたくさん来ます。柴犬には毛の色によって赤柴、黒柴、白柴、胡麻柴という種類があります。柴犬がたくさんいるとうれしいトモエちゃんは、それぞれの毛色の柴犬が何頭いるかがんばって数えましたが、まだ足し算ができないので柴犬が全部で何頭いるかわかりません。

課題それぞれの毛色の柴犬の数が与えられたときに、柴犬の総数を計算するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
R B W G
１行に赤柴の数R(1≦R≦100)、黒柴の数B(1≦B≦100)、白柴の数W(1≦W≦100)、胡麻柴の数G(1≦G≦100)が与えられる。

出力柴犬の総数を１行に出力する。

入出力例
入力例１4 2 1 1

出力例１8

入力例２22 18 34 36

出力例２110

問題２問題２ アスキー文字（４点）

コンピュータの内部ではすべての情報が数値として扱われています。たとえば、アスキーコードでは、アルファベットの大文字 A に数値の 65 が割り当てられています。同様にアルファベットの大文字 B に66、C に 67 というように、A から Z には連続してそれぞれ 65 から 90 が割り当てられています。また、
アスキーコードでは、アルファベットの小文字 a に 97 が割り当てられています。同様にアルファベッ
トの小文字 b に 98、c に 99 というように、a から z には連続してそれぞれ 97 から 122 が割り当てられています。

課題
与えられたアスキーコードの数値が、アルファベットの大文字と小文字のどちらを表すか判定するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N
１行に数値N(0≦N≦127)が与えられる。

出力
大文字なら「1」を、小文字なら「2」を、それ以外なら「0」を１行に出力する。

入出力例
入力例１67

出力例１1

入力例２110

出力例２2

入力例３32

出力例３0

問題３問題３ ２の累乗（５点）与えられた数を、それ以下の数の中で最大の２の累乗に変換してください。たとえば、2 や 3 ならば 21=2に変換してください。同様に 4,5,6,7 ならば 22=4 に、8,9,10,11,…,15 ならば 23=8 に変換してください。

課題
与えられた数を、その数以下の数の中で最大の２の累乗に変換するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N
１行に数N(2≦N≦106)が与えられる。

出力変換した数を１行に出力する。

入出力例
入力例１54

出力例１32

入力例２1024

出力例２1024

問題４問題４ 集会所（６点）

イヅア村の住民は村に集会所を建てることにしました。この村では東西に一直線に伸びる道路に沿って建物を建てられる地点が決まっています。最も西の地点を０番目の地点として、そこから等間隔に東に向かって１番目、２番目、…と地点番号が与えられています。村人の家と集会所を建てることができるのは、これらの地点だけです。各家には１人以上の村人が住んでいます。どの村人も隣の地点まで１分間で移動できます。
集会を開くのに便利なように、ある時刻に一斉に全ての村人が自分の家から集会所に向かったとき、全員が集まるのに必要な時間が最小になるような場所に、集会所を建てることにしました。

課題
家の建っている地点の番号が与えられたときに、全ての村人が集会所に集まるのに必要な時間の最小値を計算するプログラムを作成せよ。ただし、集会所の地点番号が家の地点番号と重複してもよいものとする。

入力
入力は以下の形式で与えられる。
N
x1 x2 … xN
１行目に家の数N(1≦N≦1000)が与えられる。２行目に家の建っている地点番号xi(0≦xi≦2000)が与えられる。ただし、家の地点番号は全て異なる(i≠jについてxi≠xjである)。

出力
集会所に集まるのに必要な最小の時間を分単位で１行に出力する。

入出力例
入力例１34 0 1

出力例１2

入力例２21 2

出力例２1

問題５ ねこのねこのあな（７点）

あなたの家の近所には多くの猫が出入りする横穴があります。中は行き止まりで通り抜けることはできませんが、近所の猫が全部入れるくらいの奥行きがあります。穴の幅は猫がちょうど収まるくらいなので、先に入った猫を後から入った猫が押しのけて奥に向かうことはできません。また、先に入った猫が、後から入ってきた猫を押しのけて出口から出ることもできません。
猫好きのあなたは横穴に出入りする猫を順番に記録していきました。記録をはじめたときは横穴の中には一匹も猫はいませんでしたが、やがて猫たちは横穴への出入りを始めました。同じ猫が何度も出入りすることもありました。
記録を終えたあなたは、正しく記録できたかプログラムを書いてチェックすることにしました。

課題
横穴に出入りした猫のリストが与えられる。リストを先頭から順に見ていったとき、それより後ろを見なくても誤りと判断できる最初の位置を求めるプログラムを作成せよ。ただし、猫は 100 匹いて、1 から 100 までの番号が与えられているものとする。

入力
入力は以下の形式で与えられる。
L
c1 c2 … cL
１行目に横穴に出入りした猫のリストの長さL(1≦L≦1000)が与えられる。続く１行に、i番目に横穴に出入りした猫の情報ci(-100≦ci≦100、ただしci≠0)が与えられる。ただし、i番目に出入りした猫の番号がaで、その猫が横穴に入ったときはci=a、横穴から出たときはci=-aである。

出力
リストを先頭から順に見ていったとき、それより後ろを見なくても誤りと判断できる最初の位置を１行に出力する。誤りがない場合は、「OK」を１行に出力する。

入出力例
入力例１41 2 -3 -1

出力例１3

入力例２62 1 2 -2 -1 -2

出力例２3

入力例３52 1 -1 3 -3

出力例３OK問題６問題６ 床（８点）

ヒデヨ博士の家の床には正方形のタイルが敷きつめられています。芸術に造詣が深いヒデヨ博士は、赤、黄、青の塗料を使ってタイルに色を塗ることにしました。はじめに部屋の適当なタイルをひとつ選び、以下の方法で色を塗っていきます。


タイルを塗る色を、赤（図の番号１）、黄（図の番号２）、青（図の番号３）の順に変えていき、青の次はまた赤から始める。
すでに色を塗った領域の隣に正方形を追加し、そこに色を塗る。それらを合わせた領域が長方形になるようにする。正方形を追加する方向は、東、北、西、南の順に変えていき、南の次はまた東から始める（図では、上方向が北、右方向が東である）。

最初に赤く塗ったタイルから東西方向に x 個、南北方向に y 個移動したところにあるタイルは、何色に塗られているでしょうか。ただし、東の方向を x の正の方向、北の方向を y の正の方向とします。

課題
x と y を入力し、タイルの色を出力するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
x y
１行にxとy(-106≦x,y≦106)が与えられる。

出力
タイルの色が赤のとき 1、黄のとき 2、青のとき 3 を１行に出力する。

入出力例
入力例１0 0

出力例１1

入力例２-4 5

出力例２2入力例３8 -14

出力例３3

問題７問題７ アカベコ２０
アカベコ２０（９点）「アカベコ２０」は、イヅア地方の専用劇場で公演を開催しているグループです。アカベコ２０のそれぞれのメンバーは、ある一定の日数ごとに公演に参加することになっています。
今日の公演ではメンバーが全員参加していました。プロデューサーであるあなたは、メンバーから、今後の公演のメンバーの組み合わせを教えてほしい、と頼まれました。あなたは、公演に参加するメンバーの組み合わせがいくつあるのかを数えることにしました。

課題
アカベコ２０のメンバー数と、それぞれのメンバーが公演に参加する周期が１日単位で与えられたとき、参加するメンバーの組み合わせが何通りあるかを数えるプログラムを作成せよ。このとき、グループは同じメンバーで永遠に存続すると仮定する。ただし、だれも参加しない場合は組み合わせに含めないこととする。

入力
入力は以下の形式で与えられる。
Np1 p2 … pN
１行目にアカベコ２０のメンバー数N(1≦N≦20)が与えられる。続く１行に、それぞれのメンバーが公演に参加する周期pi(1≦pi≦40)が与えられる。

出力参加するメンバーの組み合わせの数を１行に出力する。

入出力例
入力例１33 5 2

出力例１7入力例２32 3 6

出力例２3

周期が２日のメンバーのみが参加する公演，周期が３日のメンバーのみが参加する公演，周期が２日、３日、６日のメンバーが参加する公演の３通りとなる。

問題８問題８ 矢印

（１１点）
１１点）

L 個のマスが左右に一列に並んでいます。いくつかのマスの上に駒が置いてあります。駒には左向きか右向きの矢印が書いてあります。なお、一つのマスに二つ以上の駒を置くことはできません。
どのマスにいる駒も、駒が置かれていないマスに動かすことができます。ただし、一度に動けるのは隣のマスまでで、一度に動かせるのは一つの駒だけです。駒は、矢印の向きにかかわらず、左にも右にも動かすことができます。ただし、駒を矢印の方向に一回動かすと点数が１点もらえますが、矢印とは逆方向に一回動かすと１点減点されてしまいます。なお、どのような状況から始めたとしても、得られる点数には必ず最大値があることがわかっています。

課題
マスの個数と駒の状況が与えられたとき、得られる最大の点数を計算するプログラムを作成せよ。ただし、マスには列の左端から順番に 1 から L までの番号が割り当てられているものとする。

入力
入力は以下の形式で与えられる。
N L
p1 d1
p2 d2
:
pN dN
１行目に駒の数N(1≦N≦105)とマスの数L(N≦L≦109)が与えられる。続くN行に駒が置かれたマスの番号
pi(1≦pi≦L)と駒に書かれた矢印の向きdi(0または1)が与えられる。ただし、diが0のときは矢印が左向。
き、1のときは右向きを表す。同じマスの番号は与えられない（i≠jについて、pi≠pj）

出力得られる最大の点数を１行に出力する。

入出力例
入力例１2 103 06 1

出力例１6入力例２2 82 18 0

出力例２5入力例３2 81 08 1

出力例３0問題９問題９ 天空の城ツルガ

（１１点）
１１点）

天空の城ツルガはアイヅ国の上空に浮かんでいる。アイヅ国では、天空の城ツルガによって日光がさえぎられる日もある。日光が当たらない日があった場所の住人には、その日数に応じて補償金を支払っている。アイヅ国の補償金支払い担当者であるあなたは、天空の城ツルガの日ごとの位置と補償金の申請があった場所のリストから、その日にその場所で日光が当たらなかったことを確かめる必要がある。

課題
天空の城ツルガの場所とアイヅ国の地上のある場所が与えられたとき、その日にその場所が影に入っていたかどうかを判定するプログラムを作成せよ。影の中に入っていたかどうかは、ある特定の時刻で判定するので、天空の城ツルガや太陽の移動については考えなくて良い。太陽の位置は x=y=0,z=106 にある大きさのない点であり、天空の城ツルガは z=100 の平面にある凸多角形、地上の場所は z=0 にある大きさのない点とする。また、ある地点と太陽を結ぶ直線を天空の城ツルガがさえぎるとき、その地点は影に入るものとする。

入力
入力は以下の形式で与えられる。
N
xt1 yt1xt2 yt2:xtN ytNQ
xa1 ya1xa2 ya2:

xaQ yaQ
１行目に天空の城ツルガの領域を表す点の数N(3≦N≦3×104)が与えられる。続くN行に、領域を構成する頂点の座標xti,yti(-108≦xti,yti≦108)が領域の重心の周りに反時計回りに整数で与えられる。ただし、同じ座標をもつ頂点は与えられない（i≠jについて、xti≠xtj または yti≠ytj）。また、領域の面積は0より大きいと考えて良い。続く１行に、補償金の申請があった場所の数Q(1≦Q≦6×104)が与えられる。
続くQ行に、補償金の申請があった場所の座標xai,yai(-108≦xai,yai≦108)が整数で与えられる。ただし、補償金の申請があった場所の座標は、天空の城ツルガの影の輪郭線から距離10-3以上離れていると考えて良い。

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

出力補償金の申請があった各場所について、影に入っていたら「1」、入っていなかったら「0」を１行に出力する。

入出力例
入力例１60 0
4 0
6 35 5
1 50 352 26 63 15 1-1 -1

出力例１10100

入力例２4100000 100000
101000 100000
101000 101000100000 101000
2100005 100005
101005 101005

出力例２01

問題１０
問題１０ トーナメントの記録

（１２点）
１２点）

N 人が参加するトーナメントを行いました。トーナメントでは一対一で対戦を行い、勝ち負けを決定します。勝った方が次の試合に進んでゆき、最終的に残った一人が優勝します。トーナメントが行われる会場はひとつしかないので、同時に行えるのは１試合のみです。
トーナメントが終わって優勝者が決まるまで、記録係のあなたは対戦の勝者と敗者を記録しました。あなたは対戦ごとに１枚の紙を使って正しく記録しましたが、記録した紙の順序がいくつか入れ替わった可能性があります。

課題
順序が入れ替わった可能性のある対戦の記録から、あり得る対戦の順番が何通りあるかを求めるプログ
ラムを作成せよ。ただし、トーナメントの参加者には 1 から N までの番号が割り当てられているものとする。

入力
入力は以下の形式で与えられる。
N
a1 b1
a2 b2
:
aN-1 bN-1
１行目に出場者の数N(2≦N≦1000)が与えられる。続くN-1行に、試合の勝者と敗者の記録ai,bi(1≦ai,bi≦N)が与えられる。ただし、aiが勝者、biが敗者を表す。

出力あり得る対戦の順番が何通りあるかを表す数を 106 で割った余りを１行に出力する。

入出力例
入力例１31 2
1 3

出力例１2

入力例２32 1
1 3

出力例２1

問題１問題１１ イワシロの祈り
イワシロの祈り

（１２点）
１２点）

古代国家イワシロでは、災害が起きたときにそれを鎮めるために、神官が祈りをささげます。
神官は古文書から文字列 S を選び、以下を繰り返すことで儀式を進めていきます。


文字列 S の中の場所を一つ選び、そこに書かれた文字を他の文字に入れ替えて、S を更新する。
S がどのような文字列の繰り返しで表せるかを見つけて、見つけた文字列を唱える。ただし、S が文字列の繰り返しで表せないときは S を唱える。

祈りの効力が最大になるのは、最も短い文字列の繰り返しで元の文字列を表すものを唱えたときです。
たとえば、abababab という文字列に対して、この文字列そのものや abab ではなく、ab と唱えたときに祈りの効力が最大になります。
新米神官のあなたは、与えられた文字列 S から祈りの効力を最大にする文字列を素早く見つける方法を会得しなければなりません。

課題
文字列 S と文字の入れ替えの情報がいくつか与えられる。文字を入れ替えるたびに、得られた文字列について祈りの効力を最大にする文字列の長さを求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N Q
S
p1 c1
p2 c2
:
pQ cQ
１行目に文字列の長さN(2≦N≦105)と文字を入れ替える回数Q(1≦Q≦105)が与えられる。２行目に英小文字からなる長さNの文字列Sが与えられる。続くQ行に、i番目に入れ替える文字の位置pi(1≦pi≦N)と入れ替えた後の文字ciが与えられる。ただし、piは文字列の左端から数えて何番目かで表される。また、ciは英小文字である。

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

出力
文字を入れ替えるたびに、得られる文字列について祈りの効力を最大にする文字列の長さを１行に出力する。

入出力例
入力例
6 5ababac
6 b3 c4 a5 b6 c

出力例
26663

問題１
問題１２ ダンジョン３（１２点）
１２点）

あなたは有名な冒険家であり、すでに２つのダンジョンを制覇した。あなたはいくつかの通路と宝物庫が記された新たなダンジョンの地図を入手した。地図にはそれぞれの宝物庫にある財宝の価値が書かれている。
あなたは、任意の宝物庫からダンジョンに侵入し、任意の宝物庫からダンジョンを脱出することができる。侵入から脱出までの間に、通路を通って宝物庫の間を何度か移動して、訪れた宝物庫の財宝を手に入れることができる。地図によれば、各通路は双方向に通ることができ、どの宝物庫からどの宝物庫にも１本以上の通路を経由してたどりつくことができる。しかし、通路は一度通ると二度目以降は一度目と同じ向きにしか通ることができなくなる。宝物庫の財宝は、そこを最初に訪れたときだけ手に入れることができる。このとき、手にする財宝の価値の総和を最大にしたい。

課題
地図の情報が与えられたとき、侵入から脱出までの間に手にいれることのできる財宝の価値の総和の最大値を求めるプログラムを作成せよ。ただし、宝物庫には 1 から N までの番号が割り当てられているものとする。

入力
入力は以下の形式で与えられる。
N M
v1
v2:
vN
s1 t1
s2 t2:
sM tM
１行目に宝物庫の数N(2≦N≦105)と通路の数M(1≦M≦2×105)が与えられる。続くN行に、i番目の宝物庫に置かれている財宝の価値vi(1≦vi≦1000)が与えられる。続くM行に、それぞれの通路の両端に接続されている宝物庫の番号si,ti(1≦si,ti≦N, si≠ti)が与えられる。ただし、同じ宝物庫同士をつなぐ通路は２度以上与えられない。

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

出力得ることができる財宝の価値の総和の最大値を１行に出力する。

入出力例
入力例
5 4213641 22 32 44 5

出力例14