東京海上日動　プログラミングコンテスト2020

#Atcoder #Python #競プロ

東京海上日動　プログラミングコンテスト2020

東京海上日動プログラミングコンテスト2020

参加日 2020/06/14

参加したので記録として残す。
問題文はタイトルのリンク参照。

(コードブロックの中のシンタックスハイライト効かない?)

A

見たまま。
どこでも良いので先頭から3文字にした

S = input()
print(S[:3])

Shortest目指して1行で書くならこうだったなと。

print(input()[:3])

早ければ早いだけ良かったので速度重視ということで。
今回は問題開く時間, 問読み時間も含めて27秒で行けた。だいぶいい感じ。

B

追う側が追われるより早い必要があってさらに時間内に追いつければいい。
ということは速度の差 / 距離の差 <= 制限時間とすればいい。

距離の差が0になっちゃうと動かないのでその条件も追加した。

A,V = map(int, input().split())
B,W = map(int, input().split())
T = int(input())

print('YES' if V-W != 0 and 0 <= abs(A-B)/(V-W) <= T else 'NO')

もっと短くエラー無く書こうとするなら割り算を消した式(速度の差 <= 制限時間 * 距離の差)に変えればよかった。

A,V = map(int, input().split())
B,W = map(int, input().split())
T = int(input())

print('YES' if abs(A-B) <= (V-W)*T else 'NO')

問題解いてる量が多いほど誤読したかも?
1秒毎に今の位置からV,Wだけ動くって読んじゃうと追い越しちゃったらどうするんだ的な疑問が出てきてハマってたかも。怖い。

C

今まで本番で解けなかった500点問題。初めて解けたのが嬉しすぎてこのブログ開設したきっかけになった。

最初の考察

愚直にやるなら?
- N <=10^5, K<=10^5
- 次のステップでランプが何個のランプから照らされているかを先頭から見るのをK回繰り返す方法だとどうか。
  - O(N*N*K)になる
  - 愚直な実装だとまず間に合わない
- どうやったら計算量減らせるかを考えよう
法則性を探してみる
- サンプルから探す
  - 0も次のステップでは1以上になることに気づく(自分自身で照らしているってことかなと納得)
  - 次のステップで照らされる数が減ることはないことに気づく
  - 照らされる数は最大でもランプの数(N)なことに気づく
    - つまり[N,N,...N]になったらそれ以上変化しない
  - 実験してみる

実験コード

N, K = map(int, input().split())
A_list = np.array(list(map(int, input().split())))

# 愚直にやってパターンを見つけてみる
for k in range(K):

    B_list = []
    for i in range(N):
        tmp = 0
        for j in range(N):
            tmp += 1 if A_list[j] >= abs(i-j) else 0
        B_list.append(tmp)
    print(k+1, B_list)
    A_list = B_list

実行1

サンプルケースと同じNとAのリストで4回回してみる。

1 [1, 2, 2, 1, 2]
2 [3, 3, 4, 4, 3]
3 [4, 5, 5, 5, 4]
4 [5, 5, 5, 5, 5]

1でサンプル1の結果と合っている。
2でサンプル2の結果と合っているので動きとしては正しそう。

実行2

Nを大きくして更にパターンが見えないか試す。

# 入力
# N = 100, K = 100
# A_list = [0]*100
# A_list[0] = 1

1 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] ... [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
2 [2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3] ... [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2]
3 [4, 5, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7] ... [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 6, 5, 4]
4 [8, 9, 10, 11, 12, 12, 13, 13, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15] ... [15, 15, 15, 15, 15, 15, 15, 15, 15, 14, 14, 14, 13, 13, 12, 12, 11, 10, 9, 8]
5 [16, 17, 18, 19, 20, 21, 22, 23, 24, 24, 25, 25, 26, 26, 27, 27, 28, 28, 28, 29] ... [29, 28, 28, 28, 27, 27, 26, 26, 25, 25, 24, 24, 23, 22, 21, 20, 19, 18, 17, 16]
...
11 [95, 96, 97, 97, 98, 98, 99, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100] ... [100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 99, 98, 98, 97, 97, 96, 95]
12 [98, 98, 99, 99, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100] ... [100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 99, 99, 98, 98]
13 [99, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100] ... [100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 99]
14 [100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100] ... [100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100]
...
99 [100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100] ... [100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100]
100 [100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100] ... [100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100]

14回の時点で収束している。

更に試してN=10の時は6回, N=100の時は14回, N=1000の時は22回なことが分かった。
N=10000以上は手元の環境だと遅すぎ終わるのが待てなかったがおそらくN=10000で30回程度, N=100000で50回未満と予想がついた。

考察2

Kステップ繰り返す部分は最大でも50回程度やれば十分なことがわかったので計算量がO(N*N*50)程度にできて計算量減らせた嬉しい。
しかしまだ遅いのでN*Nの部分を減らしたい
imos法が使えそう
先頭からと後ろから2回imos法やればO(2N40)程度にできるのでは?
- 片方向に動くからすでに書き換えている値を更に書き換えるのは遅そうだなと思っての発想
A[i] = iより前のランプで照らされる数 + iより後のランプで照らされる数 + 1

実装

def main():
    N, K = map(int, input().split())
    A_list = list(map(int, input().split()))

    for _ in range(min(K,50)):
        e_list_1 = [0] * N
        l_1 = [0] * N
        v = 0
        for i,a in enumerate(A_list):
            l_1[i] = v 
            e_list_1[min(i + a, N-1)] += 1
            v = v + 1 - e_list_1[i]

        e_list_2 = [0] * N
        v = 0
        for _i,a in enumerate(A_list[::-1]):
            i = N-1-_i
            A_list[i] = l_1[i] + v + 1
            e_list_2[max(i-a, 0)] += 1
            v = v + 1 - e_list_2[i]

    print(*A_list)
if __name__ == "__main__":
    main()

Python3だとTLE出したのでPyPy使ったらACできた。嬉しすぎて夜中なのに叫んじゃった。
コンテスト中にPythonで通してる人3人しかいなかった。すごすぎ