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

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

問題１
問題１ 旅行先のパーティ
旅行先のパーティ（３点）

八重さんは、旅行先で何度か行われるパーティに出席することになりました。パーティでは１回につき１着、ドレスを身に付ける必要があります。旅行には何着かドレスを持っていきますが、パーティの回数よりもドレスの枚数が少ない場合、すべてのパーティに出席するには、同じドレスを何回か身に付ける必要があります。
おしゃれな八重さんは、同じドレスを何回も着たくありません。一番多く使うドレスを着る回数をなるべく少なくしたいと考えています。

課題
ドレスの枚数とパーティの回数が与えられる。一番多く使うドレスを着る回数をなるべく少なくしたときに、そのドレスを何回着なければならないかを計算するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
A B１行にドレスの枚数A(1≦A≦105)とパーティの回数B(1≦B≦105)が与えられる。

出力
一番多く使うドレスを何回着なければならないかを、１行に出力する。

入出力例
入力例１3 5

出力例１2

入力例２25 10

出力例２1

問題２問題２ マンションの設計
マンションの設計（３点）

親方はバンゲヒルズマンションを設計しています。マンションは同じ高さの階を積み上げて建造するので、各階の高さの合計があらかじめ決められたマンションの高さと同じになるよう、設計のときに１階あたりの高さを調整します。1 階あたりの高さは、ある範囲の整数で自由に決めることができます。
マンションの出来栄えは 1 階あたりの高さによって変わります。親方は考えられる 1 階あたりの高さを計算し、何通りの高さが選べるかを計算することにしました。

課題
マンションの高さと、1 階あたりの高さの範囲が与えられたとき、１階あたりの高さが何通りあるかを計算するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
H A B
１行に、マンションの高さH(1≦H≦105)と、１階あたりの高さの範囲の下限Aと上限B(1≦A≦B≦H)がすべて整数で与えられる。

出力
１階あたりの高さが何通りあるかを１行に出力する。

入出力例
入力例１100 2 4

出力例１2

入力例２101 3 5

出力例２0

問題３問題３ ブロック積み上げ（５点）

ブロックを積み上げて塔を一つ作ります。塔はいくつかの段からなり、各段は水平方向にブロックをつなげて作ります。どのブロックも重さは同じで、K 個以下のブロックの重さがかかってもつぶれないだ
けの強度があります。
塔を作るには、次の条件を満たさなければなりません。
 塔のすべての段に１個以上のブロックがある。
 どのブロックにも、ブロックがつぶれない程度の重さしかかかっていない。ただし、各ブロックにかかる重さは、そのブロックより上にあるすべての段のブロックの重さの合計を、そのブロックと同じ段にあるブロックの個数で割った値とする。

課題
ブロックの個数と各ブロックの強度が与えられたとき、作ることのできる塔の段数の最大値を求めるプ
ログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N K
１行にブロックの個数N(1≦N≦105)と、ブロックの強度K(1≦K≦105)が整数で与えられる。

出力
塔の段数の最大値を１行に出力する。

入出力例
入力例１4 2出力例１3入力例２5 2

出力例２4問題４問題４ 賢者の円卓（５点）

N 個の席が円状に並んでいる円卓に、N 人の賢者が座ろうとしている。それぞれの賢者は、利き手で箸を持ち食事をとる。このとき、以下のようなことが起こる。


賢者 i が右利きの場合、その右隣に左利きの賢者が座ると不満度 wi が発生し、右利きの賢者が座ると不満度は発生しない。
賢者 i が左利きの場合、その左隣に右利きの賢者が座ると不満度 wi が発生し、左利きの賢者が座ると不満度は発生しない。

あなたは席順をうまく調整して、発生する不満度の総和を最小化したいと考えている。

課題
賢者の人数、それぞれの利き手と不満度を入力し、不満度の総和の最小値を出力するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N
a1 a2 … aN
w1 w2 … wN
１行目に賢者の人数 N(3≦N≦10)が与えられる。２行目に各賢者の利き手を表す整数 ai(0 または 1)が与えられる。ai が 0 のとき賢者 i は右利き、1 のとき左利きであることを表す。３行目に各賢者の不満度を表す整数 wi(1≦wi≦1000)が与えられる。

