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

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

問題１
問題１ ケーキのケーキの価格（２点）

２０１９年１０月１日から消費税引き上げと同時に軽減税率制度が導入されました。ヤエちゃんの大好
きなケーキを店内で食べると１０％、持ち帰ると８％の税率が適用されます。ヤエちゃんは、ケーキを店内で食べる場合と持ち帰る場合とで支払う金額がいくら違うか興味が湧いてきました。

課題
ケーキの税抜き価格が与えられたとき、店内で食べる場合に支払う金額が、持ち帰る場合に支払う金額と比べて、いくら高いかを計算するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
p
１行にケーキの税抜き価格p(50≦p≦5,000)が与えられる。ただし、pは50の倍数である。

出力
ケーキを店内で食べるときと持ち帰るときの差額を１行に出力する。

入出力例
入力例１50出力例１1入力例２1500

出力例２30

入力例３5000

出力例３100

問題２問題２ 角度の変換（３点）

通常、角度は度という単位で表しますが、１度より小さい角度まで表したいときには、分や秒という単位を使います。1 度を分で表すと 60 分、１分を秒で表すと 60 秒になります。たとえば、10.52 度を秒で表すと 37,872 秒になり、度分秒で表すと 10 度 31 分 12 秒になります。

課題
角度が秒で与えられたとき、それらを度分秒に変換するプログラムを作成せよ。ただし、度は 0 以上の整数、分と秒は 0 から 59 までの整数とする。

入力
入力は以下の形式で与えられる。
d
１行に秒で表した角度d(0≦d≦648,000)が整数で与えられる。

出力
度分秒で表した角度の度、分、秒を、空白区切りで１行に出力する。

入出力例
入力例１37872

出力例１10 31 12

入力例２503784

出力例２139 56 24入力例３0

出力例３0 0 0

問題３問題３ ホットケーキ（４点）

あなたの家では家族が順番に朝食の準備をします。今日はあなたがホットケーキを作ります。ホットケーキは、１分で片面が焼きあがります。両面焼いたらできあがりです。
あなたはフライパンを１つ持っています。このフライパンでは、一度にホットケーキを３枚まで、片面だけ焼くことができます。

課題
ホットケーキの枚数が与えられたとき、すべてのホットケーキを作るために必要な最短の時間（分）を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N
１行にホットケーキの枚数N (1≦N≦1,000)が整数で与えられる。

出力
すべてのホットケーキを作るために必要な最短の時間を１行に出力する。

入出力例
入力例１
3

出力例１
2

入力例２
4

出力例２
3

入力例２で焼くホットケーキをそれぞれＡ、Ｂ、Ｃ、Ｄとする。最初にＡ、Ｂ、Ｃの表面を同時に焼く。
次に、Ａ、Ｂの裏面とＤの表面を同時に焼く。最後にＣ、Ｄの裏面を同時に焼くと３分で焼きあがる。

問題４ 最小の MAW（５点）

文字列 S の連続部分文字列とは、S の先頭と末尾からそれぞれ長さ０以上の連続した文字列を削除したもののことです（ただし、S の文字をすべて削除したものは除きます）。たとえば、文字列 abc の連続部分文字列は、a, ab, abc, b, bc, c の６個です。
文字列 S と T があるとき、T が以下の条件を満たすなら、T は S の最小欠失語（minimal absent word, これ以降はＭＡＷと書く）といいます。


T の長さは２以上。
T は S の連続部分文字列ではない。
T の連続部分文字列で T でないものはすべて、S の連続部分文字列である。

たとえば、文字列 S が aabb のとき、S のＭＡＷは文字列 aaa, ba, bbb です。

課題
文字列が与えられる。その文字列のＭＡＷで、辞書式順序（英和辞書で単語が並んでいる順番）で最小の文字列を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
Nstr
１行目に文字列の長さ N(3≦N≦400,000)が与えられる。２行目に英小文字からなる長さ N の文字列が与えられる。

出力
辞書式順序で最小のＭＡＷを１行に出力する。

