DISCO presents ディスカバリーチャンネルコードコンテスト2019 本戦

A - レース (Race)

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点: 300 点

問題文

高橋君はペンギンのレース場を作りました。

レース場は N 個の正方形のマスが西から東に一列に並んだ形状をしています。
これらのマスの状態は文字列 S により表され、西から i 番目のマスの状態は S の i 文字目が - なら「雪」、> なら「氷」です。
また、スタート地点は西端のマスの西の端、ゴール地点は東端のマスの東の端です。

高橋くんのペンギンが、スタート地点からゴール地点を目指して東に進みます。
ペンギンは、雪マスを 1 マス通過するのに 1 秒、氷マスを 1 マス通過するのに 1/(k+2) 秒の時間を要します。
ここで、k はその氷マスの直前に連続して存在する氷マスの個数です。
例えば、雪マスの直後に氷マスが 2 つ存在する場合、1 つ目の氷マスは 1/2 秒、2 つ目の氷マスは 1/3 秒で通過します。

ペンギンがスタートする前に、高橋君は雪マスのうち 1 つを氷マスに変えることができます。
ペンギンがスタート地点を出発してからゴール地点に到達するまでに最小で何秒かかるでしょうか？

制約

3 \leq N \leq 100 \ 000
S は -, > で構成される長さ N の文字列
S_1 = S_2 = S_{N-1} = S_N = -
S において、- は必ず別の - と隣接して現れる

入力

入力は以下の形式で標準入力から与えられる。

N
S

出力

ペンギンがゴール地点に到達するのに要する秒数の最小値を出力せよ。
ジャッジの出力との相対誤差または絶対誤差が 10^{-8} 以下であれば正解となる。

入力例 1

5
-->--

出力例 1

3.83333333333333

西から 4 番目のマスを雪マスから氷マスに変えると、レース場は -->>- となります。
このとき、ペンギンは西から 1, 2, 3, 4, 5 番目のマスの通過にそれぞれ 1, 1, 1/2, 1/3, 1 秒、合計で 23/6 = 3.83333333... 秒を要し、これが最短です。

入力例 2

7
-------

出力例 2

6.5

どのマスを雪マスから氷マスに変えても、ペンギンは 13/2 = 6.5 秒でゴールします。

入力例 3

10
-->>>-->--

出力例 3

6.78333333333333

西から 2 番目または 6 番目のマスを雪マスから氷マスに変えると、ペンギンは 407/60 = 6.783333333... 秒でゴールすることができます。

B - 大吉数列 (Array of Fortune)

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点: 600 点

問題文

以下の条件を満たす長さ N の数列 A = {A_1, A_2, A_3, ..., A_N} を「大吉数列」とします。

A には 1 以上 N 以下の整数がちょうど 1 回ずつ出現する。
a_i \geq a_j + K を満たす (i, j) の組 (i < j) がちょうど R 個存在する。

数列君は、大吉数列を見つけようと思いましたが、すぐには見つけられませんでした。
彼のために、大吉数列を 1 つ構成してください。
大吉数列が 1 つも存在しない場合は、No Luck と出力してください。

制約

1 \leq N \leq 100 \ 000
1 \leq K \leq N - 1
0 \leq R \leq N \times (N - 1) / 2
入力値はすべて整数

小課題

この問題は小課題に分けられている。

小課題 1 [200 点]

N \leq 100 を満たす。

小課題 2 [400 点]

追加の制約はない。

入力

入力は以下の形式で標準入力から与えられる。

N K R

出力

大吉数列が存在しない場合、No Luck と出力せよ。
大吉数列が存在する場合、大吉数列として考えられるものを以下の形式で 1 つ出力せよ。

A_1 A_2 A_3 ... A_N

大吉数列が複数存在する場合は、そのうちのどれを出力しても正解となる。

入力例 1

5 2 4

出力例 1

3 4 1 5 2

