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

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

問題１

キャンディの分配（１点）

ヤエちゃんは、お母さんからもらったキャンディを友達と分けようとしています。ヤエちゃんと友達それぞれが同じ数のキャンディを受け取り、かつ、受け取る数が最も多くなるように分けるとき、キャンディはいくつ余るでしょうか？

課題
キャンディの数とキャンディを分けあう友達の人数が与えられる。上述の通りにキャンディを分けたとき、余ったキャンディの数を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝐴𝑁
１行にキャンディの数𝐴(1 ≤ 𝐴 ≤ 1,000)と友達の人数𝑁(1 ≤ 𝑁 ≤ 1,000)が与えられる。

出力余ったキャンディの数を１行に出力する。

入出力例
入力例１5 1出力例１15個のキャンディをヤエちゃんと友達1人の合計2人で分けると1個余る。
入力例２10 10

出力例２1010個のキャンディをヤエちゃんと友達10人の合計11人で分けようとしたとき、みんなが同じ数のキャンディがもらえるように分けるなら、誰もキャンディをもらえないので10個余る。

参考C, C++, Javaには、余りを計算する演算子として%演算子が用意されている。たとえば、5÷2の余りを計算するには 5%2と書けばよい。

問題２

的当ての判定（２点）

右の図のような頂点𝐴(0, 𝑑)、𝐵(𝑑, 0)、𝐶(0, −𝑑)、𝐷(−𝑑, 0)で囲まれた正方形の的があります。この的に向かって矢を投げ、正方形の内部か辺の上に刺されば矢が的に当たったと判定されて賞品がもらえます。
矢が点𝑃(𝑥, 𝑦)に刺さったとき、矢が的に当たったかどうかは、以下のように判定できます。原点𝑂から𝑥軸に沿って座標(𝑥, 0)まで進んだ後、𝑦軸と平行に点𝑃まで進む道のりを考えます。この道のりに沿って長さを測り、それが𝑑以下かどうかを調べることで判定できます。
たとえば、𝑑 = 6で、矢が点(2,3)に刺さったとします。このとき、原点𝑂から点(2,0)まで𝑥軸に沿って2進み、そこから点(2,3)まで𝑦軸に平行に3進む道のりを考えます。この道のりの長さは2 + 3 = 5です。5 ≤𝑑 = 6なので、矢は的に当たったことがわかります。

課題
𝑑の値と矢が刺さった点𝑃の座標が与えられたとき、矢が的に当たったかどうかを判定するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑑𝑥𝑦
１行に正方形の大きさを示す数𝑑(1 ≤ 𝑑 ≤ 100,000 = 10 )、点𝑃の𝑥座標(−100,000 = −10 ≤ 𝑥 ≤100,000 = 10 )、点𝑃の𝑦座標(−100,000 = −10 ≤ 𝑦 ≤ 100,000 = 10 )が与えられる。

出力
矢が的に当たっていれば「Yes」、そうでなければ「No」を１行に出力する。

入出力例
入力例１5 3 2

出力例１Yes

入力例２5 0 -8

出力例２No参考
この問題で測った原点から点𝑃までの道のりの長さを、原点から点𝑃までのマンハッタン距離と呼びます。点𝛼(𝑥 , 𝑦 )から点𝛽(𝑥 , 𝑦 )までのマンハッタン距離は、𝑑 (𝛼, 𝛽) = |𝑥 − 𝑥 | + |𝑦 − 𝑦 |として計算します。記号|𝑥|は𝑥の絶対値を意味します。

問題３菌の祖先（３点）

ヒデヨ博士は、新しい菌が増殖する様子を観察しています。１つの菌から子が生まれるときは同時に２つの菌が生まれます。一度子を生んだ菌は、二度と子を生むことはありません。ヒデヨ博士は、菌の増殖の過程を記録するために菌に番号を付けることにしました。最初、菌が１つだけのときはその菌に番号１を付けます。博士は、番号𝑖の菌が子を生んだとき、それらに番号2𝑖と2𝑖 + 1を付ければ、すべての菌にそれぞれ異なる番号が付けられることに気づきました。この番号付けでは、菌１が２つの子を生んだらそれらの菌の番号は２と３、菌２が２つの子を生んだらそれらの菌の番号は４と５になります。
博士は、番号𝑏の菌から番号 1 の菌まで親子関係をさかのぼる順で、菌𝑏のすべての祖先を記録することにしました。たとえば、菌 5 は菌 2 の子で,菌 2 は菌 1 の子なので、菌 5 の祖先の記録は 5,2,1 となります。