入出力例
入力例１4aabb

出力例１aaa

入力例２4tree

出力例２eee問題５問題５ スロットマシン（５点）

アイヅ工業は新しいスロットマシンを開発しました。このスロットマシンは、０から９までの数字を横に W 個、縦に H 個表示します。横方向の数字の並びを行、縦方向の数字の並びを列と呼びます。W=5、H=3 のときに表示される数字の例を図１に示します。
１列 目

２列 目

３列 目

４列 目

５列 目

１行目

03077

２行目

50333

３行目

35743

図１. スロットマシンに表示される数字の例（W=5, H=3）

このスロットマシンでは、表示された数字に応じて得点を得られます。得点は以下のように計算されます。１列目から W 列目すべてに特定の同じ数字が現れるとき（行の一致は問わない）、その数字を線で結んで１本の折れ線を作ることで得点（その数字）を得ることができます。もし、形状が異なる複数の折れ線を作ることができる場合、すべての折れ線の得点の総和がスロットマシンで得られる得点になります。折れ線が一つも作れなければ、得点は０点になります。
図１に表示された数字で得られる得点を図２で考えます。
１列 目

２列 目

３列 目

４列 目

５列 目

１列 目

２列 目

３列 目

４列 目

５列 目

１行目

0

30

77

１行目

0

30

77

２行目

50

333

２行目

50

333

３行目

35743

３行目

3574

3

3点＋3点

＝ 6点

図２. スロットマシンの得点の計算例

図１の例では３がどの列にも現れるので、３を結んで折れ線が作れます。５列目に３が２つ現れるので、図２に示すように２種類の折れ線が作れます。各折れ線の得点が３点なので、スロットマシンで得られる得点は６点になります。

課題
スロットマシンに表示されている数字が与えられたとき、得られる得点を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
W H
row1
row2
:
rowH
１行目に横方向の数字の個数W (1≦W≦1,000)と縦方向の数字の個数H(1≦H≦1,000)が与えられる。続
くH行に、i行目に表示されるW個の数字の並びrowiが与えられる。rowiは0から9の数字からなる、長さWの列である。

出力得られる得点を 998,244,353 で割った余りを１行に出力する。

入出力例
入力例１5 3

出力例１603077
50333
35743
入力例２4 4335153353573

出力例２287350
入力例２では、3がどの列にも現れる折れ線が6本、5がどの列にも現れる折れ線が2本できる。よって、得点は 3×6 + 5×2 ＝ 28 となる。
入力例３12 5999999999999
999999999999
999999999999
999999999999
999999999999

出力例３200776919

問題６
問題６ はんぶんこ（７点）

双子の姉弟ヤエちゃんとジョー君は、お母さんからおやつに煎餅を１枚もらいました。その煎餅は凸多角形の形をしていて、割りやすいようにすべての対角線上に切れ込みが入っています。
２人は煎餅をはんぶんこにしたいのですが、力がないので、１本の対角線の両側を手ではさんで割るしかありません。姉弟は、どの対角線に沿って煎餅を２つに割ったら、はんぶんこに一番近くなって、２人の取り分の差が最も小さくなるか考え始めました。

課題
凸多角形によって表される煎餅の形についての情報が与えられたとき、２人の取り分の差の最小値を求めるプログラムを作成せよ。ただし、２人の取り分の差は、１本の対角線に沿って煎餅を２つに分割したときの、それらの面積の差の絶対値で表される。

入力
入力は以下の形式で与えられる。
Nx1 y1x2 y2:xN yN
１行目に凸多角形の頂点の数N(4≦N≦60,000)が与えられる。続くN行に凸多角形の頂点の座標xi,yi(0≦xi,yi≦100,000,000)が整数で与えられる。凸多角形の頂点は、隣り合った頂点を反時計回りに訪問するような順番で与えられる。

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

出力
２人の取り分の差の最小値を実数で１行に出力する。ただし、誤差がプラスマイナス 0.0001 を超えてはならない。この条件を満たせば小数点以下は何桁表示してもよい。