出力
不満度の総和の最小値を１行に出力する。

入出力例
入力例１51 0 0 1 02 3 5 1 2

出力例１3

入力例２30 0 01 2 3

出力例２0

問題５問題５ 宝の地図（８点）

実家の蔵を掃除していたコボウ氏は、古い紙の束を見つけた。それぞれの紙には２つの数列が書いてある。不思議に思ったコボウ氏が蔵の中を探すと、先祖が残したメモが見つかった。それによると、この紙は先祖が残した宝の地図で、２つの数列は宝が埋まっている場所の手がかりを表しているらしい。
紙に書かれた数列は、ある場所を格子状に区切ってできる区画のそれぞれの列と行に、いくつ宝が埋まっているかを表している。１つ目の数列の i 番目の数は、左から i 番目の列にいくつ宝が埋まっているかを表している。同様に、２つ目の数列のj 番目の数は、上から j 番目の行にいくつ宝が埋まっているかを表している。たとえば、横方向に５つと縦方向に４つ並んだ区画のうち、右の図の#で示した区画に宝が埋まっているときは、0,2,2,1,1 と 1,1,1,3 という数列で表される。

021121#
#

131#
#

#

#

用心深い先祖は、紙に書かれた数列の意味を推測しにくくするために、有り得ない情報が書かれた紙を紛れ込ませていた。たとえば 3,2,3,0,0 と 4,2,0,0,2 という数列は、横方向と縦方向に５つずつ並んだ区画に宝が埋まっているどのような状況にもあてはまらない。コボウ氏が宝を見つけるには、有り得ない情報が書かれている紙を除外しなければならない。

課題
紙に書かれた情報が与えられたとき、紙に書かれた情報が有り得るかどうかを判定するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
W H
a1 a2 … aW
b1 b2 … bH
１行目に、紙に書かれた横方向の区画の数W(1≦W≦1000)と縦方向の区画の数H(1≦H≦1000)が与えられる。２行目に、その紙に書かれた１つ目の数列のi番目の数ai(0≦ai≦H)が与えられる。３行目に、その紙に書かれた２つ目の数列のj番目の数bj(0≦bj≦W)が与えられる。

出力
紙に書かれている情報が有り得るなら「1」を、有り得ないなら「0」を１行に出力する。

入出力例
入力例１5 40 2 2 1 11 1 1 3

出力例１1

入力例２5 53 2 3 0 04 2 0 0 2

出力例２0

問題６問題６ コプライムソート（８点）

あなたは、与えられた数列を昇順に並べ替えるために、一風変わった方法を考察している。その方法では、与えられた数列に対して、共通の素因数を持つ要素同士の位置のみ交換できる。たとえば数列「6 42 3 7」が与えられたとき、以下のようにすれば整列可能である。
Step 0 : 6 4 2 3 7 (与えられた数列)
Step 1 : 2 4 6 3 7 (要素 6 と 2 を交換)
Step 2 : 2 6 4 3 7 (要素 4 と 6 を交換)
Step 3 : 2 3 4 6 7 (要素 6 と 3 を交換)
ただし、与えられた数列によっては、整列させることができない場合がある。あなたはこの方法を、コプライムソートと名付け、与えられた数列がコプライムソートで整列させることができるか調べることにした。

課題
与えられた整数の数列に対して、共通の素因数を持つ要素同士を交換する操作を任意の回数行うことで、その数列を昇順に整列できるかを判定するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
Na1 a2 … aN
１行目に数列の要素数N(2≦N≦105)が与えられる。続く１行に、数列の各要素を表す整数ai(2≦ai≦105)が与えられる。

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

出力
昇順に整列することができる場合は「1」、できない場合は「0」を出力する。

入出力例
入力例１56 4 2 3 7

出力例１1

入力例２72 9 6 5 6 7 3

出力例２0

問題７問題７ 美しい数列（１０点）

Ａ君は、全国数学コンクールに応募するための自由研究に取り組んでいる。今年のテーマは「美しい数列」。Ａ君は、コンピュータの仕組みに興味を持っており、0 と 1 のみを含む長さ N の数列において、1が M 個連続する部分列を含む数列を「美しい数列」と定義し、作品を作ることにした。
Ａ君は得意のプログラミングで、異なる「美しい数列」がいくつ作れるかを計算し、レポートにまとめることにした。