課題
菌の番号が与えられたとき、その菌のすべての祖先の記録を出力するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑏
１行に菌の番号𝑏 (1 ≤ 𝑏 ≤ 1,000,000 = 10 )が与えられる。

出力
菌𝑏の祖先の記録を𝑏から1まで順番に、１行に番号を１つずつ出力する。

入出力例
入力例１5

出力例１521

入力例２12出力例２12631

問題４正方形（５点）

２次元平面上に整数座標の点が４つ与えられます。これらの点を、与えられた順に線で結んで、最後の点と最初の点の間も線で結んでできあがる図形が、正方形かどうか判定してください。

課題
与えられた順に点を線で結んで、最後の点と最初の点の間も線で結んでできあがる図形が、正方形かどうかを判定するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑥 𝑦𝑥 𝑦𝑥 𝑦𝑥 𝑦
入力は４行である。𝑖行目に𝑖番目の点の座標𝑥 , 𝑦 (−1,000 ≤ 𝑥 , 𝑦 ≤ 1,000)が、整数で与えられる。ただし、𝑖番目の点と𝑖 + 1番目の点は異なり(𝑥 ≠ 𝑥(𝑥 ≠ 𝑥 または𝑦 ≠ 𝑦 )。

または𝑦 ≠ 𝑦)、4番目の点と1番目の点も異なる

出力できあがる図形が正方形であれば「Yes」、正方形でなければ「No」を１行に出力する。

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

出力例１Yes

入力例２10 1012 1012 1212 10

出力例２No

入力例３0 02 20 4-2 2

出力例３Yes問題５２０２３に似た数（５点）

2023 は17 × 17 × 7という３つの素数の積で表せます。このうち、２つだけが同じ数17です。ある正の整数𝑁が、異なる２つの素数𝑝,𝑞によって𝑁 = 𝑝 × 𝑝 × 𝑞と表せるとき、𝑁を 2023 に似た数と呼ぶことにします。

課題
正の整数𝑁が与えられたとき、𝑁が 2023 に似た数かどうかを判定するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑁
１行に正の整数𝑁 (1 ≤ 𝑁 ≤ 1,000,000,000 = 10 )が与えられる。

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

出力
𝑁が 2023 に似た数なら「Yes」、そうでないなら「No」と 1 行に出力する。

入出力例
入力例１2023

出力例１
Yes

入力例２12

出力例２Yes

入力例３27

出力例３No27 = 3 × 3 × 3となるが、３つの数は同じになってはいけないため、2023に似た数ではない。
入力例４49

出力例４No49 = 7 × 7 × 1となるが、1は素数ではないため、2023に似た数ではない。

問題６

ダンシング迷路（６点）

A 君は人気のゲーム「ダンシング迷路」に没頭している。このゲームの迷路は、上から𝑖行目、左から𝑗列目の部屋の番号を(𝑖, 𝑗)とする𝐻 × 𝑊個の正方形の部屋を、縦と横にそれぞれ𝐻行と𝑊列に並べた長方形の領域である。
プレイヤーの目的は、迷路の入口がある部屋(1,1)から出口のある部屋(𝐻, 𝑊)まで、最少の移動回数で移動することである。入口から出口まで移動する間、プレイヤーは一定の間隔で手拍子を打ち続けなければならない。ゲームは、プレイヤーが手拍子で刻む拍にしたがって進行する。
縦または横に隣り合う部屋の間は扉で仕切られている。ふだん扉は閉じられているが、最初の３拍のどれかの拍で開き、以後３拍ごとに開く。つまり、最初の３拍のうち𝑏拍目(𝑏 = 1, 2, 3)で開く扉は𝑏 + 3𝑛拍目だけで開く(𝑛 ≥ 0)。最初の３拍のうちどの拍で開くかは、扉によって様々である。たとえば、最初の３拍のうち２拍目で開く扉は、その後５拍目、８拍目、…で開く。扉は手拍子の瞬間に開き、プレイヤーはその瞬間に開いている扉を通って、隣り合う部屋へ瞬時に移動できる。
プレイヤーは１拍ごとに移動しなければならない。このとき、１つの拍で移動できるのは一部屋だけである。移動できなければ、そこでゲームオーバーとなるため、プレイヤーは出口にはたどり着けない。
移動を続けることができても、迷路によっては永久に出口にたどり着けない場合もある。