入出力例
入力例１40 01 01 10 1

出力例１0.0

入力例２4出力例２0.50000 01 0
1 20 1

問題７
問題７ 旅館の客室番号（７点）

サカエさんとカナエさんは、旅館「イヅア屋」に宿泊しました。イヅア屋には受付から伸びた一本の長い廊下があり、その廊下に沿って客室が等間隔で一列に並んでいます。それぞれの客室には、受付に近い部屋から順番に、客室番号が小さい順に割り振られています。客室番号は 1 から始まり、重複はありません。しかし、日本では４と９は縁起の悪い数字とされているため、それらの数字をどの桁にも含まない、すべての正の整数が客室番号として使われています。
サカエさんとカナエさんは受付でそれぞれが宿泊する部屋の番号を教えてもらいました。二人は、お互いの部屋を行き来する予定なので、サカエさんの部屋からカナエさんの部屋まで、何部屋分移動しなければならないか知りたくなりました。

課題
イヅア屋の客室番号が２つ与えられる。片方の客室からもう片方の客室に移動するために必要な距離を計算するプログラムを作成せよ。このとき、１つ隣の部屋に移動する距離を１とする。

入力入力は以下の形式で与えられる。
p q
１行にサカエさんの客室番号pとカナエさんの客室番号q(1≦p＜q≦10100＝10の100乗)が与えられる。ただし、pとqはどの桁にも4と9を含まない整数である。

出力
片方の客室からもう片方の客室に移動するために必要な距離を出力する。

入出力例
入力例１5 12

出力例１6入力例２38 50

出力例２1入力例３1 10000000000

出力例３1073741823

問題８問題８ 壊れた出口（９点）

人気のゲーム「壊れた出口」は、最小の移動回数で迷路から脱出することを目指すパズルゲームです。
迷路は、N×M 個のマスからなり、各マスには行番号と列番号が割り当てられています。行番号が r、列番号が c のマスは(r, c)で表します。左上隅がマス(0, 0)、右下隅がマス(N-1, M-1)です。各マスには以下のいずれかの記号が割り当てられています。
.
E#地面出口壁

ゲームの各プレイで、あなたはプレイごとに指定されたマスから出発して出口を目指します。各出口へは壁以外のどのマスからもたどり着くことができます。あなたがいるマスの上下左右の隣接したマスが地面または出口であれば、そのマスに移動することができます。ただし、マスのない場所には移動することはできません。
迷路には２つ以上の出口が存在しますが、そのうちの一つが壊れています。どの出口が壊れているかは、プレイごとに指定されます。壊れていない出口にあなたがたどり着いたらプレイ終了です。出口が壊れていてもその出口のマスに移動することはできますが、プレイ終了にはなりません。

課題
１つの迷路と、各プレイの情報が与えられたとき、各プレイが終了するまでの最小移動回数を出力するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N M
row1
row2
:
rowN
P
sr1 sc1 br1 bc1sr2 sc2 br2 bc2:
srP scP brP bcP
１行目に迷路の大きさを表す２つの整数N(2≦N≦1,000)とM(2≦M≦1,000)が与えられる。続くN行に上からi番目に並んだマスの情報を表す文字列rowiが与えられる。rowiは長さMの文字列であり、j文字目がマス(i-1, j-1)の記号を表す。続く行にプレイの数P(1≦P≦100,000)が与えられる。続くP行に各プレイで指定される、出発点である地面のマス(sri,sci)、壊れている出口のマス(bri,bci)を表す整数sri,sci,bri,bci(0≦sri,bri＜N, 0≦sci,bci＜M)が与えられる。

出力
出力は P 行である。各プレイに対して最小移動回数を１行に出力する。

入出力例
入力例
4 5
.....
.#.#E..##.
.E...
3
0 0 3 11 2 3 11 2 1 4

出力例547

問題９ ロボットアーム（１０点）

