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

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

問題１問題１ 緯度経度（３点）

地球上の位置は緯度と経度の二つの角度で表現できます。緯度は南北の位置を表す角度で、経度は東西の位置を表す角度です。角度は通常、度という単位で表しますが、秒という単位でも表すことができます。角度 1 度は 3600 秒です。たとえば、10.2 度は 36720 秒になります。

課題
緯度と経度の角度が秒で与えられたとき、それらを度に変換するプログラムを作成せよ。秒から度への変換は、それぞれの値を 3600 で割ることで求めることができる。ただし、この問題では計算結果の小数点以下は切り捨てるものとする。

入力
入力は以下の形式で与えられる。
La Lo
１行に緯度La(72,000≦La≦165,600)と経度Lo(442,800≦Lo≦554,400)が整数で与えられる。

出力度で表した緯度と経度を、空白区切りで１行に出力する。

入出力例
入力例１72000 500000

出力例１20 138

入力例２135090 503784

出力例２37 139

問題２問題２ 商店街へのお出かけ（４点）

イズア村には東西に延びる道に沿って商店街があります。ヤエちゃんは商店街の西の端に、タケコちゃんは東の端に住んでいます。二人は自分の家から商店街にあるジョーさんの店まで道に沿って歩いて行こうとしています。しかし、ヤエちゃんとタケコちゃんはまだ小さいので、家からあまり遠くまで歩いていけません。

課題
商店街の長さ、二人が歩ける最大距離、商店街の西の端からジョーさんの店までの道に沿った距離が与えられたとき、ヤエちゃんとタケコちゃんが店まで歩いて行けるか計算するプログラムを作成せよ。ただし、二人が歩ける最大距離は二人とも同じである。

入力
入力は以下の形式で与えられる。
w m s
１行に商店街の長さw(2≦w≦1,000)、二人が歩ける最大距離m(0≦m≦500)、商店街の西の端からジョーさんの店までの道に沿った距離s(0＜s＜w)が整数で与えられる。

出力
二人ともたどり着けないとき 0 を、ヤエちゃんだけがたどり着けるとき 1 を、タケコちゃんだけがたどり着けるとき 2 を、二人ともたどり着けるとき 3 を１行に出力する。

入出力例
入力例１200 50 30

出力例１1入力例２300 100 200

出力例２2入力例３500 300 300

出力例３3

入力例４1000 400 450

出力例４0問題３ あいさつまわり

（５点）
（５点）

オオウチ村では、村の大通りに沿って村人の家があります。大通りは、村の西の端から東に向かって一直線に延びています。オオウチ村に引っ越してきたモチヒト君は、すべての家を訪ねて挨拶をしたいと考えています。モチヒト君が、現在いる位置から出発して、すべての家に挨拶をするまでに移動しなければならない距離はどれくらいになるでしょうか。

課題
モチヒト君が現在いる位置と、すべての村人の家の位置が、大通りに沿って与えられたとき、すべての家を訪ねるのに必要な移動距離の最小値を計算するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
Nx x1 x2 … xN
１行目に村人の家の数N(1≦N≦100)が与えられる。２行目の最初のx(0≦x≦1,000)にモチヒト君が現在いる位置が与えられ、残りのxi(0≦xi≦1,000)に村人の家の位置が与えられる。ただし、村人の家の位置はすべて異なる(i≠jならばxi≠xjである)。また、道路の西の端の位置を0とする。

出力すべての家を訪ねるのに必要な移動距離の最小値を１行に出力する。

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

出力例１5入力例２64 10 2 3 7 4 8

出力例２10問題４ カラフル円盤通し

（６点）
（６点）

カラフル円盤通しは、垂直に棒が刺さった土台と、中心に穴の開いたいくつかの紙の円盤を使って遊ぶゲームです。円盤の半径はすべて異なり、同じ色の円盤はありません。土台に刺さっている棒を円盤の穴に通し、すべての円盤を重ねたとき、真上から見ることができる色の数が、このゲームでの得点になります。すなわち、真上から見えない円盤は得点に関係しません。

課題
円盤の半径が下から順番に与えられたとき、すべての円盤を重ね終えたときの得点を計算するプログラ
ムを作成せよ。たとえば、図のような積み方の場合、得点は 3 になる。

BGRGRGB

