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

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

問題１
問題１ 目盛りのないストップウォッチ
目盛りのないストップウォッチ
右の図のようなストップウォッチがあります。このストップウォッチには０を示す目印が一つあるだけで、目盛りがありません。起動した瞬間、針は目印を指し、そこから針は軸を中心に一定の割合で時計回りに回転します。目盛りがないので、起動からの経過時間を直接読み取ることはできません。その代わり、針が目印から時計回りに a 度回ったときの経過時間が t 秒であることがわかっています。ただし、a は 360 度未満とします。

（２点）
０

目印
針
軸課題
角度 a と経過時間 t が与えられたとき、ストップウォッチ起動後に読み取った針の角度 r が表す経過時間を求めるプログラムを作成せよ。ただし、針が１周していないことはわかっているものとする。

入力
入力は以下の形式で与えられる。
a t r
１行に角度a(1≦a≦359)と角度aのときの経過時間t(1≦t≦1,000)、読み取った角度r(0≦r≦359)がすべて整数で与えられる。ただし、aとrの単位は度、tの単位は秒とする。

出力読み取った針の角度が表す経過時間を秒で１行に実数で出力する。ただし、誤差がプラスマイナス 0.001を超えてはならない。この条件を満たせば小数点以下何桁表示してもよい。

入出力例
入力例１180 120 90

出力例１60.0

入力例２90 100 120

出力例２133.333333※ C++のiostreamのcoutを使う場合、coutを行う前に以下の関数を呼び出せば、常に小数点以下の桁までを出力させることができる。
std::cout.setf(std::ios_base::fixed,std::ios_base::floatfield);問題２問題２ ガソリンスタンド（４点）

白虎サービスエリアのガソリンスタンドには、１から N の番号が割り当てられた N 個のレーンがあります。各レーンの先頭の車が給油を行うことができます。
ガソリンスタンドに入場した車は、並んでいる車が最も少ないレーンを選び列の末尾に並びます。そのようなレーンが複数ある場合は、番号が最も小さいレーンを選びます。給油が終わるとその車はレーンから出ていき、その後ろの車が給油を行います。一度レーンを選んだら、他のレーンに移ることはできません。また、レーンに並んでいる車の順番が変わることはありません。

課題
レーンの数、入場した車と給油が終了したレーンの情報が与えられたとき、給油が終了した車のナンバーを順番に出力するプログラムを作成せよ。入場の情報はスタンドに入ってくる車のナンバー、給油終了の情報は先頭の車の給油が終了したレーン番号としてそれぞれ与えられる。ただし、最初はどのレーンにも車は並んでいないものとする。

入力
入力は以下の形式で与えられる。
N M
info1
info2
:

infoM
１行目にレーンの数N(1≦N≦10)と情報の数M(2≦M≦10,000)が与えられる。続くM行に各情報infoiが与えられる。各infoiは以下のいずれかの形式で与えられる。
0 laneまたは
1 car
最初の数字が0の場合、番号がlane(1≦lane≦N)であるレーンに並んでいる先頭の車の給油が終了したことを示す。最初の数字が1の場合、ナンバーがcar(1≦car≦9,999)である車がスタンドに入場したことを示す。
入力は以下の制約を満たす。
 ガソリンスタンドに入って来る車のナンバーは、全て異なる。
 最初の数字が0,1である情報は、それぞれ必ず１つ以上ある。
 車のいないレーンに対して、最初の数字が0である情報は与えられない。

出力
給油終了の情報ごとに、給油が終了した車のナンバーを 1 行に出力する。

入出力例
入力例
2 71 999
1 10000 21 1001
1 10020 10 1

出力例
10009991002

のり（５点）問題３問題３ 海苔

ヒバラ海の浜辺の集落では海苔の生産が盛んです。海苔はすべて長方形に成型されます。海苔を天日干しするときは、２枚の海苔を同じ敷物の上に乗せて、１枚目の上辺と２枚目の上辺が平行になるように置きます。アルバイトのゲンムさんは平行に置くことはできるのですが、まだ慣れていないため重なった部分ができてしまうことがあります。重なった部分は売り物にならないので、重なっていない部分の海苔の面積を求めておく必要があります。

