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

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

問題１
問題１ 摂氏華氏（３点）

温度を表すとき、日本では摂氏（℃）という単位を使いますが、アメリカでは華氏（℉ ）という単位を使います。例えば、摂氏での２０度は華氏だとおよそ６８度になるので、アメリカに行くと「今日は６８度だ」などという会話が日常的にされます。
華氏で表された温度から３２を引いて９分の５を掛けると、摂氏に直すことができます。しかし、これだと暗算しづらいので、簡易版として３０を引いて２で割るという式が使われることがあります。これを使うと、華氏の６８度は（６８－３０）÷２＝１９度になります。

課題
華氏で表された温度を簡易版の変換式℃＝（℉－３０）÷２で摂氏に直すプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
F
１行に華氏で表された温度F(30≦F≦100)が与えられる。ただし、Fは２で割り切れる整数である。

出力摂氏に変換した温度を１行に整数で出力する。

入出力例
入力例１68

出力例１19

入力例２50出力例２10問題２問題２ 赤とんぼ

（３点）

まだ暑い日が続きますが、もう９月。暦の上では秋です。気がつけば、目の前の塀の上に赤とんぼが２匹とまっています。秋ですね。

課題
塀の左端から計った、２匹のトンボの頭の位置が与えられたとき、２匹のトンボの頭がどれだけ離れているか計算するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
x1 x2
１行に１匹目のトンボの頭の位置x1と２匹目のトンボの頭の位置x2(0≦x1,x2≦100)が整数で与えられる。

出力
２匹のトンボの頭の間の距離を 1 行に出力する。

入出力例
入力例１20 30出力例１10入力例２50 25

出力例２25

入力例３25 25

出力例３0

問題３問題３ ケーキパーティー
ケーキパーティー（４点）

私の誕生日にケーキパーティーをすることにしました。パーティには私と友人が参加します。何人かの友人は、ケーキを数切れずつ買ってきました。しかし、ケーキの数の合計が、参加者の数でぴったり割りきれるかはわかりません。
ケーキを皆でできるだけ平等に分けたいので、次のようにルールを決めました。ケーキはまず皆が同じ数になるように分けます。その結果余りが出た場合は、パーティの主役である私が優先的に一切れもらうことにします。私は何切れのケーキをもらえるでしょうか？

課題
友人の数とケーキの情報が与えられたとき、私がもらえるケーキの数を求めるプログラムを作成せよ。
ただし、友人の数には私自身が入っていないことに注意せよ。

入力
入力は以下の形式で与えられる。
N C
p1 p2 … pC
１行目にパーティに参加している友人の数N(1≦N≦100)とケーキを持ってきた友人の数C(1≦C≦N)が与えられる。続く１行に、ケーキを持ってきた友人のうち、i番目の友人が持ってきたケーキの数pi(1≦pi≦100)が与えられる。

出力
私がもらえるケーキの数を１行に出力する。

入出力例
入力例１5 45 5 6 5

出力例１4入力例２7 58 8 8 8 8

出力例２5入力例３100 3
3 3 3出力例３1

問題４問題４ 熱中症対策（５点）

この夏は記録的な猛暑に見舞われています。あなたは、熱中症を予防するために、最寄りのスーパーで必要な量の水をまとめ買いすることにしました。このスーパーでは、１リットルと 500 ミリリットルの２種類のボトルに入った水が、それぞれの価格で売られています。あなたは、必要な量ぴったり買う方法がない、または合計金額が安くなるなら、必要な量より多く買おうと思っています。

課題
２種類のボトルの価格と必要な水の量を入力とし、必要な量以上の水を、できるだけ安くなるように買ったときの合計金額を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
A B X
１行に１リットル入りボトルの価格A(1≦A≦1000)、500ミリリットル入りボトルの価格B(1≦B≦1000)、必要な水の量X(1≦X≦20000)が与えられる。入力はすべて整数であり、水の量はミリリットル単位で与えられる。

出力
合計金額を 1 行に出力する。

入出力例
入力例１180 100 2400