入力
入力は以下の形式で与えられる。
Nr1 r2 … rN
１行目に円盤の数N(1≦N≦1,000)が与えられる。２行目に各円盤の半径ri(1≦ri≦N)が整数で与えられる。ただし、円盤の半径はすべて異なる(i≠jならばri≠rjである)。

出力
得点を１行に出力する。

入出力例
入力例１73 6 7 4 5 1 2

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

出力例２6問題５ 写真の回転（７点）（７点）

PCK 君は、写真を回転して加工するアプリケーションを開発しています。このアプリケーションでは、正方形の写真を１つ入力した後、複数の回転命令によって写真を回転させます。１つの回転命令で、写真の真ん中の点(正方形の対角線の交点)を軸として時計回りまたは反時計回りに 90°回転させます。

課題
写真と回転命令が与えられたとき、すべての命令を処理した後の写真を描画するプログラムを作成せよ。
ただし、写真は N×N 個のピクセルで構成され、１つのピクセルの情報は英文字１つで表すものとする。

入力
入力は以下の形式で与えられる。
N
row1
row2
:

rowN
Q
r1
r2
:

rQ
１行目に写真の縦と横のピクセルの数N(1≦N≦1,000)が与えられる。続くN行に上からi番目にある行のピクセル情報rowiが与えられる。rowiは英文字からなる長さNの文字列である。続く1行に回転命令の数Q(1≦Q≦200,000)が与えられる。続くQ行に、回転の方向を表す整数ri(-1 または 1)が与えられる。riが1のとき時計回りに、-1のとき反時計回りに90°回転することを意味する。

出力すべての回転命令を処理した後の写真のピクセル情報を N 行に出力する。上から i 番目にある行のピクセル情報を i 行目に出力する。

入出力例
入力例１2AIZU211

出力例１UZIA

入力例２3xOO
OOyOOO1-1

出力例２OyO
OOOxOO問題６問題６ テトラへドロン

（８点）
（８点）

アイヅ塗装の職人は、独特な方法で壁に色を塗ります。壁は次の図のような三角形の座標系で区画されています。

(1, 3)(0, 3)(1, 2)(2, 2)(1, 1)(1, 0)(0,0)(5, 2)(3, 0)(5, 0)(2, 0)(4, 0)(9, 2)(8, 2)(7, 1)(6, 1)(9, 3)(8, 3)(7, 2)(6, 2)(5, 1)(4, 1)(7, 3)(6, 3)(4, 2)(3, 1)(2, 1)(5, 3)(4, 3)(3, 2)(0, 2)(0, 1)(3, 3)(2, 3)(9, 1)(8, 1)(7, 0)(9, 0)(6, 0)(8, 0)

各表面に十分な塗料を染み込ませた四面体があります。彼らは、ローラーの代わりに、この四面体を転がします。四面体の各表面には、次の図のように４つの色 R, G, B, Y の塗料がそれぞれ染み込ませてあり、表面が接した区画を塗ることができます。

GG

RBYY
底面はB

底面はR

職人は区画(0,0)から始めて、四面体の１辺を軸として転がしながら壁を塗っていきます。作業が終わるまで四面体を壁から離したり、壁の上を滑らせたりすることはしません。例えば、四面体を適当に転がすと、壁には次の図のような模様ができます。

BR

YY
BG
BG
B

Y

R

YR

Y

R

BR
YG

この方法で色を塗ると、最初の区画(0,0)と２番目に通る区画(1,0)の色を決めれば、その後どのような転がし方をしても、全ての区画の色が一通りに決まります。

課題
最初と２番目に通る区画の色が与えられ、さらに、色を求めたい区画が 1 つ以上与えられたとき、指定された各区画の色を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
c1 c2
N
x1 y1
x2 y2
:
xN yN
１行目に最初と２番目に通る区画の色c1とc2 (‘R’,‘G’,‘B’または‘Y’) が与えられる。ただし、c1≠c2である。２行目に色を求めたい区画の数N (1≦N≦100)が与えられる。続くN行に、色を求めたい区画の座標xi,yi(0≦xi,yi≦100)が与えられる。

出力
出力は N 行である。色を求めたい i 番目の区画の色を表す文字１つを i 行目に出力する。

入出力例
入力例
B R
28 31 1

出力例
YG

