はいどうも電電です．
今回は昨日参加したAtCoderの東京海上日動2020のコンテストにおいてC問題に２時間使った挙句解けなかったので解説を書いていきたいと思います．(いもす法まで浮かんだのにどうしてできなかった)
A - Nickname
あなたは同じ授業を受けている男性に名前を尋ねました。彼は S と名乗りました。S は英小文字からなる長 3 以上 20 以下の文字列です。 あなたは S から適当に連続する 3 文字を選んで、彼のあだ名とすることにしした。彼のあだ名として適切な文字列を 1 つ出力してください。
はいこれは，出入力ちゃんとできますかという問題ですね．名前となるSを入力として受け取って頭から3文字取れば終わりです． 一応僕の回答を載せときます．頭からじゃなくて後ろから3文字でも大丈夫です．
S = str(input()) print(S[3:])
B - Tag
2人の子供が数直線上で鬼ごっこをしています．鬼役の子供は今座標Aにいて1秒あたり距離V移動することができます．また鬼から逃げている子供は今座標Bにいて1秒あたり距離W移動することができます． 鬼役の子供は相手と同じ座標にいるとき，相手を捕まえることができます．今からT秒後に鬼役の子供がもう一方の子供を捕まえることができるかどうかを 判定してください．ただし，2人の子供は最適に動くとします．
鬼ごっこで鬼が追いかけられる側に追いつくかどうかの問題ですね． 問題文をきっちり読めば追いかける側がちょうど追いつく必要はなくて，一瞬でもすれ違えばいいので，単純に初期の位置の差分と速度の差分を使って大小比較すればいい問題でした．また，答えが"YES", "NO"と全て大文字になっている点なども少しミスしやすいところだったのかもしれません． 式としては
|A - B|と (V - W) * Tを比較して左辺が大きければNO,右辺が大きければYESと答えれば大丈夫ですね．
def LI(): return list(map(int, sys.stdin.readline().split())) A,V = LI() B,W = LI() T = int(input()) if abs(A-B) <= (V-W) * T: print("YES") else print("NO")
C - Lamps
これが個人的に取れるべき問題だったと思いました．これが解けなかったのは精進が足らん気がしますね． 問題をみていきましょう．
まず行ったのはnumpyを使った小規模な実装でした．
N, K = LI() A = LI() """ 明るさが一定値を超えると計算しなくて良い 一定？d > math.floort(N/2) """ lamps = [[0] * N] * (K + 1) lamps[0] = A lamps = np.array(lamps) for i in range(K): if lamps[i][-1] == N: if np.all(lamps[i] == np.ones(N) * N): ans = [str(N)] * N print(" ".join(ans)) sys.exit() for j in range(N): tmp = lamps[i][j] if tmp == 0: lamps[i+1][j] += 1 else: lamps[i + 1][max(0, j - tmp):min(N + 1, j + tmp) + 1] += 1 ans = lamps[-1].tolist() ans = map(str, ans) print(" ".join(ans))
ただこれだと明らかに計算量が多いのでいろんなケースを試してみました． すると以下のような状態変化をすることがわかります．
[0 0 0] -> [1 1 1] -> [2 3 2] -> [3 3 3] [0 0 0 0] -> [1 1 1 1] -> [2 3 3 2] -> [3 4 4 3] -> [4 4 4 4] ... [0 0 0 0 0 0 0] -> [1 1 1 1 1 1 1] -> [2 3 3 3 3 3 2] -> [4 5 6 5 6 5 4] -> [6 6 7 7 7 6 6] -> [7 7 7 7 7 7 7]
この結果を見ると結構早い段階で各ランプの光の強さが上限に達することがわかりました．
何回かやってるとこの天井に達する回数がだいたいlogNになるので50回くらい操作を行うと全部が上限値になるようです．
(解説で41回という数字が出ていて謎に思っていましたが，実験してみたところこの41回という数字は，全てが0で大きさが制約の最大の時全ての明かりの強さが上限に達するまでにかかる回数のようです．)(ご指摘いただいたArkさんありがとうございます．)
これでK >50以上のときは計算量を気にしないでいいことがわかりましたが，問題は一回の操作にまだO(N*2) かかってるので最大の計算量はO(50*N *2)となり，まだ厳しいということです． もう少し一回の操作の計算量を減らさないといけません．
ここでimos法が使えます． imos 法は このように数列のある範囲に一様な足し算や引き算の操作を行う時に一回累積和の差分を示すテーブルを持つことによって計算量をO(N**2) -> O(N)に減らせるという方法です．
例えば今ここに a = [0,0,0,0,0] があり， このa[0:3],a[1:2],a[0:4],a[1:3]にそれぞれ1を足したい時，愚直に行うと
a = [0,0,0,0] B = [[0,3], [1,2], [0,4], [1,3]] for b in B: left, right = b for i in range(left, right): a[i] += 1 print(a)
であり，計算量はO(N**2)ですが，一度差分のテーブルを計算してやると
a = [0,0,0,0] B = [[0,3], [1,2], [0,4], [1,3]] table = [0,0,0,0] for b in B: left, right = b table[left] += 1 if right >= len(table): continue table[right] -= 1 print(table) tmp = 0 for i in range(len(a)): tmp += table[i] a[i] += tmp print(a)
とすることで計算量をO(N)に落とすことができます．
imos法についてより説明すると
最初の計算は以下のような表を順に計算しています．
この時にa[0:3] += 1の部分についてだけ考えると，これは
a[0] += 1 a[1] += 1 a[2] += 1
という計算になります．この時一時変数tmp = 0をおき，このtmpの値が計算した後のaの値になるするとtmpが変化しているのはa[0]になる時とa[3]になる時です． つまりa[0]の時tmp += 1, a[3]の時tmp -= 1となれば，
tmp += 1 a[0] = tmp a[1] = tmp a[2] = tmp tmp -= 1 a[3] = tmp
となります．
これを全ての計算に当てはめることで計算量をO(N)に落とすことができます．
さて回答の方はimos法を用いてこのようになりました．
def LI(): return list(map(int, sys.stdin.readline().split())) N, K = LI() A = LI() if K > 50: print(" ".join([str(N) for i in range(N)])) sys.exit() for i in range(K): A_new = [0 for i in range(N)] imos_table = [0 for i in range(N)] for j in range(N): # ここで一度状態の差分についてをimos_tableに保存 left = max(0, j - A[j]) right = j + A[j] + 1 imos_table[left] += 1 if right >= N: pass else: imos_table[right] -= 1 # tmp を使って前から順に状態を計算していく tmp = 0 for j in range(N): tmp += imos_table[j] A_new[j] += tmp A = copy.deepcopy(A_new) print(" ".join(map(str, A)))
これをPyPyで提出すればACです．
最後に
この問題atcoder problemsによれば水色のeasyみたいなので解けるべきでしたね．imos法使えるかちょっと頭よぎったんですけど理解が浅かったみたいです．情報学の大学院に入る時にAtCoder水色を目標にしてたんですけど，もうちょっと精進しないとダメですね．頑張ります．
ほなまた．