PCK 工業では、新作のロボットアームを開発しています。このロボットアームの仕事は、１列に並んだ1 から N の番号が割り振られた N 個の部品を、番号が小さい順に並べ替えることです。
ロボットアームは 1 回の動作で３つの部品を選択し（隣り合っている必要はありません）、それらに対して以下の交換作業を行うことができます。


選んだ部品の番号が先頭から a, b, c のとき、これらの部品の位置を b, c, a または c, a, bの順番に入れ替える

たとえば、部品が 3 6 1 5 4 2 と並んでいて、ロボットアームが 6 5 4 の部品を選択した場合は、これらの位置を交換して 3 5 1 4 6 2 または 3 4 1 6 5 2 の順番に並べ替えることができます。

課題
部品の列が与えられる。これらを番号が小さい順に並べ替えるために必要な、ロボットアームの最小の操作回数を求めるプログラムを作成せよ。ただし、どのように操作を行っても番号が小さい順にできない場合は-1 を出力せよ。

入力
入力は以下の形式で与えられる。
Nh1 h2 ... hN
１行目に部品の数N (3≦N≦200,000)が与えられる。２行目に各部品の番号hi(1≦hi≦N)が与えられる。
ただし、すべての番号は異なる（i≠jならばhi≠hj）

出力最小の操作回数を１行に出力する。ただし、番号が小さい順に並べ替えることができない場合は-1 を 1行に出力する。

入出力例
入力例１62 3 4 1 6 5出力例１3入力例２42 3 4 1出力例２-1

問題１０ 柿の実

（１１点）
（１１点）

秋が深まり、今年も庭の柿の木に実がなりました。しかし、今年は天候不順だったので、なった実は３つだけでした。
柿の木の上から陽が射して、地面に柿の実の影ができました。１つの柿の実の影は円形で、太陽の位置によって３つの柿の実の影は重なり合ったり、離れたりします。

課題
３つの柿の実それぞれの影に関する情報が与えられたとき、影の面積を求めるプログラムを作成せよ。
ただし、３つの柿の実の影はどれも同じ半径である。

入力
入力は以下の形式で与えられる。
rx1 y1x2 y2x3 y3
入力は４行である。１行目に３つの柿の実の影を表す円の半径(1≦r≦500)が整数で与えられる。続く
３行に i 番目の円の中心の座標 xi,yi(0≦xi,yi≦500)が整数で与えられる。ただし、すべての円の中心の座標は異なる（i≠j なら、xi≠xj または yi≠yj）。

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

入出力例
入力例１20 02 0

出力例１32.7856330486

1 5
入力例２33 25 24 5

出力例２55.2157319565

問題１１ 高速道路網の再編

（１１点）
（１１点）

ヅイア国の高速道路網は、都市(地点)とそれらを結ぶ道路から構成されています。この高速道路網は以下の条件を満たすように建設されています。


1 から N の番号が割り当てられた N 個の都市（地点）がある。
道路は一方通行で、ある地点とある地点を直接結ぶ道路は多くても２つしかない（２つあるときは互いに逆向き）。
どの地点からも、他のすべての地点へ必ずたどり着くことができる。

高速道路網を維持するには、道路ごとにコストがかかります。財政難を避けるため、ヅイア国はいくつかの道路を廃止することに決め、あなたを担当者に指名しました。あなたは、上の条件は変えずに、高速道路網全体の維持コストが最小になるように再編しなければなりません。

課題
地点の数と道路の情報が与えられたとき、再編後の高速道路網全体の維持コストの最小値を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N M
u1 v1 c1
u2 v2 c2:
uM vM cM
１行目に地点の数 N(2≦N≦13)と道路の数 M(N≦M≦N×(N-1))が与えられる。続く M 行に i 番目の道路の出発地点 ui と到着地点 vi(1≦ui≠vi≦N)、維持コスト ci(1≦ci≦10,000)が与えられる。

出力
再編後の高速道路網全体の維持コストの最小値を１行に出力する。

入出力例
入力例１3 41 2 22 3 3
1 3 13 1 1

出力例１6

入力例２5 8