問題７問題７ 加工機

（９点）
（９点）

アイヅ工業は、加工機でのものづくりの仕事を請け負っています。アイヅ工業が所有する加工機を図１の左に示します。この加工機は、任意の直方体を加工することができ、その幅、奥行、高さは自由に設定できます。この直方体の上に幅 1cm と奥行 1cm の刃があります。この刃は、削りたい位置の真上に動かすことができます。削りたい位置は図１の右に示すような区画の座標で指定します。
立体図

座標
刃

加工する物を高さ方向から見下ろしたところ

高さ

奥行６

幅６0,0 1,0 2,0 3,0 4,0 5,0

幅0,1 1,1 2,1 3,1 4,1 5,10,2 1,2 2 2 3,2 4,2 5,20,3 1,3 2,3 3,3 4,3 5,3

幅

0,4 1,4 2,4 3,4 4,4 5,4

加工する物

0,5 1,5 2,5 3,5 4,5 5,5
奥行

奥行

図１：加工機の立体図と区画の座標

この加工機は以下の手順を繰り返すことで直方体を削ります。
 刃を指定した区画の真上に移動します。
 加工するものに接するまで刃を下ろし、その区画を指定した長さだけ新たに削ります。
 刃を上げて最初の高さまで戻します。
端の一画を削ったときの例を図２に示します。
刃高さ

幅
加工する物
奥行
0,0 1,0 2,0 3,0 4,0 5,0

図２：加工機を用いた切削の例

幅0,1 1,1 2,1 3,1 4,1 5,10,2 1,2 2 2 3,2 4,2 5,2上の図では区画(0,5)を削っている

0,3 1,3 2,3 3,3 4,3 5,30,4 1,4 2,4 3,4 4,4 5,40,5 1,5 2,5 3,5 4,5 5,5
奥行

アイヅ工業では、加工後の表面積がいくらになるかで加工料金を決めています。いままでは職人さんが手作業で測っていましたが、これをプログラムで計算できるようにしたいと考えています。

課題
加工する直方体の大きさと、直方体をどのように削るかを表す情報が与えられたとき、加工後の表面積がいくらになるかを計算するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
W D H Cx1 y1 z1x2 y2 z2:

xC yC zC
１行目に加工する直方体の幅W(1≦W≦100,000)、奥行D(1≦D≦100,000)、高さH(1≦H≦100,000)、および削る回数C(0≦C≦100,000)が与えられる。続くC行に、直方体をどのように削るかを表す情報が与えられる。xi(0≦xi＜W)とyi(0≦yi＜D)は削る区画の座標を表す。また、zi(1≦zi＜H)は、その区画を現在の高さからどれだけ削るかを表す整数である。ただし、各区画について、削った後の高さが１より小さくなるような入力は与えられない。

出力
加工後の表面積を１行に出力する。

入出力例
入力例１3 4 5 20 0 4
1 1 4

出力例１110

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

入力例２は、一度も削らない場合なので、表面積は与えられた直方体の表面積と同じになる。

問題８ 高速道路網

（１０点）
（１０点）

ヅイア国の高速道路網は、都市(地点)とそれらを結ぶ道路から構成されています。イワシロ地域を縦断するイワシロ自動車道は国の重要な幹線です。イワシロ自動車道の上り線は以下のように建設されています。





1 から N の番号が割り当てられた N 個の都市（地点）がある。
地点 1 が起点、地点 N が終点である。
道路は一方通行で、ある地点とある地点を直接結ぶ道路は多くても１つしかない。
どの地点にも必ず起点からたどり着くことができ、どの地点からも終点にたどり着ける。
どのように道路をたどっていっても、同じ地点に戻ることはない。

ヅイア国はイワシロ自動車道の上り線の調査を行うことにしました。この調査では、上り線の各地点について、その地点を通って起点から終点へ向かうすべての経路の長さの和を求める必要があります。

課題
地点の数と道路の情報が与えられる。各地点 i について、起点から地点 i を通って終点へたどり着くすべての経路の長さの総和を出力するプログラムを作成せよ。ただし、経路の長さは経由した道の数とする。

入力
入力は以下の形式で与えられる。
N M
u1 v1
u2 v2
:
uM vM
１行目に地点の数 N(2≦N≦50)と道路の数 M(N-1≦M≦N×(N-1)/2)が与えられる。続く M 行に i 番目の道路の出発地点 ui と到着地点 vi(1≦ui＜vi≦N)が与えられる。