出力例１460

入力例２200 90 2018

出力例２450

問題５問題５ デュードニー数（６点）

正の整数 x の各桁をすべて足して得られる数の３乗が x になるとき、この数 x をデュードニー数といいます。たとえば、５１２は８の３乗で、５＋１＋２＝８となるので５１２はデュードニー数です。
この問題では、デュードニー数と似た数を考えて、その個数を求めます。

課題
負でない整数 a、２以上の整数 n、および上限値 m が与えられる。このとき、x の各桁をすべて足して得られる数 y について、x=(y+a)n となる m 以下の正の整数 x の個数を出力するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
a n m１行に、a(0≦a≦50)、n(2≦n≦10)と上限値m(1000≦m≦108)が、すべて整数で与えられる。

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

出力個数を１行に出力する。

入出力例
入力例１出力例１16 2 1000
222400 = (4+0+0+16) となる数 400、841 = (8+4+1+16) となる数 841 の２つ。
入力例２出力例２0 3 5000
333
1 = 1 となる数 1、512 = (5+1+2) となる数 512、4913 = (4+9+1+3)3 となる数 4913 の３つ。
入力例３出力例３2 3 100000
0x の各桁をすべて足して得られる数 y について(y+2)3 = x となるような 100,000 以下の数 x はない。

問題６ ボゾソート（７点）

ボゾソートはボゴソートと並んで極めて効率の悪い整列アルゴリズムである。ボゾソートは乱数に基づくアルゴリズムで、以下の手順で数列の要素を整列する：
1. ２つの要素をランダムに選び、交換する。
2. 全ての要素が昇順に整列されているか確認する。
3. 整列されていれば終了。そうでなければ 1.へ戻る。
あなたはボゾソートを解析するために、あらかじめいくつか用意された２つの要素の位置にしたがって、シミュレーションすることにした。

課題
整数の数列に対して２つの要素を交換する命令がいくつか与えられる。何回目の命令で数列が昇順になるかを求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N
a1 a2 … aNQ
x1 y1x2 y2:
xQ yQ
１行目に数列の要素数N(2≦N≦300,000)が与えられる。続く１行に、数列の各要素を表す整数ai(1≦ai≦109)が与えられる。３行目に命令の個数Q(1≦Q≦300,000)が与えられる。続くQ行にi番目の命令を表す２つの整数xi,yi(1≦xi,yi≦N)が与えられる。命令は数列のxi番目の要素とyi番目の要素を交換することを示す。ただし、xi≠yiである。

出力
最初に数列が昇順になる命令の番号を 1 行に出力する。ただし、最初から昇順に整列されている場合は0、全ての命令を処理しても昇順にできない場合は-1 を出力する。

入出力例
入力例１69 7 5 6 3 131 62 53 4

出力例１2入力例２44 3 2 121 23 4

出力例２-1入力例３51 1 1 2 211 2

出力例３0

問題７ ワープ装置

（１０点）
１０点）

西暦 30xx 年、ある星を訪れた探検隊は、謎の超文明が作ったワープ装置を発見した。ワープ装置の入り口を通ると、出口がどんなに遠く離れたところにあっても瞬時に移動できる。この技術を解明すれば、人類は宇宙の果てまで旅することができるのだ！
調査を始めた科学者チームは、ワープ装置の出入り口が存在するすべての星を特定した。星には、1 から N までの番号が振られており、それぞれの星にはワープ装置の入り口と出口が一つずつある。入り口と出口には、それぞれ一つずつ文字が記されている。
ワープ装置の間の移動の仕組みは以下のようなものである。
 文字 a が書かれている入り口から入ると、文字 a が書かれた出口のどれかに移動できる。
 星 i にある入り口から入ると、i＜j を満たす星 j にある出口だけから出ることができる。
ある星に置かれたワープ装置の出口から出た後、同じ星にあるワープ装置の入り口から入ることを繰り返していけば、ワープ装置を乗り継いで遠くの星までたどり着くことができる。人類は星１を起点として星 N に探検隊を派遣することにした。星 N に到達できる可能性を見積もるために、星 1 から出発したときに星 N に到達できる行き方が何通りあるか計算することになった。