数列 A = {3, 4, 1, 5, 2} に対して、a_i \geq a_j + 2 を満たす (i, j) の組 (i < j) は以下のちょうど 4 個存在します。

(i, j) = (1, 3), (2, 3), (2, 5), (4, 5)

よって、数列 A は大吉数列の一つです。
この他に、例えば以下のような出力も正解となります。

5 1 3 4 2

入力例 2

7 1 21

出力例 2

7 6 5 4 3 2 1

入力例 3

10 3 22

出力例 3

6 7 8 9 10 1 2 3 4 5

入力例 4

10 5 45

出力例 4

No Luck

C - 光の反射 (Reflection of Light)

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点: 700 点

問題文

2 次元平面上に、原点 (0, 0) を中心とする半径 1 の円形の部屋があります。
その内部に、点 (X, Y) を中心とする半径 R の円形の柱が建てられています。

DISCO 君は、光源を部屋の内部であって柱の外部であるような点 (S_X, S_Y) に設置しました。
この点から、光がすべての方向に一直線に進みます。
光は、部屋の外周または柱に当たると反射されずに吸収されます。

彼は、部屋の外周上のうちどのくらいの割合の部分に、一定の個数以内の鏡を使って光を届けられるのかを知りたくなりました。
t = 0, 1, 2, ..., K のそれぞれに対し、以下の質問に答えてください。

鏡を使うことで、光が進む方向を t 回まで自由に変えることができるとしたときに、光が到達しうる部屋の外周上のすべての点を白く塗る。
このとき、部屋の外周上の白く塗られた部分の割合を求めよ。(すなわち、部屋の外周上の白く塗られた部分の長さを l として l / 2π を求めよ。)

制約

|X|, |Y|, |S_X|, |S_Y| < 1
0.01 \leq R < 1
1 \leq K \leq 10
柱は部屋の内部にあり、柱から部屋の外周までの距離は 0.05 以上である
光源は部屋の内部にあり、光源から部屋の外周までの距離は 0.01 以上である
光源は柱の外部にあり、光源から柱までの距離は 0.01 以上である
X, Y, R, S_X, S_Y の値は最大で小数点以下 7 桁まで与えられる
K は整数

入力

入力は以下の形式で標準入力から与えられる。

X Y R
S_X S_Y
K

出力

K + 1 行出力せよ。i 行目 (1 \leq i \leq K + 1) に t = i - 1 のときの質問に対する答えを出力すること。
すべての質問について、ジャッジの出力との絶対誤差が 10^{-4} 以下ならば正解となる。

入力例 1

0.0 0.0 0.6
0.0 0.7
2

出力例 1

0.467404563822388
1
1

t = 0 のとき、部屋の外周上の光が到達しうる範囲は点 (0.99476..., 0.10222...) と点 (-0.99476..., 0.10222...) を結ぶ長さ 2.93678... の円弧で、この長さが外周全体に占める割合は 2.93678... / 2π = 0.46740... です。

t = 1 のとき、光の方向を適切に変えることで、t = 0 のときに到達できなかったすべての点に光を到達させることができます。

入力例 2

0.3 0.3 0.4
0.9 0.0
1

出力例 2

0.623158068351223
1

入力例 3

0.00 0.00 0.90
0.65 0.65
3

出力例 3

0.208804270061789
0.495936856319201
0.783069442576613
1

入力例 4

-0.2018 -0.1190 0.6858
-0.5000 -0.7777
3

出力例 4

0.266193331431572
0.767297626518897
1
1

D - DISCO!

実行時間制限: 13 sec / メモリ制限: 1024 MB

配点: 700 点

問題文

高橋君は文字列 S を書きました。次の Q 個の質問に答えてください。

質問 q (1 \leq q \leq Q): 整数 L_q, R_q が与えられる。S_i = D, S_j = I, S_k = S, S_l = C, S_m = O であるような組 (i, j, k, l, m) (L_q \leq i < j < k < l < m \leq R_q) は何個存在するか？その個数を 2^{32} で割った余り を求めよ。

制約