出力
出力は N 行である。i 行目に、地点 i を通る経路の長さの総和を出力する。

入出力例
入力例１3 3
1 22 3
1 3

出力例１323

起点から地点1を通って終点へと向かう経路は1→2→3,1→3の二つであり、その長さの総和は3となる。
起点から地点2を通って終点へと向かう経路は1→2→3の一つであり、その長さの総和は2となる。
起点から地点3を通って終点へと向かう経路は1→2→3,1→3の二つであり、その長さの総和は3となる。
入力例２6 8
1 21 3

出力例２141172 3
2 43 54 5711144 65 6問題９問題９ 倉庫番ロボット
倉庫番ロボット

（１０点）
（１０点）

アイヅ運送では倉庫番ロボットを開発しています。アイヅ運送の倉庫では、以下の平面図のように倉庫内の地点を座標(x,y)によって管理しています。倉庫内には、荷物が管理しやすいように、底面が正方形の棚を規則的に配置しています。倉庫内の地点の座標のペアで棚の南西隅と北東隅の位置を表すと、棚は(0,0)と(1,1)、(2,0)と(3,1)、…、(0,2)と(1,3)、(2,2)と(3,3)、…、というように、倉庫の端から端まで、0 以上の整数 i と j を使って(2i,2j)と(2i+1,2j+1)で表される正方形の領域を占めるように置かれています。

…

倉庫内の地点の座標

棚

倉庫内の棚の配置

(0,5)

…

北東

(0,1)

(1,1)

(0,0) (1,0)…

(5,0) …

倉庫番ロボットは、棚のないところでは自由に動くことができます。棚が置かれている領域内を通り抜けることはできませんが、サイズが小さいので棚の領域の境界上を通ることはできます。例えば、地点(0,0)から地点(4,3)へ最短距離で向かうには、以下のように動くことができます。
地点(0,0)から地点(4,3)へ最短距離で向かうときの倉庫番ロボットの動き方の例

(4,3)

(0,0)

倉庫番ロボット開発部のあなたは、ロボットに目標地点までの最短距離を計算する機能を付けようと考えています。

課題
倉庫番ロボットが現在いる地点と、目標の地点が与えられたとき、ロボットが目標の地点に到達するために移動する最短距離を出力するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
x0 y0 x1 y1
１ 行 に 倉 庫 番 ロ ボ ッ ト が 現 在 い る 地 点 の 座 標 x0,y0(0≦x0,y0≦300) と 、 目 標 の 地 点 の 座 標
x1,y1(0≦x1,y1≦300)が、すべて整数で与えられる。倉庫は与えられる座標の地点がすべて存在するような大きさの長方形であると考えてよい。ロボットが現在いる地点と目標の地点の座標は異なる(x0≠x1または y0≠y1)。

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

出力
ロボットが目標の地点に到達するための最短距離を、１行に実数で出力する。ただし、誤差がプラスマ
イナス 0.00001 を超えてはならない。この条件を満たせば小数点以下は何桁表示してもよい。

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

出力例１5.24264069

入力例２7 1 1 6

出力例２7.89292223

入力例３0 2 5 2

出力例３5※ C++のiostreamのcoutを使う場合、coutを行う前に以下の関数を呼び出せば、実数の形式で小数点以下６桁まで出力させることができる。
std::cout.setf(std::ios_base::fixed,std::ios_base::floatfield);

問題１０ Ｃｏｐｙ＆Ｓｕｍ

（１２点）
（１２点）

長さ N の数列 A と数列 B がある。A と B の i 番目の要素をそれぞれ ai と bi で表す。ただし、i は１からN までの整数である。これらの数列に対して以下の操作を行う。
copy(x, y, z) : ax, ax+1, …, ax+z-1 の値をそれぞれ、by, by+1,…, by+z-1 の値に置き換える。
sum(p, q) : ap + ap+1 + … + aq の値を出力する。