課題
同じ敷物の上に置いた２枚の海苔それぞれの左下端の位置と幅と高さが与えられたとき、重なっていない部分の海苔の面積を出力するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
x1 y1 w1 h1
x2 y2 w2 h2
１行目に１枚目の海苔の左下端の座標x1,y1(0≦x1,y1≦1,000)と幅と高さw1,h1(1≦w1,h1≦1,000)が与えられる。２行目に２枚目の海苔の左下端の座標x2,y2(0≦x2,y2≦1,000)と幅と高さw2,h2(1≦w2,h2≦1,000)が与えられる。入力はすべて整数で与えられる。

出力重なっていない部分の海苔の面積を整数で１行に出力する。

入出力例
入力例１0 0 4 52 2 3 6

出力例１26

入力例２1 2 2 12 0 2 2

出力例２6

入力例３0 0 1 10 0 1 1

出力例３0

問題４問題４ へびの脱皮（５点）

セアブリ高原で発見された新種のへびは、頭から尾にかけて１列に並んだマル（o）xxoooxxxooxとバツ（x）からなる模様が特徴です。右の図に例を示しますが、へびの模様は個体により様々です。
図: へびの例
このへびは脱皮のときに、２つのマルが並んだ部分の間すべてが伸びることで成長します。新たに加わった箇所にはマル、バツ、マルが並んだ模様が付きます。
たとえば、長さ３のへび ooo が１回脱皮すると、左から 1 番目と２番目、２番目と３番目のマルの間にマル、バツ、マルが並んだ模様が加わるので、脱皮後のへびは ooxoooxoo となります（下線部が新たに加わった箇所です）。もう一回脱皮すると ooxooxooxoooxooxooxoo となり、へびの長さは２１になります。
このへびの生態を研究しているあなたは、このへびが脱皮を繰り返したら、とてつもない長さになってしまうかもしれないと危惧しています。

課題
へびの模様と脱皮の回数が与えられたとき、この回数だけ脱皮した後のへびの長さを求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
L Nsnake
１行目に脱皮する前の蛇の長さL(1≦L≦100)と脱皮の回数N(1≦N≦50)が与えられる。続く１行に脱皮する前のへびの模様を表す長さLの文字列snakeが与えられる。ただしsnakeは英小文字xとoからなる。

出力
へびの長さを１行に出力する。

入出力例
入力例１3 2ooo

出力例１21

入力例２3 4xoo

出力例２48

入力例３13 30xooxoooxxxoox

出力例３12884901889

問題５問題５ デジットＫ（８点）

アイヅ赤べこ店では、デジットＫと呼ばれるユニークな「くじ」を販売しています。各くじには、左から右へ向かって 1 列に N 個の数字が並んでいます。
ただし、書かれているのは１から９までの数字です。
くじの購入者は、これらの数字から K 個の数字を消去し、残った N-K 個の数字を左から順番に並べてできる数をポイントとして獲得することができます。たとえば K=3 のとき、くじに 1414213 と書かれていれば、左から 1、1、2 を選択して消去することで 4413 ポイントを獲得することができます。

課題
数字の列と整数 K が与えられたとき、獲得できるポイントの最大値を出力するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N K
a1 a2 … aN
１行目に数字の数N(1≦N≦200,000)と整数K(0≦K＜N)が与えられる。２行目にくじに書かれているN個の数ai(1≦ai≦9)が与えられる。

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

出力ポイントの最大値を１行に出力する。

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

出力例１4423

入力例２4 11 1 9 9出力例２199問題６問題６ ２つの多角形（８点）