課題
迷路の大きさと、隣り合う部屋との間の扉が開く拍の情報が与えられる。入口の部屋から出口の部屋へ移動するための最少の移動回数を求めよ。ただし、最初の拍は 1 とする。

入力
入力は以下の形式で与えられる。
𝐻𝑊𝑟𝑜𝑤
𝑟𝑜𝑤
:
𝑟𝑜𝑤
𝑐𝑜𝑙
𝑐𝑜𝑙:
𝑐𝑜𝑙

1 行目に、迷路の縦方向の部屋の数𝐻(2 ≤ 𝐻 ≤ 100)と横方向の部屋の数𝑊(2 ≤ 𝑊 ≤ 100)が与えられる。
続く𝐻行に、𝑖行目に並ぶ部屋の間の扉がいつ開くかを表す情報𝑟𝑜𝑤 が以下の形式で与えられる。
𝑑, 𝑑, … 𝑑,𝑑 , (1,2 または 3)は、𝑖行目の部屋の並びで、横方向に𝑗番目と𝑗 + 1番目の間にある扉が最初の３拍のうちどの拍で開くかを表す整数である。

続く𝑊行に、𝑗列目に並ぶ部屋の間の扉がいつ開くかを表す情報𝑐𝑜𝑙 が以下の形式で与えられる。
𝑓, 𝑓, … 𝑓,𝑓 , (1,2,または 3)は、𝑗列目の部屋の並びで、縦方向に𝑖番目と𝑖 + 1番目の間にある扉が最初の３拍のうちどの拍で開くかを表す整数である。

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

出力出口に移動できる場合は最少の移動回数を 1 行に出力する。どのように移動しても出口にたどり着けない場合は「-1」を出力する。

入出力例
入力例１2 33 12 3121

出力例１3

入力例２2 33 1
1 3121

出力例２-1

問題７

ボールの並べ替え（６点）

様々な大きさの𝑁個の箱が左から右へ一列に並んでいて、それぞれの箱にボールが１つずつ入っています。ボールの大きさも様々ですが、どの箱にも箱より大きなボールを入れることはできません。
箱は交換せずに、隣り合う箱の中のボールだけを交換する操作を好きなだけ行うことができるとき、左から右へボールの大きさの昇順、つまりどのボールの大きさも、その左隣のボールの大きさ以上になるように並べ替えることは可能でしょうか。

課題
箱の大きさとボールの大きさがそれぞれ与えられたときに、ボールを昇順に並べ替えることができるかどうかを判定するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑁𝐴 𝐴 ⋯𝐴𝐵 𝐵 ⋯𝐵
１行目に箱とボールの数𝑁(1 ≤ 𝑁 ≤ 100,000 = 10 )が与えられる。続く１行に左から𝑖番目の箱の大きさ𝐴 (1 ≤ 𝐴 ≤ 1,000,000,000 = 10 )が与えられる。続く１行に左から𝑖番目の箱に入っているボールの大きさ𝐵 (1 ≤ 𝐵 ≤ 1,000,000,000 = 10 )が与えられる。ただし、𝐵 ≤ 𝐴 である。

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

出力
昇順に並べ替えることができれば「Yes」、そうでなければ「No」を１行に出力する。

入出力例
入力例１53 2 3 5 5
2 1 3 5 4

出力例１Yes

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

出力例２No

入力例３33 3 3
1 1 1

出力例３Yes

問題８ボールの回収（１０点）

野球部員のユアサ君は、帰宅する前にグラウンドに散らばったボールをすべて回収しなければなりません。グラウンドを２次元平面で、ボールを平面上の点で表します。はじめは、ユアサ君は原点にいます。
また、𝑖番目のボールは座標(𝑥 , 𝑦 )にあり、𝑥方向に秒速𝑠 、𝑦方向に秒速𝑡 で動いています。ボールは座標が同じになっても衝突せず、お互いの移動に影響しません。
ユアサ君は常に秒速𝑣で移動します。彼は、最初に移動する方向を任意に決めることができます。その後、ボールを回収したときに限り移動の方向を任意に変えることができます。ユアサ君がボールと同じ座標にいれば、そのボールを０秒で回収できます。すべてのボールを回収するためにかかる最小の秒数を求めてください。