課題
数列の長さ N と、1 が連続する個数 M を入力とし、美しい数列の個数を求めるプログラムを作成せよ。
ただし、答えは非常に大きくなる場合があるため、1000000007(=109+7)で割った余りを出力せよ。

入力
入力は以下の形式で与えられる。
N M
１行に数列の長さN(1≦N≦105)と、1が連続する個数M(1≦M≦N) が与えられる。

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

出力
美しい数列の個数を１行に出力する。

入出力例
入力例１4 3出力例１3

長さが 4 で 1 が３個連続する数列は、0111、1110、1111 である。
入力例２4 2

出力例２8長さが 4 で 1 が２個連続する数列は、0011、0110、0111、1011、1100、1101、1110、1111 である。

問題８問題８ 給料計算（１０点）

ＰＣＫ社では 0 から N-1 の ID が割り当てられた N 人の従業員が働いている。また、0 から N-1 の ID が割り当てられた N 個の仕事があり、仕事 j にかかる時間は tj である。
ＰＣＫ社では、従業員により多くの仕事を覚えてもらうため、以下の規則で仕事の割り当てを変更している。
 初日を 0 として、d 日目に仕事 j が従業員(j+d)％N に割り当てられる。ここで、p％q は p を qで割った余りを表す。
ＰＣＫ社の給料は時給に応じて日当で支払われる。時給が a の従業員が仕事 j を行うと a×tj 円の給料が発生する。従業員 i の最初の時給は si 円だが、従業員のモチベーションを上げるため、ユニークな方法で給料が上がる。ＰＣＫ社の昇給表には 0 から M-1 の番号が付けられた係数 fk が書かれており、毎日ある一人の従業員の時給が以下の規則で上昇する。
 初日を 0 として、d 日目が終了した時点で、従業員 d％N の時給が f(d％M)円上昇する。ただし、昇給が行われるのは日当が支払われた後である。
ＰＣＫ社の経理担当であるあなたは、初日から D 日分の給料の総額を計算しなければならない。

課題
各従業員の最初の時給、各仕事にかかる時間、昇給表の内容、日数を入力とし、給料の総額を求めるプ
ログラムを作成せよ。ただし、答えは非常に大きくなる場合があるので、1000000007(=109+7)で割った余りを出力せよ。