ヤエさんは３本以上の真っすぐな棒を繋げて多角形を作り、恋人のジョウ君にプレゼントすることにしました。棒はそれらの端点でのみ繋げることができます。端点はすべて同じ平面上に置きます。一つの接合点で繋がる棒は２本だけで、それらがなす角度は自由に決めることができます。
ヤエさんは、自分が持っている棒をすべて使って大きさが同じくらいの２つの多角形を作ろうとしています。

課題
与えられたすべての棒を使って、２つの多角形を、それらの周囲の長さの差の絶対値が最小となるように作る。各棒の長さが与えられたとき、２つの多角形の周囲の長さの差の絶対値を求めるプログラムを作成せよ。２つの多角形を作成できない場合はそのことを報告せよ。ただし、長さが a1≦a2≦…≦am である m(m≧3)本の棒で、am＜a1+a2+…+am-1 を満たすとき、これら m 本の棒でひとつの多角形を作成できるものとする。

入力
入力は以下の形式で与えられる。
Na1 a2 … aN
１行目に棒の数N(6≦N≦40)が与えられる。２行目に各棒の長さai(1≦ai≦100)が与えられる。

出力与えられたすべての棒を使って２つの多角形を作れる場合は、長さの差の絶対値の最小値を１行に出力する。２つの多角形を作れない場合は「-1」を１行に出力する。

入出力例
入力例１62 2 3 2 2 2出力例１1入力例２72 2 3 2 2 2 1出力例２0入力例３61 1 1 1 2 4出力例３-1

問題７問題７ コンピュータシステムの不具合（１０点）

あなたは世界最高性能のコンピュータシステム「那由多（なゆた）」を設計している。しかし、このシステムのプロトタイプの実装中に、命令列がある条件を満たすとシステムが停止するという不具合が見つかった。
このシステムは、長さ N の命令列をプログラムとして与えることで動作する。命令列の中の m 番目の命
令を数 Xm で表したとき、不具合が起こる条件は、ある整数 i,j(2≦i＜j≦N)に対して Xi + Xj-1 = Xj + Xi-1となる命令のパターンが命令列に存在することであると判明した。
あなたはこの不具合がどの程度の影響になるのかを調べるため、ある長さで作ることができる命令列のうち、何種類の命令列が不具合を起こすかを調べることにした。

課題
長さ N の命令列のうち、不具合が起こる命令列が何通りあるかを求めるプログラムを作成せよ。
ただし、命令は 1 以上 K 以下の整数で表せることとする。答えは与えられた素数 M で割った余りとする。

入力
入力は以下の形式で与えられる。
N K M１行に、命令列の長さN(3≦N≦100,000)、命令の種類の数K(1≦K≦10)、素数M(100,000,007≦M≦1,000,000,007)が与えられる。

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

出力不具合を起こす命令列の数を M で割った余りを出力する。

入出力例
入力例１3 2 100000007

出力例１2

命令列を(X1,X2,X3)のように表すと、考えられる命令列は(1,1,1)、(1,1,2)、(1,2,1)、(1,2,2)、(2,1,1)、(2,1,2)、(2,2,1)、(2,2,2)の８通り。このうち、不具合が起こる命令列は(1,1,1)、(2,2,2)の２通り。
入力例２9 10 100000037

出力例２66631256

不具合が起こる命令列は866631552通りあるが、その数を素数100000037で割った余りが出力となる。

問題８問題８ 決まりごとの多いジム（１０点）

イヅア村のスポーツジムには１から N までの番号が付いた N 台のトレーニング機器があります。トレー
ニング機器を１回利用するには、その機器の番号が書かれたチケットが１枚必要です。トレーニング機
器を１回利用したときの消費カロリーは、機器ごとに決まっています。
このスポーツジムのチケットを何枚かもらったアツシ君は、運動不足解消のためにジムに行きました。
このジムでは、利用者が運動をやりすぎて体を痛めないように、機器の利用回数にルールがあります。
たとえば、「２番の機器は３番の機器よりも５回以上多く使ってはいけません」というようなルールです。機器を使う人は、ルールを守って機器を利用しなければなりません。
アツシ君は、もらったチケットを使って、ルールで許される範囲でなるべく多くのカロリーを消費したいと思っています。