課題
数列 A，B と、いくつかの操作が与えられるとき、操作 sum の結果を出力するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N M
a1 a2 … aN
b1 b2 … bN
op1
op2:
opM
１行目に数列の長さN (1≦N≦200,000)と操作の数M(1≦M≦200,000)が与えられる。続く１行に数列Aのi番目の要素ai(0≦ai≦1,000,000,000)が整数で与えられる。続く１行に数列Bのi番目の要素bi(0≦bi≦1,000,000,000)が整数で与えられる。続くM行に、操作を示す情報opiが与えられる。各opiは以下のいずれかの形式で与えられる。
0 x y zまたは
1 p q
最初の文字が 0 の場合、操作 copy(x, y, z)を行うことを示す。ただし、1≦x,y≦N、1≦z、max(x,y)+z-1≦Nである。max(x,y)は x,y のうち大きい方を表す。最初の文字が 1 の場合、操作 sum(p, q)を行うことを示す。ただし、1≦p≦q≦N である。入力には、操作 sum が１回以上与えられる。

出力操作 sum が与えられるごとに、操作 sum の結果を１行に出力する。

入出力例
入力例１5 5
1 3 5 7 9
2 4 6 8 10
1 1 31 4 5

出力例１916960 4 1 2
1 1 3
1 4 5
入力例２6 5
1 2 3 4 5 6
2 4 8 16 32 64
1 1 60 1 4 3
1 1 60 3 1 3
1 1 6

出力例２2112768

問題１１ パスポート

（１３点）
（１３点）

地球にそっくりな新たな惑星が見つかりました。その惑星にはそれぞれ 1 から N までの番号がついた国があります。これらの国は鉄道路線と航空路線でつながっています。鉄道路線を使うと、どの国 i からでも、その隣の国 i+1 へ入国できます。i＜j を満たす国 i と国 j の間に航空路線が開設されていると、国 i から国 j へ直接入国できます。
各国に入国すると、あなたのパスポートにその国の頭文字を書いてもらえます。頭文字は A から Z までの英大文字です。この惑星にやってきたあなたは、国１に入国しました。国１に入国してから国 N まで移動する間に書かれた文字を、入国した順番に並べて作った文字列が、辞書式順序（英和辞書で単語が並んでいる順番）で最小になるという条件で旅行を計画しています。

課題国の頭文字と航空路線の情報が与えられる。入国した順に並べて作った文字列が辞書式順序で最小になるように経路を選んで旅行したとき、パスポートに書かれている文字列を出力するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N M
c1 c2 … cN
u1 v1
u2 v2
:
uM vM
１行目に国の数 N(2≦N≦300,000)と航空路線の数 M(0≦M≦300,000)が与えられる。2 行目に国 i の頭文
字 ci (ci は英大文字)が与えられる。続く M 行に i 番目の航空路線の出発国 ui(1≦ui＜N)と到着国 vi(ui＜vi≦N)が与えられる。

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

出力
パスポートに書かれている文字を並べて作った文字列を出力する。

入出力例
入力例１4 1A B C D
1 3

出力例１ABCD

入力例２6 2A M D U Z K

出力例２ADUZK

1 33 5

問題１２ 色付き山小屋

（１３点）
（１３点）

あなたは N 棟の山小屋と、山小屋の間をつなぐ道を管理しています。山小屋にはそれぞれ 1 から N までの番号がついています。道は全部で N-1 本あります。どの道も同じ長さで、どちらの方向にも通ることができます。また、どの山小屋からでも、いくつかの道を通っていくことで他のどの山小屋にも到達できます。
すべての山小屋には目印となる色が塗ってあります。登山者が同じ色の山小屋の間を移動できるように、どの山小屋にもその色と同じ色をした他の山小屋が少なくとも 1 つあります。あなたは、それぞれの山小屋について、その山小屋と同じ色の他の山小屋の中で最短の移動距離で到達できる山小屋を求めようとしています。

課題山小屋の色と、山小屋同士を直接つなぐ道の情報が与えられる。それぞれの山小屋について、その山小屋と同じ色の他の山小屋の中から移動距離が最短のものを見つけ、その最短の移動距離を出力するプロ
グラムを作成せよ。ただし、道の長さはすべて 1 とする。

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

出力
出力は N 行である。山小屋 i について、同じ色の他の山小屋の中から移動距離が最短のものを見つけ、その最短の移動距離を i 行目に出力する。

入出力例
入力例
81233

出力例
413312223311 241 32 42 54 65 77 8