出力例２241 2 7
1 5 22 1 8
2 3 3
3 4 54 5 8
5 1 55 2 1

問題１２
問題１２ 交換と転倒数（１２点）１２点）

長さ N の数列 a1, a2, ... aN の転倒数とは、1≦i＜j≦N と ai＞aj を満たす要素の組(ai, aj)の総数です。
数列の転倒数は、初等的整列アルゴリズムであるバブルソートの交換回数としても知られています。
この問題では、数列中の２つの要素の値を交換し、交換後の数列の転倒数を出力するという操作を行います。

課題
数列と、複数回の操作に関する情報が与えられたとき、各操作の結果を出力するプログラムを作成せよ。
ただし、２回目以降の各操作は、その直前の操作の結果得られた数列に対して行うものとする。

入力
入力は以下の形式で与えられる。
Na1 a2 ... aN
Mb1 e1b2 e2:
bM eM
１行目に数列の要素数N(2≦N≦500,000)が与えられる。２行目に数列のi番目の要素の値ai(0≦ai≦1,000,000,000) が与えられる。ただし、すべての要素の値は異なる（i≠jならばai≠aj）。続く行に操作の数M(1≦M≦30,000)が与えられる。続くM行に、i番目の操作の情報を表す整数の組biとei(1≦bi＜ei≦N)が与えられる。biとeiは、i番目の操作で交換されるのが数列のbi番目とei番目の要素の値であることを示す。

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

出力
出力は M 行である。各操作に対して、操作の結果を１行に出力する。

入出力例
入力例
64 6 5 3 1 2出力例
9832 43 61 53問題１３ 山小屋スタンプラリー（１４点）

あなたは N 棟の山小屋と各山小屋をつなぐ道を管理しています。山小屋にはそれぞれ 1 から N までの番号がついています。道は全部で N-1 本あります。どの道も双方向に移動可能です。また、どの山小屋からでも、いくつかの道を通っていけば他の山小屋に到達できます。
あなたは、山小屋の利用客が楽しめるように、すべての山小屋にスタンプを設置して、スタンプラリーを始めることにしました。このスタンプラリーのルールは以下の通りです。


利用客は山小屋をいくつか選ぶ。このとき、選ぶことができる数は２棟から N 棟までである。
その後、選んだ山小屋のどれか１つに移動し、そこからスタンプラリーを開始する。
スタンプラリーの間、利用客は道を通って山小屋の間を移動する。移動中に通った山小屋すべてを訪れ、そこでスタンプを押す。
既にスタンプを押した山小屋を訪れると、その時点でスタンプラリーは失敗となり終了する。
選んだ山小屋をすべて訪れた時点で、スタンプラリーが成功して景品がもらえる。

スタンプラリーを成功させるため、利用客は山小屋を巡るルートを正しく選ぶ必要があります。しかし、山小屋の選び方によっては、どのようにルートを選んでも成功できなくなってしまいます。そこで、スタンプラリーを成功させることができるような山小屋の選び方だけを認めることにしました。そのような山小屋の選び方はどれくらいあるでしょうか。

課題
山小屋の数と、山小屋同士を直接つなぐ道の情報が与えられる。山小屋を２棟から N 棟までそれぞれ選ぶとき、選んだ山小屋の数ごとに、スタンプラリーを成功させることができるような山小屋の選び方の数を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N
s1 t1
s2 t2
:
sN-1 tN-1
１行目に山小屋の数 N(2≦N≦200,000)が与えられる。続く N-1 行に、２つの山小屋を直接つなぐ道の情報が与えられる。si と ti (1≦si＜ti≦N)は i 番目の道がつなぐ２つの山小屋の番号である。ただし、どの２つの山小屋についても、それらを直接つなぐ道は１本以下とする。

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

出力
出力は N-1 行である。i 行目に、山小屋を i+1 棟選んだ場合の、スタンプラリーを成功させることができるような山小屋の選び方の数を、998,244,353 で割った余りを出力する。

入出力例
入力例
51 22 33 43 5

出力例10820