入力
入力は以下の形式で与えられる。
N M D
s0 s1 … sN-1
t0 t1 … tN-1
f0 f1 … fM-1
１行目に従業員の人数と仕事の個数を表す数N(1≦N≦100)、係数の個数M(1≦M≦100）、日数D(1≦D≦1510 )が与えられる。ただし、N+Mは100以下である。２行目に各従業員の最初の時給si(1≦si≦108)が整数で与えられる。３行目に各仕事にかかる時間tj(1≦tj≦108)が整数で与えられる。４行目に昇給表の各係数fk(1≦fk≦108)が整数で与えられる。

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

出力
給料の総額を１行に出力する。

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

出力例１26

入力例２3 2 53 2 1
1 2 3
1 2

出力例２91

問題９問題９ メイズ＆アイテム（１２点）

メイズ＆アイテムは、アイテムを回収しながら、ゴールを目指すパズルゲームである。迷路は W×H 個のマスから成り、持っているアイテムによって、入れるマスと入れないマスがある。また、アイテムの回収順序によって定められた得点を獲得することができる。ゲームの目的は、スタート地点から出発し、全てのアイテムを回収し、最小の移動回数でゴール地点に到達することである。最小の移動回数でゴール地点に到達できる経路が複数ある場合は、最大の得点で到達することを目指す。
各マスには以下のいずれかの記号が割り当てられている。あなたは以下のルールで、縦または横の辺を共有するマスに移動することができる。ただし、迷路の外側を移動先として選ぶことはできない。
記号

意味.

常に入ることができるマス。

#

常に入ることができないマス。

数字：0, 1,…, 9

アイテムがあるマス。数字がアイテムの番号を表す。常に入ることができる。

大文字：A, B,…, J

対応するアイテムを持っていないときだけ入ることができるマス。
A, B,…, J がそれぞれ 0, 1,…, 9 に対応する。

小文字：a, b,…, j

対応するアイテムを持っているときだけ入ることができるマス。
a, b,…, j がそれぞれ 0, 1,…, 9 に対応する。

S

スタート地点のマス。常に入ることができる。

T

ゴール地点のマス。常に入ることができる。

ゴール地点に到達しても、すべてのアイテムを持っていないとゲームの目的を達成することはできない。
また、アイテムがあるマスに入った場合は、回収するかどうかを選ぶことができる。回収したアイテムはマスから消える。一度回収したアイテムは持ち続けなければならない。

課題
迷路の状態と、２つのアイテムを回収した順序によって得られる得点の表が与えられたとき、全てのアイテムを回収しゴール地点にたどり着くための、最小の移動回数とそのときに得られる最大の得点を出力するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
W H
row1
row2
:
rowH
s00 s01 … s09
s10 s11 … s19:

s90 s91 … s99
１行目に迷路の横方向と縦方向のマスの数W(4≦W≦1000)とH(4≦H≦1000)が与えられる。続くH行に、迷路の上からi行目に並んだマスの情報rowiが与えられる。rowiは、それぞれ長さがWであり、上の表で定められた記号からなる文字列である。１文字が１つのマスを表す。続く10行にアイテムを回収した順序によって得られる得点の表が与えられる。sij(0≦sij≦100)は、アイテムiの次に回収したアイテムがアイテムjであるときに得られる得点を表す整数である。ただし、sii = 0である。
マスの情報は以下の条件を満たす。
 S, T, 0, 1, …, 9 は迷路の中にそれぞれちょうど１つ存在する。
 A, B, …, J, a, b, …, jは迷路の中にそれぞれ高々１つ存在する。

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

出力最小の移動回数とそのときに得られる最大の得点を、空白区切りで１行に出力する。ただし、ゲームの目的を達成することができない場合は「-1」をひとつだけ１行に出力する。

入出力例
入力例１
12 5
.....S......
.abcdefghij.
.0123456789.
.ABCDEFGHIJ.
.....T......
0 1 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0

出力例１26 2

入力例２4 50jSB
###.
1234
5678
9..T0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

出力例２31 0入力例３7 7
1.3#8.0#.###.##.###.#
5..S..9#.#T#.##.###.#
4.2#6.7
0 0 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 00 0 0 0 7 0 0 0 0 00 2 0 0 0 0 0 0 0 00 0 3 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 8 0 0 0
2 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

出力例３53 19

入力例４5 6..S..
#####01234
56789
#####
..T..
0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0

出力例４-1

問題１０
問題１０ 石遊び（１２点）

幸四郎くんと浮子さんは白と黒の石を使った遊びをしている。この遊びは以下のような内容である。
１．遊びの開始時に、いくつかの場を作り、それぞれの場に白石と黒石をそれぞれ１つ以上置く。
２．幸四郎くんと浮子さんは交互に、場をどれか選び、その場に対して以下の中から一つを選んで行動する。
(ア) 白石を場から１つ取り除く。
(イ) 白石の数を超えない個数だけ、黒石を１つ以上場から取り除く。
(ウ) 黒石を１つ白石と交換する。このとき白石は石入れから持ってくる。石入れには十分な数の白石が入っているものとする。
３．先に２ができなくなった人が負け。
幸四郎くんが先攻、浮子さんが後攻で何度かこの遊びをしているが、遊びの開始時に勝敗が決まるようである。そこで、幸四郎くんと浮子さんが最適な行動をとったときの、勝者を計算してみることにした。

課題
遊びの開始時にそれぞれの場に置かれる白石と黒石の数が与えられたとき、幸四郎くんと浮子さんが最適な行動をとったときの勝者を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N
w1 b1
w2 b2
:
wN bN
１行目に場の数N(1≦N≦10000)が与えられる。続くN行には、それぞれの場の白石の数wiと黒石の数bi (1≦wi,bi≦100)が与えられる。

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

出力
幸四郎くんが勝つ場合は「0」を、浮子さんが勝つ場合は「1」を、１行に出力する。

入出力例
入力例１424 99
15 68
12 9095 79

出力例１0

入力例２32 4694 846 57

出力例２1

問題１１問題１１ Ｋ番目の排他的論理和
Ｋ番目の排他的論理和（１２点）

0 または 1 からなる２つの数 x、y に対する排他的論理和とは、x と y が同じであるとき 0、異なるとき1 となる演算である。この演算を⊕で表現する。定義から、0 ⊕ 0 = 0, 0 ⊕ 1 = 1, 1 ⊕ 0 = 1, 1 ⊕
1 = 0 である。
２つの非負整数 X、Y に対するビットごとの排他的論理和とは、X と Y を２進数で表現したとき、各桁について排他的論理和をとりそれを数とする演算のことである。この演算も⊕で表現する。たとえば、１０進数で 3 ⊕ 5 は、２進数で 011 ⊕ 101 なので、ビットごとの排他的論理和をとると２進数で 110 となり、１０進数では 6 になる。
非負整数である要素 z1, z2, …, zM からなる要素数 M の数列 Z に対する、ビットごとの排他的論理和を以下のように定義する。
・ v0 = 0, vi = vi-1 ⊕ zi (1 ≤ i ≤ M) とする。
・ 数列 Z に対するビットごとの排他的論理和を vM と定める。
あなたは N 個の非負整数からなる数列 A と、たくさんの紙、ひとつの空箱を持っている。あなたは、1 ≤L ≤ R ≤ N を満たす全ての整数の組(L, R)について、以下の操作を１度ずつ行った。
① A の L 番目から R 番目の要素からなる数列に対し、ビットごとの排他的論理和を求める。その数をB とする。
② まだ箱に入れていない紙を１枚選び、その紙に B を書き、箱に入れる。
紙は十分にあるので、操作の途中で足りなくなることはないものとする。あなたは、正の整数 K を選び、箱の中の紙に書かれた数を降順に並べたときの K 番目の数を求めることにした。

課題
数列が与えられたとき、すべての操作の終了後、箱の中の紙に書かれた数を降順に並べたときの K 番目の数を計算するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N K
a1 a2 … aN
１行目に、数列の要素数N(1≦N≦105)、選んだ数K(1≦K≦N(N+1)/2)が整数で与えられる。２行目に、数列の要素ai(0≦ai≦106)が与えられる。

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

出力
箱の中の紙に書かれた数を降順に並べたときの K 番目の数を 1 行に出力する。

入出力例
入力例１出力例１3 32
1 2 3
操作の後、箱の中の紙に書かれた数を降順に並べると以下のようになる。
・ 3,3,2,1,1,0
3番目の数は2であるため、2を出力する。
入力例２7 11 0 1 0 1 0 1

出力例２1入力例 35 101 2 4 8 16

出力例３7問題１２問題１２ 街道建設

（１２点）

1 から N までの番号がついた N 個の都市が合併し、ヅイア王国が建国された。ヅイア王国の交通大臣に任命されたあなたは、都市間の街道建設の仕事を与えられた。
あなたは計画を立てるために、各都市を地図上の一点だと考えることにした。そうすると、都市 i は地図上の座標(xi, yi) に存在するとみなせることがわかった。
都市 u と都市 v を結ぶ街道を建設するには、|xu - xv|と|yu - yv|のうち大きい方（２つが同じ値ならその値）のコストがかかる。ただし、|A|は A の絶対値を表す。相異なる任意の都市の間を１本以上の街道を使って移動できるように建設するとき、かかるコストの合計の最小値を求めたい。

課題
都市の個数と座標を入力とし、街道建設にかかるコストの合計の最小値を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
Nx1 y1x2 y2:xN yN
１行目に、都市の数N(2≦N≦105)が与えられる。続くN行に、i番目の都市の座標xi,yi(0≦xi,yi≦109)が整数で与えられる。ただし、同じ座標をもつ点は与えられない(i≠jについて、xi≠xjまたはyi≠yj）。

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

出力
街道建設にかかるコストの合計の最小値を１行に出力する。

入出力例
入力例１31 23 410 1

出力例１9

都市1と都市2を結ぶ街道をコスト2で建設でき、都市2と都市3を結ぶ街道をコスト7で建設できるので、コストの合計は9となり、これが最小である。
入力例２31 23 43 2

出力例２4

入力例３57 41
10 099 2771 87
14 25

出力例３163