課題
星の情報が与えられたとき、星１から星 N まで行く方法が何通りあるか求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
Nst
１行目にワープ装置がある星の数N(2≦N≦100,000)が与えられる。２行目に、1からNまでの星にあるワープ装置の入り口に書かれた文字を表す長さNの文字列sが与えられる。３行目に、1からNまでの星にあるワープ装置の出口に書かれた文字を表す長さNの文字列tが与えられる。ただし、sとtに現れる文字はすべて英小文字であり、sのi番目の文字が星iにあるワープ装置の入り口に書かれた文字、tのi番目の文字が星iにあるワープ装置の出口に書かれた文字を表す。

出力
星 1 から星 N まで到達する方法が何通りあるかを表す数を 1,000,000,007 で割った余りを１行に出力する。

入出力例
入力例１6
abbababaabab

出力例１5

入力例２25neihsokcpuziafoytisrevinu
universityofaizupckoshien

出力例２4

問題８ タクシー（１０点）
１０点）

会津都市の PCK 社が運営する PCK タクシーはユニークな料金形態を採用しており、料金は客が決めることができる。今日も駅のタクシー乗り場では、多くの人が列をつくっている。
駅には、横 N 列に PCK 社のタクシー乗り場が設置されている。各乗り場には 1 から N までの番号が順番に付いており、タクシーが１台ずつ停まっている。また、各乗り場にはタクシーを待つ客が並んでおり、それぞれの客が払う料金はあらかじめわかっている。
PCK タクシーの運転手は提示額の低い客の乗車を断り、提示額の高い客を乗車させることで PCK 社の売り上げを上げている。
i 番目の乗り場にいる運転手は、客を乗せ出発するまで以下の行動を好きな順番で何度でも行うことができる。
1. i 番目の乗り場の列の先頭の客をタクシーにのせる。
2. i 番目の乗り場の列の先頭の客の乗車を断る。断られた客は列から消える。
3. i+1 番目のタクシー乗り場に他のタクシーが存在しなければ、そこに移動する。ただし、N 番目の乗り場にいる場合は、公道に出てタクシー乗り場を去る。
あなたの仕事は、事前調査で得られた客の希望料金の表を基に、PCK 社の売り上げを最大化することである。なお、１台のタクシーには最大一人の客を乗せることができる。

課題
タクシー乗り場の数と、各タクシー乗り場に並んでいる客の情報が与えられたとき、売り上げの総和の最大値を求めよ。

入力
入力は以下の形式で与えられる。
N
s1
s2
:sN
１行目にタクシー乗り場の数 N(1≦N≦300,000)が与えられる。続く N 行に、i 番目のタクシー乗り場に並んでいる客の情報 si が与えられる。各情報 si は以下の形式で与えられる。
M c1 c2 … cM
最初の整数 M(1≦M≦300,000)が、このタクシー乗り場に並んでいる人の数を表す。それに続いて、この乗り場の j 番目に並んでいる客が払う料金 cj(1≦cj≦10,000)が与えられる。
ただし、タクシー乗り場に並んでいる客の総数は 300,000 人以下である。

出力
売り上げの最大値を 1 行に出力する。

入出力例
入力例
33 8 10 1
4 7 1 2 15
3 11 8 19

出力例45

問題９問題９ 直線上の点（１０（１０点）

Ａ大学は今年もプログラミングコンテストを開催する。問題作成チームの一員であるあなたは、２次元座標平面上に複数の点を配置した入力データをいくつか生成した。このデータは K 個以上の点が同じ直線上にあってはならない。あなたは、作成した入力データがこの条件を満たしているかチェックすることにした。

課題
２次元座標平面上の各点の座標と数 K を入力とし、それらの点の中の K 個以上の点が同じ直線上に存在する場合があるか判定するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N K
x1 y1x2 y2:

xN yN
１行目に座標平面上の点の数N(3≦N≦3000)と整数K(3≦K≦N)が与えられる。続くN行に、点の座標xi,yi(0≦xi,yi≦10000)が整数で与えられる。ただし、同じ座標をもつ点は与えられない（i≠jについて、xi≠xj または yi≠yj）。

出力
K 個以上の点が同じ直線上に存在すれば「1」、存在しなければ「0」と１行に出力する。

入出力例
入力例１5 40 0
1 0
1 10 12 2

出力例１0

入力例２7 50 0
1 0
1 10 12 0
3 04 0

出力例２1

問題１０
問題１０ ダンジョン２（１４点）

Ｂ君は、昨年発売され人気だったゲーム「ダンジョン」の続編「ダンジョン２」で遊んでいる。ゲームは、N 個の部屋とそれらを直接つなぐ N-1 本の道からなるマップ上で行われる。道はどちらの部屋からでも行き来することができる。また、どの部屋からでも、いくつかの道をたどって他のどの部屋にも到達できる。各部屋には点数が書かれている。
Ｂ君はキャラクターのトラトラ君を動かして、高得点の獲得を目指す。部屋に初めて到達したときだけ、その部屋に書かれた点数が加算される。スタート地点とゴール地点の点数も加算される。ただし、道を通るたびに得点が１減点される。トラトラ君のスタート地点としてどの部屋を選んでも良いし、スタート地点も含め、どの部屋でゴールしても良い。

課題
マップの情報が与えられたとき、Ｂ君が得ることができる合計点の最大値を出力するプログラムを作成せよ。

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

出力
Ｂ君が得ることができる合計点の最大値を１行に出力する。

入出力例
入力例１76
1-143311 22 33 43 55 65 7

出力例１10

例えば、部屋番号６→５→３→４→３→２→１とたどれば得点が最大になる。
入力例２450111 22 32 4

出力例２5

部屋番号１をスタート地点かつゴール地点とすれば、得点が最大になる。

問題１１問題１１ 円盤（１４点）

古代遺跡から不思議な装置が発見された。発見された装置は、両面に整数が書かれた円盤、整数が書かれたカードの束、カードの束を入れる台からなる。台にカードの束を入れると、円盤が回転する。円盤は、常に片面だけが見えている。
円盤は中心から角度が均等になるように K 個の区画に分割されていて、表側に 1 から K までの整数が順番に時計回りに刻まれている。また、円盤は裏表で区画の境界を共有しており、ある区画の表側に数 Xが刻まれているとき、その裏側には数-X が刻まれている。さらに、円盤の外側には針が存在し、ある一つの区画の弧の中心を指し示している。以降、見えている面の針が指し示している値が X であるとき、円盤は X にセットされていると呼ぶ。

図 1

K = 5 の場合(の場合(図の左側では図の左側では円盤左側では円盤は円盤は 1 に、右側ではに、右側では-1 にセットされている)にセットされている)調査の結果、装置の挙動について以下のことが判明した。
装置の台にカードの束を入れると、装置は円盤を 1 にセットする。
その後、装置はカードを上から順に読み込んでいき、書かれている数 A に応じて以下のように動作する。
A が正の数のとき
A が 0 のとき
A が負の数のとき

円盤を図の時計回りに|A|区画回転させる
針と円盤の中心を通る直線を軸として、円盤を裏返す
円盤を図の反時計回りに|A|区画回転させる

ただし、|A|は A の絶対値を表す。台に入れる直前のカードの並び方によって、すべての動作終了後に円盤にセットされている値は様々である。そこで、装置の特性を調べるために、2 枚のカードを交換するごとにカードの束を台にセットし、すべての動作終了後の円盤にセットされている値を求めることを繰り返した。

課題
装置の情報とカードを交換する命令がいくつか与えられたとき、各命令に対して、すべての動作終了後に円盤にセットされている値を計算するプログラムを作成せよ。ただし、各命令では、それまでの命令で得られたカードの束に対して交換を行う。