課題
もらったチケットとそれぞれの機器の情報が与えられたとき、ルールを守ったときの消費カロリーの最大値を求めるプログラムを作成しなさい。

入力
入力は以下の形式で与えられる。
N R
t1 e1
t2 e2
:
tN eN
a1 b1 c1
a2 b2 c2:
aR bR cR
１行目にトレーニング機器の台数N(1≦N≦100,000)とルールの数R(0≦R≦100,000)が与えられる。続く
N行に、i番の機器について、アツシ君がもらったチケットの枚数ti(1≦ti≦200,000)とその機器を使ったときの消費カロリーei(0≦ei≦100,000)が与えられる。続くR行に、「ai番の機器はbi番の機器よりもci回以上多く使ってはいけません」というルールを表す数ai(1≦ai≦N)、bi(1≦bi≦N)、ci(1≦ci≦100,000)が与えられる。
入力は以下の制約を満たす。
 同じ機器のペアに対するルールは１度しか与えられない(i≠jならai≠ajまたはbi≠bj)。
 同じ機器自身に対するルールは与えられない(ai≠bi)。

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

出力
消費カロリーの最大値を１行に出力する。

入出力例
入力例１3 25 110 46 22 1 33 2 1

出力例１45

もらったチケットを使って、ルールを守って使える各機器の最大の回数は、１番が５回、２番が７回、３番が６回なので、消費カロリーの最大値は５×１＋７×４＋６×２＝４５となる。
入力例２4 55 16 22 37 1
1 2 42 1 3
1 3 2
3 2 3
3 4 2

出力例２26

入力例３1 0200000 100000

出力例３20000000000

問題９問題９ 山へ帰そう（１２点）

近年イズア国では、山から街に降りてくる動物に悩まされている。あなたは動物を山へ帰そうと研究を重ね、以下のことを明らかにした。
 それぞれの動物には固有の名前がついている。
 ２体の動物について、一方の動物の名前のどこかの位置に１文字を挿入すると、もう一方の動物の

名前と一致する場合、これらをペアにして山へ帰すことができる。
一度山へ帰った動物が、再び街に降りてくることはない。

あなたは、街に降りてきた動物を、この方法でどのくらい山へ帰すことができるかを計算することにした。

課題
街に降りてきた動物の名前が与えられたとき、この方法で最大いくつのペアを山へ帰すことができるかを求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N
str1
str2
:
strN
１行目に動物の数N(2≦N≦100,000)が与えられる。続くN行にi番目の動物の名前を表す文字列striが与えられる。ただしstriは英小文字と英大文字で構成された10文字以下の文字列である。また、すべての動物の名前は異なる(i≠jならstri≠strj)。

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

出力
山へ帰すことができる動物のペアの数の最大値を出力する。

入出力例
入力例１4aedb
aeb
ebCd
cdE

出力例１1

入力例２4bcD
bD
AbDbc

出力例２2

問題１０
問題１０ 化学物質
化学物質アルファ
物質アルファ

（１２点）

アイヅ製薬では日々化学物質の研究がなされています。いま研究をしているのは、1 番から N 番の分子が左端から右端へ直線状にならんだ構造をしている化学物質、コードネーム「アルファ」です。
アイヅ製薬の開発した技術を使えば、アルファを構成する分子の位置を入れ替えることができます。入れ替えは決まった手順でしか行うことができませんが、その手順の途中から始めて途中で終わることもできます。左端から a 番目と b 番目の分子を入れ替える操作を(a,b)と書くとします。たとえば、N=5で決まった手順が(1,3),(2,5),(4,3),(1,5)のとき、１番目の操作(1,3)から始めて３番目の操作(4,3)
で終わることも、２番目の操作(2,5)から始めて４番目の操作(1,5)で終わることもできます。
あなたは、アルファの分子の入れ替え手順の中の開始位置と終了位置を選んでシミュレーションを行い、入れ替え後の分子の状態を調べることにしました。