課題
ボールの個数とその座標と速度、ユアサ君の移動速度が与えられたとき、すべてのボールを回収するために必要な最小の秒数を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑁𝑣
𝑥 𝑦 𝑠 𝑡𝑥 𝑦 𝑠 𝑡:𝑥 𝑦 𝑠 𝑡
１行目に、回収したいボールの数𝑁(1 ≤ 𝑁 ≤ 8)と、ユアサ君の速さ𝑣(2 ≤ 𝑣 ≤ 1,000)が整数で与えられる。続く𝑁行に、𝑖番目のボールが最初にある座標𝑥 , 𝑦 (−1,000 ≤ 𝑥 , 𝑦 ≤ 1,000)と、𝑥方向、𝑦方向それぞれに動く速度𝑠 , 𝑡 (−30 ≤ 𝑠 , 𝑡 ≤ 30)が、すべて整数で与えられる。ただし、𝑠 + 𝑡 ≤ √𝑣とする。

出力すべてのボールを回収するために必要な最小の秒数を実数で 1 行に出力する。ただし、誤差がプラスマイナス 0.0001 を超えてはならない。この条件を満たせば小数点以下は何桁表示してもよい。

入出力例
入力例１2 22 0 -1 0
1 2 -1 0

出力例１2

入力例２2 22 0 1 0
2 2 0 1

出力例２6.23927

問題９

色鉛筆とキャップ（１１点）

ユキは色鉛筆が大好きです。大好きな色鉛筆の芯が折れないように、ユキはそれぞれの色鉛筆の先にキャップを１つ装着します。いま、𝑁色で１セットの色鉛筆セットがあります。また、𝑁色のキャップがそれぞれ𝑀個あります。すべてのキャップは１つの袋にまとめて入っています。
ユキさんの前には、どの色鉛筆にもキャップが装着されていない色鉛筆セットがあります。これから、以下の操作を繰り返して色鉛筆にキャップを装着します。
 袋から１つのキャップを取り出す。ただし、袋の中のキャップを取り出す確率はどれも等しいとする。そのキャップの色を𝑖とする。色𝑖の色鉛筆にまだキャップが装着されていなければ、このキャップを装着する。そうでなければ、このキャップは袋に戻さずに破棄する。
𝑇回操作した後に、すべての色鉛筆にキャップが装着された状態になる可能性を計算してください。

課題
色鉛筆の種類の数𝑁と、キャップのセットの個数𝑀と、操作の回数𝑇が与えられる。上の操作を𝑇回行った際に、すべての色鉛筆にキャップが装着されている確率を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑁𝑀𝑇
１行に色鉛筆の種類の数𝑁、キャップのセットの個数𝑀、操作を行う回数𝑇が正の整数で与えられる。
ただし、1 < 𝑀 × 𝑁 < 998,244,353、1 ≦ 𝑇 × 𝑁 ≦ 100,000 = 10 を満たす。また、𝑇 ≦ 𝑀 × 𝑁である。

出力す べ て の 色 鉛 筆 に キ ャ ッ プ が 装 着 さ れ た 状 態 に な る 確 率 を 既 約 分 数 𝑝/𝑞 で 表 し た と き 、 𝑞𝑥 ≡𝑝 (𝑚𝑜𝑑 998,244,353)を満たすような𝑥の値を出力せよ。ただし、𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑐) (𝑎, 𝑏は非負整数、𝑐は正の整数)とは、𝑎を𝑐で割ったあまりと𝑏を𝑐で割ったあまりが等しいという意味である。
※補足：この問題で求める確率は必ず有理数になる。また、この問題の制約下では、求める確率を既約分数𝑝/𝑞で表したときに𝑞は998,244,353で割り切れない。このとき、𝑞𝑥 ≡ 𝑝 (𝑚𝑜𝑑 998,244,353)を満たすような0以上998,244,353未満の整数𝑥はただ一つしか存在しない。

入出力例
入力例１2 10 11

出力例１1入力例２3 4 3

出力例２871195072

問題１０枠作り（１１点）

一辺の長さ１の正方形のタイルが縦に H 個、横に W 個長方形状に並べられている。タイルには綺麗なタイルと汚れたタイルの２種類があり、上から𝑟番目、左から𝑐番目のタイルの種類を𝑠 , とする。𝑠 , が1 のとき綺麗なタイルを、0 のとき汚れたタイルを表す。
あなたは綺麗なタイルだけを残して、正方形状の枠を作ろうとしている。このときに作れる最大の正方形の一辺の長さを求めよ。なお、以下の条件を全て満たす整数の組(𝑟 , 𝑐 , 𝑟 , 𝑐 )が存在するとき、一辺の長さが𝑟 − 𝑟 + 1の正方形の枠が存在するものとする。






