matsu7874/contest_20190209

contest_20190209

contest_20190209's Issues

02_group_photoのtester解作成

本番環境ですべての解をテストする

本番環境がどこかわかっていませんが(HackerRank?)、そこで想定解（想定誤答）を実行した際、想定通りのステータスになることを確認する

06_gas_stationのgenerator実装

07_path_on_triangleのtester解作成

05_treeの想定解実装

03_incense_stickのtester解作成

06_gas_stationの想定解実装

04_counting_shortest_pathの例を増やしてほしい

問題文に無向グラフとありますが、有向だと勘違いするとWAになるような例があったほうが親切かなと思いました。
1->3->2->4みたいな感じです。

一撃

問題文

射撃をします。
手前(F)と奥(B)にそれぞれN個の的が並んであり、あなたはそれぞれの的を撃ち抜くことでF_i, B_i点の点数が得られます。
あなたはとても射撃が上手なので、手前のi番目の的について奥の[i-K, i+K]の任意の的１つと同時に撃ち抜くことができます。
１発だけ打つとき得られる点数の最大値を出力せよ。

入力

N K
F_1 F_2 ... F_N
B_1 B_2 ... B_N

1 <= N <= 100000
0 <= K <= 100000

1 <= F_i <= 100000
1 <= B_i <= 100000

出力

max_score

サンプル

4 1
1 3 4 5
4 2 1 1

7

手前の2番めと奥の1番目の的を同時に撃ち抜くことで3+4点を獲得することができます。

各問題の配点を決める

下記の配点は順当でしょうか。

No.	問題	配点
1	B式A+B	100
2	集合写真	200
3	線香	300
4	最短経路	400
6	ガソリンスタンド	500
5	木	600
7	三角形	700
8	射的	800

08_one_shotのtester解作成

蛇状に折り返す文字列のmod5

このコンテストのハッシュタグは#yfkpoである。
集合写真を撮影する際、K*Y人のコンテスタントは1行あたりK人の長方形に整列し、各人の位置に応じてハッシュタグの文字のポーズを行う。

最も左上の人を(y,x) = (1,1)として、奇数行目は右方向に、偶数行目は左方向に順番に'y', 'f', 'k', 'p', 'o'を割り当てていく。行を跨いでも割り当てる文字はリセットされない、つまりジグザグ状の道の上に'y', 'f', 'k', 'p', 'o'を割り当てる。

あなたはY行目X列目に立っている。行うべきポーズのアルファベット('y', 'f', 'k', 'p', 'o'のいずれか)を出力せよ。

入力

K
Y X

1 <= Y <= 100
1 <= X <= K <= 100

出力

サンプル

サンプル1

6
4 2

k

K=6の場合のY=4, X=2は'k'である。

yfkpoy
fyopkf
kpoyfk
pkfyop

サンプル2

2
3 2

y

K=2の場合のY=3, X=2は'k'である。

yf
pk
oy

04_counting_shortest_pathsのtester解作成

重ならない

一筆書きABC

問題文

正三角形ABCが与えられます。

マス(i, j)からは下記の図の隣接6マスに移動可能です。

       (i-1, j-1)    (i-1, j  )
              \      /
(i  , j-1) <- (i  , j  ) -> (i  , j+1)
              /      \
       (i+1, j  )   (i+1, j+1)

同じマスを2回以上通らないようにA(0,0)->B(N-1, 0)->C(N-1, N-1)を移動するとき、最小のコストを求めよ。
※A,B,Cの３マスについて、コストが０であることが保証される。

入力

N
c_(0,0)
c_(1,0) c_(1,1)
...
c_(N-1,0) ... c(N-1,N-1)

制約

• 1 <= N <= 10^3
• 1 <= c <= 10

出力

文字列を一行で出力せよ。
末尾は改行せよ。

サンプル

sample 1

3
0
4 1
0 2 0

6

同じマスを2回通過せずにABCの順に結ぶ経路は下記の1通りであり、コストは4+2=6となります。
(0,0)->(1,0)->(2,0)->(2,1)->(2,2)

sample 2

5
0
9 1
9 1 9
1 5 1 1
0 1 1 9 0

12

01_b_calcのtester解作成

07_path_on_triangleのgenerator実装

2次元座標で距離d以下の辺のみを使ったダイクストラの経路復元

問題文

N箇所のガソリンスタンドの座標が与えられます。ガソリンスタンド1からスタートして、ガソリンスタンドNに到着する経路を出力してください。
ただし、あなたの車は燃料を満タンに積んでも距離Dちょうどまでしか移動することができないため、距離Dより離れたガソリンスタンド間は直接移動することができません。
言い換えるとdistance(i,j) <= Dを満たすi,j間のみ移動が可能です。
また、同じガソリンスタンドを複数回使用することはできません。

※入力について、条件を満たす経路がただ１つだけ存在することが保証されます。

入力

N D
Y_1 X_1
Y_2 X_2
...
Y_N X_N

2 <= N <= 1000
0 <= D <= 100
0 <= Y <= 100000
0 <= Y <= 100000
Y,Xは非負整数。

サンプル

サンプル1

3 1
0 0
1 0
1 1

1
2
3

サンプル2

7 3
5 5
2 2
4 1
2 5
5 6
10 10
0 0

1
4
2
7

04_counting_shortest_pathの出力が大きくなりうる。

制約がM <= 10^4の範囲内では、私が以前指摘した入力生成を用いることで、C++などの言語ではオーバーフローする入力を作ることができる。
次のうちのどちらかを検討してほしい

• 制約を変更し、M <= 10^3にする
• 答えの数値に制限を設け、これを問題文で明示する。

08_one_shotの想定解実装

06_gas_stationのtester解作成

ある点から全ての点への距離の合計を求める

問題文

N頂点の0を根とした無向木が与えられる。各辺の長さは1である。
各頂点について、全ての頂点への距離の合計を出力せよ。

入力

N
p_1
p_2
...
p_n-1

ノード数Nに続いて、各頂点の親ノードが与えられる。
各iについてp_i < i

出力

d_0
d_1
...
d_N-1

各クエリの頂点からの距離の合計を各行で答えよ。

サンプル

サンプル1

3
0
1

3
2
3

入力は0-1-2に対応する。
ノード0から各ノードへの距離の合計は1 + 2 = 3。
ノード1から各ノードへの距離の合計は1 + 1 = 2。
ノード2から各ノードへの距離の合計は2 + 1 = 3。

線香

問題文

燃える速度の異なるN本の線香に一斉に火をつけたところ、線香1が最初に燃え尽きた。
火をつける前の線香iの長さはS_iであり、線香1が燃え尽きた瞬間の線香i長さはT_iであった。

線香1の「単位時間あたりに燃える長さ」を1として、線香iの「単位時間あたりに燃える長さ」を既約分数で出力せよ。ただし分母が1になる場合は n 1の形で出力せよ。

入力

N
S_1 S_2 ... S_N
T_1 T_2 ... T_N

2 <= N <= 100
1 <= S_1 <= 10000
T_1 = 0
i >= 2について1 <= T_i < S_i <= 10000

出力

各i(1<=i<=N)について分子_i 分母_iの組を出力せよ

1 1
n_2 d_2
...
n_N d_N

サンプル

5
24 24 23 14 52
0 12 18 6 16

1 1
1 2
5 24
1 3
3 2

05_treeのtester解作成

07_path_on_triangleの想定解実装