課題
アルファの分子の入れ替え手順が与えられる。シミュレーションを何度か行ったとき、各シミュレーションでの分子の位置について質問に答えるプログラムを作成せよ。質問は次の(1)または(2)の形をしている。
(1) 終了後に左端から i 番目に位置している分子は、最初は何番目に位置していたか。
(2) 最初に i 番目に位置していた分子が終了後にどの位置に来ているか。
ただし、各シミュレーションは、アルファの初期状態（1 番から N 番の分子が左端から右端へ直線状にならんだ状態）から始めるものとする。

入力
入力は以下の形式で与えられる。
N K Q
a1 b1
a2 b2:
aK bK
query1
query2:
queryQ
１行目にアルファを構成する分子の数N(2≦N≦100,000)、入れ替え手順の長さK(1≦K≦100,000)、入れ替え後の分子の状態を調べる回数Q(1≦Q≦100,000)が与えられる。続くK行に入れ替え手順の中の各操
作ai,bi(1≦ai,bi≦N, ai≠bi)が与えられる。i番目の操作は、左端からai番目とbi番目の分子を入れ替える操作を表す。続くQ行に、入れ替え終了後の分子の状態を尋ねる質問が与えられる。各queryiは以下のいずれかの形式で与えられる。
1 s t xまたは
2 s t x最初の数字が1の場合、入れ替え手順の中の入れ替えをs番からt番(1≦s≦t≦K)まで行った後に、左側からx番目(1≦x≦N)の分子の番号が何番か尋ねる質問を表す。最初の数字が2の場合、入れ替え手順の中の入れ替えをs番からt番(1≦s≦t≦K)まで行った後に、x番(1≦x≦N)の分子が左から数えて何番目にあるか尋ねる質問を表す。

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

出力
各質問に対して、答えを１行に出力する。

入出力例
入力例
6 5 81 32 53 42 42 51 1 5 1
1 1 5 21 1 5 31 1 5 41 1 5 5
1 1 5 62 3 4 2
1 1 1 1

出力例
32451643

入れ替え手順は(1,3),(2,5),(3,4),(2,4),(2,5)である。
１番目から６番目の質問では、手順の１番目(s=1)から５番目(t=5)まですべて行った場合なので、入れ替え後の状態はすべて共通で以下のようになる。
初期状態 1 2 3 4 5 6(1,3)の後 3 2 1 4 5 6(2,5)の後 3 5 1 4 2 6(3,4)の後 3 5 4 1 2 6(2,4)の後 3 1 4 5 2 6(2,5)の後 3 2 4 5 1 6
７番目の質問ではs=3,t=4なので、入れ替え後の状態は以下のようになる。分子番号２番は左から数えて４番目にあるので、答えは４になる。
初期状態 1 2 3 4 5(3,4)の後 1 2 4 3 5(2,4)の後 1 3 4 2 5
８番目の質問ではs=1,t=1なので、入れ替え後の状態は以下のようになる。
初期状態 1 2 3 4 5(1,3)の後 3 2 1 4 5

問題１問題１１ 三角形の個数の和三角形の個数の和

（１２点）
１２点）

座標平面上の原点 O を左下、座標(W,H)にある点を右上とする長方形の領域が与えられています。この領域に含まれる、x 座標と y 座標がともに整数である点を３個以上含む点の集まりを考えます。このような点の集まりのすべての組み合わせの個数を N とし、点の集まりのそれぞれを D1、D2、…、DN で表したとき、D1、D2、…、DN のそれぞれに含まれる点を頂点とする三角形を考えます。
たとえば、右図のように W=H=1 のとき、点 O(0,0)、A(1,0)、B(1,1)、C(0,1)のうち、３個以上含む点の集まりは{O,A,B}、{O,A,C}、{O,B,C}、{A,B,C}、{O,A,B,C}の５つです。この例の場合、点の集まりのそれぞれに含まれる三角形は次のようになります。
 {O,A,B}に含まれる三角形は OAB のみ。
 {O,A,C}に含まれる三角形は OAC のみ。
 {O,B,C}に含まれる三角形は OBC のみ。
 {A,B,C}に含まれる三角形は ABC のみ。
 {O,A,B,C}に含まれる三角形は OAB、OAC、OBC、ABC の４個。