1≤𝑟 ≤𝑟 ≤𝐻1≤𝑐 ≤𝑐 ≤𝑊𝑟 −𝑟 =𝑐 −𝑐𝑐 ≤ 𝑐 ≤ 𝑐 を満たす全ての整数の組(𝑟 , 𝑐)において𝑠 , = 1𝑐 ≤ 𝑐 ≤ 𝑐 を満たす全ての整数の組(𝑟 , 𝑐)において𝑠 , = 1𝑟 ≤ 𝑟 ≤ 𝑟 を満たす全ての整数の組(𝑟, 𝑐 )において𝑠 , = 1𝑟 ≤ 𝑟 ≤ 𝑟 を満たす全ての整数の組(𝑟, 𝑐 )において𝑠 , = 1

課題
縦と横のタイルの数、および各タイルの状態が与えられたとき、作ることができる最大の正方形の一辺の長さを求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝐻𝑊𝑠 , 𝑠 , ⋯𝑠 ,𝑠 , 𝑠 , ⋯𝑠 ,⋮𝑠 , 𝑠 , ⋯𝑠 ,１行目に、縦に並んだタイルの数𝐻と横に並んだタイルの数𝑊(1 ≤ 𝐻, 𝑊 ≤ 2,000)が与えられる。続く
𝐻行に、𝐻 × 𝑊個のタイルの状態を表す整数𝑠 , 0 ≤ 𝑠 , ≤ 1 が与えられる。ただし、𝑠 , が1のときは綺麗なタイルを、0のときは汚れたタイルを示す。

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

出力作ることができる最大の正方形の一辺の長さを１行に出力する。ただし、正方形の枠が作れない場合は「0」を出力する。

入出力例
入力例１3 511100
1011011101

出力例１3

入力例２4 41111101111111111

出力例２4

入力例３2 21111

出力例３2

入力例４2 21110

出力例４1

問題１１

テレポート移動網２０２３（４０点）

イヅア国には𝑁個の街と𝑁 − 1本の道路がある。𝑖番目の道路は街𝐴 と街𝐵 を双方向に結んでおり、その通行コストは𝐶 である。また、どの街からも、いくつかの道路を通って他のすべての街へたどり着くことができる。
イヅア国には、国民の移動をより便利にするために、街 1 に管制施設が、それ以外の街にはテレポート装置が設置されている。街𝑖に設置されたテレポート装置を使って、以下の条件を満たす街𝑘へコスト𝑇で移動することができる。


街𝑖と街𝑘との距離が𝐷 以下である
街 1 と街𝑖との距離と、街 1 と街𝑘との距離が等しい

ここで、街𝑢と街𝑣との距離を、𝑢から𝑣へ道路のみを用いて移動するときに使う必要のある最小の道路の数とします。

課題
イヅア国の街の数、道路とそれらのコスト、テレポート装置の情報、始点の街の番号𝑆,終点の街の番号𝐺 が与えられる。街𝑆 から街𝐺 へ道路とテレポート装置を使ってたどり着くのにかかるコストの合計の最小値を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑁𝑆𝐺
𝐴 𝐵 𝐶
𝐴 𝐵 𝐶
⋮
𝐴

𝐵𝐶𝑇 𝐷𝑇 𝐷⋮
𝑇 𝐷

1 行目に街の数𝑁(2 ≤ 𝑁 ≤ 100,000 = 10 )、始点の街の番号𝑆(1 ≤ 𝑆 ≤ 𝑁)、終点の街の番号𝐺(1 ≤ 𝐺 ≤ 𝑁)が与えられる。続く𝑁 − 1行に、𝑖番目の道路の両端の街𝐴 , 𝐵 (1 ≤ 𝐴𝑖 < 𝐵𝑖 ≤ 𝑁)およびその通行コスト
𝐶 (1 ≤ 𝐶𝑖 ≤ 1,000,000,000 = 10 )が、すべて整数で与えられる。続く𝑁 − 1行に、街𝑖に設置されているテレポート装置を使用するコスト𝑇 (1 ≤ 𝑇 ≤ 1,000,000,000 = 10 )と、移動できる距離の制約𝐷 (1 ≤ 𝐷𝑖 ≤200,000 = 2 × 10 )が、すべて整数で与えられる。

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

出力コストの合計の最小値を 1 行に出力する。

入出力例
入力例１6 3 6
1 2 4
2 3 1
2 4 5
1 5 2
5 6 3
2 36 35 25 18 6

出力例１6入力例２6 3 6
1 2 4
2 3 1
2 4 1
1 5 25 6 32 86 8
1 85 88 8

出力例２3