S は D, I, S, C, O から構成される長さ 1 \ 000 \ 000 以下の文字列
1 \leq Q \leq 100 \ 000
1 \leq L_q \leq R_q \leq |S|
L_q, R_q は整数

入力

入力は以下の形式で標準入力から与えられる。

S
Q
L_1 R_1
L_2 R_2
L_3 R_3
:
L_Q R_Q

出力

Q 行出力せよ。q 行目に質問 q に対する答えを出力すること。

入力例 1

DDDDDDISCOOOOOO
7
6 10
5 11
4 12
3 13
2 14
1 15
1 8

出力例 1

入力例 2

DDDIIISSSCCCOOO
12
1 12
1 13
1 14
1 15
2 12
2 13
2 14
2 15
3 13
3 14
3 15
4 15

出力例 2

E - 飾りつけ (Decoration)

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点: 1200 点

問題文

来年で設立 80 周年を迎える D 社は、記念としてオフィスの前にグラフを飾ることにしました。
このグラフは、以下の条件を満たす必要があります。

重み付き有向グラフである。
頂点の数を N、辺の数を M として、頂点は 1, 2, 3, ..., N と番号付けられている。
N \leq 70 である。
i 本目の辺が頂点 u_i から v_i への重み w_i の有向辺であるとすると、u_i < v_i, 0 \leq w_i \leq 2 \ 000 (w_i は整数) である。また、i \neq j ならば (u_i, v_i) \neq (u_j, v_j) である。
頂点 1 から N へのどのパスの長さも、p_1, p_2, p_3, ..., p_Q のいずれかである。なお、パスの長さとは、そのパスに含まれる辺の重みの総和である。
頂点 1 から N へのパスのうち、長さがちょうど p_1 であるものが 1 個以上、長さがちょうど p_2 であるものが 1 個以上、長さがちょうど p_3 であるものが 1 個以上、…、長さがちょうど p_Q であるものが 1 個以上存在する。

このようなグラフを 1 個構築してください。
頂点数が少ないほど、飾りつけにかかる費用が減るので社長も喜ぶでしょう。

制約

1 \leq Q \leq 2 \ 000
1 \leq p_1 < p_2 < p_3 < ... < p_Q \leq 2 \ 000
入力値はすべて整数

得点

提出の得点は、以下のように計算される。

一つのテストケースでも不正解であった場合、その提出の得点は 0 点となる。
すべてのテストケースに正解した場合、それらに対して用いられた N の最大値を L として、提出の得点は以下のように決定される。
- 66 \leq L \leq 70 のとき、600 点
- 61 \leq L \leq 65 のとき、800 点
- 54 \leq L \leq 60 のとき、990 + 30 \times (60 - L) 点
- L \leq 53 のとき、1200 点

なお、この問題の制約下で、任意の入力に対して N \leq 53 であるような条件を満たすグラフが必ず存在することが証明できる。

入力

入力は、以下の形式で標準入力から与えられる。

Q
p_1 p_2 p_3 ... p_Q

出力

条件を満たすグラフの一つを以下の形式で出力せよ。

N M
u_1 v_1 w_1
u_2 v_2 w_2
u_3 v_3 w_3
:
u_M v_M w_M

条件を満たすグラフが複数存在する場合は、そのうちのどれを出力しても正解となる。

入力例 1

3
1 2 5

出力例 1

この出力は、以下のグラフに対応します。

頂点 1 から N = 5 へのパスは以下の 3 通りです。

1 → 2 → 5: 長さ 1 + 0 = 1
1 → 3 → 5: 長さ 2 + 0 = 2
1 → 4 → 5: 長さ 5 + 0 = 5

これらは、Q = 3, p_1 = 1, p_2 = 2, p_3 = 5 に対して問題文中の条件を満たします。
この出力の他に、例えば以下の出力も正解となります。

入力例 2

4
1 2 3 4

出力例 2

入力例 3

7
1 3 7 9 11 14 16

出力例 3