yC1

BO

A1x

この例からわかるように、同じ三角形が２つ以上の点の集まりに含まれる場合があります。たとえば、
三角形 OAB は点の集まり{O,A,B}にも{O,A,B,C}にも含まれます。

課題
W と H が与えられる。点の集まり D1、D2、…、DN それぞれに含まれる点を頂点とする三角形の個数を t1、t2、…、tN とするとき、三角形の個数の和 t1+t2+…+tN を計算するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
W H１行にWとH(1≦W,H≦1,000)が与えられる。

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

出力それぞれの点の集まりに含まれる三角形の個数の和を 1,000,000,007 で割った余りを１行に出力する。

入出力例
入力例１1 1

出力例１8

入力例２1 2

出力例２144

入力例３100 100

出力例３879128399

問題１２問題１２ 惑星ヤナイヅの資源（１２点）

人類はついに知的生命体の存在する惑星ヤナイヅを発見した。惑星ヤナイヅでは科学が進歩していたので、次第に我々との共同研究が盛んにおこなわれるようになった。
惑星ヤナイヅではベコという虫が重要な資源とみなされている。ベコは幼虫からふ化して成虫になる。
ベコの生息域ではベコの幼虫が群れて生息している群生がいくつもあり、そのような群生が一列に並んでいる。惑星ヤナイヅのバイオテクノロジーを使うと、群生に対して以下のような操作ができる。


指定した範囲のすべての群生に、同じ数の幼虫を追加する。
指定した範囲のすべての群生で、指定した数の幼虫を成虫にふ化させ、ふ化した幼虫の数の合計を求める。このとき、ふ化させる幼虫の数を一つだけ指定できる。

２つ目の操作では、指定した数よりも幼虫の数が少ない群生については、その群生にいるすべての幼虫をふ化させる。たとえば、群生１に幼虫が３匹、群生２に幼虫が２匹いる場合、群生１から２の範囲に対してふ化させる数３を指定すると、群生１からは３匹、群生２からは２匹を成虫にすることになる。
このときにふ化した幼虫の数の合計は５匹である。
今回の共同研究では、我々人類がベコの幼虫に対するこれらの操作のシミュレーションを担当することとなった。ここは我々の科学の力を示すときである。

課題
各群生に存在する幼虫の情報が与えられたとき、それらに対する操作をシミュレーションするプログラ
ムを作成せよ。

入力
入力は以下の形式で与えられる。
N
c1
c2:
cN
M
manip1manip2:manipM
１行目に群生の数N(1≦N≦100,000)が与えられる。続くN行に、各群生にいる幼虫の数ci(0≦ci≦100,000)が与えられる。

続く１行に、操作の数M(1≦M≦100,000)が与えられる。続くM行に操作の内容が与えられる。各操作の内容は次のいずれかである。
1 a b dまたは
2 a b d
先頭の数字が1のとき、指定した範囲aからb(1≦a≦b≦N)の群生に対して、幼虫をd匹(1≦d≦1,000)追加する。先頭の数字が2のとき、指定した範囲aからb(1≦a≦b≦N)の群生に対して、幼虫をd匹(1≦d≦1,000)だけ成虫にふ化させる操作を表す。このとき、実際にふ化した幼虫の合計を出力する。また、先頭の数字が2である操作は必ずひとつ以上与えられるものとする。

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

出力
幼虫をふ化させる操作ごとに、実際にふ化した幼虫の合計を１行に出力する。

入出力例
入力例
312332 1 3 21 1 2 5
2 2 3 3

出力例54