入力
入力は以下の形式で与えられる。
K N Q
A1 A2 … AN
L1 R1L2 R2:
LQ RQ
１行目に、区画の個数K(2≦K≦109)、カードの枚数N(2≦N≦100,000)、命令の個数Q(1≦Q≦100,000)が与えられる。２行目に、カードに書かれているN個の整数が与えられる。Ai(-109≦Ai≦109)は上からi番目のカードに書かれている数を表す。続くQ行にi番目の命令を表すLi,Ri(1≦Li＜Ri≦N) が与えられる。
命令は上からLi番目のカードとRi番目のカードの位置を交換し、カードの束を台に入れる操作を表す。

出力
各命令に対して、すべての動作終了後に装置にセットされている値を１行に出力する。

入出力例
入力例１5 3 1
1 -2 02 3

出力例１-3

一つめの命令後のカードの束は上から順に以下のようになる。
1 0 -2
一つ目の命令に対し、装置は以下のように動作する。

図2

装置の動作の様子したがって、すべての動作終了後に円盤にセットされている値は-3となり、これを出力する。
入力例２5 7 50 0 3 3 3 3 3
1 22 33 44 55 6

出力例２12345

問題１２
問題１２ 待ち合わせ（１４（１４点）

あなたはヅイア王国にあるイアヅ高校の教員である。ヅイア王国には N 個の都市と N-1 本の街道が存在し、どの都市からどの都市へもいくつかの街道を通って移動することができる。各街道は双方向に移動可能で、その長さもわかっている。
あなたは授業の一環として次のような課題を計画している。まず、相異なる３つの都市に共通するテーマをいくつか用意する。次に、各テーマに対し３人のグループを割り当てる。割り当てられたグループは３つの都市について１人ずつ担当を決め、各都市で現地調査を行う。その後、N 個の都市のうちのどこかに集合し、成果をまとめる。
各テーマについて、３人はそれぞれの調査対象の都市から集合先の都市まで最短距離で移動する。３人の移動距離のうち、最も長い距離をそのテーマのコストとする。あなたは、テーマごとのコストが最小になるように集合先の都市を選びたい。

課題
都市の個数、街道の情報、テーマごとに指定された３つの都市が Q 個与えられたとき、テーマごとのコストの最小値を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N Q
u1 v1 w1
u2 v2 w2:
uN-1 vN-1 wN-1
a1 b1 c1
a2 b2 c2:
aQ bQ cQ
１行目に、ヅイア王国の都市の数 N(3≦N≦100,000)、テーマの個数 Q(1≦Q≦100,000)が与えられる。
続く N-1 行に、i 番目の街道の情報を表す ui,vi,wi(1≦ui＜vi≦N,1≦wi≦10,000)が、すべて整数で与えられる。これは i 番目の街道が都市 ui と都市 vi を結んでおり、その長さは wi であることを表している。
続く Q 行に i 番目のテーマの調査対象の都市の番号 ai,bi,ci(1≦ai＜bi＜ci≦N) が与えられる。

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

出力
各テーマに対して、コストの最小値を 1 行に出力する。

入出力例
入力例１5 41 2 3
2 3 4
2 4 24 5 3
1 3 4
1 4 5
1 2 3
2 4 5

出力例１4543

1つめのテーマでは、都市2に集合すると都市3に居る生徒の移動距離である4がコストとなる。
コストを4未満にできるような集合先の都市は存在しないので、4を出力する。
2つめのテーマでは、都市2または都市4に集合するとコストが5になり、これが最小である。
入力例２5 3
1 2 1
2 3 1
3 4 1
4 5 1
1 2 3
1 3 5
1 2 4

出力例２122

入力例 315 15
1 2 452 3 81
1 4 291 5 2
5 6 254 7 847 8 564 9 2
4 10 37
7 11 39
1 12 1111 13 6
3 14 68
2 15 1610 13 14
13 14 15
2 14 15
7 12 15
10 14 15
9 10 15
9 14 15
8 13 155 6 13
11 13 15
12 13 142 3 105 13 15
10 11 146 8 11

出力例 3194194979014966149140129129194111129194140