[AtCoder 参加感想] 2019/05/26:ABC128

	A	B	C	D	E	F
問題文	■	■	■	■	■	■
自分の提出	■	■	■	■	■
結果	AC	AC	AC	WA	AC

全体感想
問題C – Switches
問題D – equeue
問題E – Roadwork
問題F – Frog Jump

全体感想

Dでバグはまり…。簡単に解けるはずの問題なのに…。
どういうデータセットで落とされているのかを確認しながらのデバッグが出来ないので、大ハマりしちゃうときもありますね。開き直ってFに進んだ方が良かったかもしれない。

問題C – Switches

$\mathbb{F}_2$上の線形代数っぽい問題。行列の階数を求めるのかな？などと。経験上、ABCコンテストのC問題はそんなに難しくない。そもそも電球が$10$個以下しかないので、全部シミュレーションするだけでした。あとは記号がごちゃごちゃしているのと戦う感じで。

[0,1]の2値のN個組に関する探索。pythonでは、

itertools.product([0,1], repeat=N)

などと書くと、N重ループや再帰を使わず簡潔に書けます。他に、

for i in range(1<<N):

として2進表示をスイッチの状態とみなす方法もあります。

問題D – equeue

左右からいくつ取り出すかを固定すると最大価値が計算は簡単で、あとは全部調べるだけです。

for L in range(N):
  for R in range(N):
    if L+R > N:
      break

ここで$N=1$のときに、全回収の場合が処理抜けしています。L+R=Nは処理に入れるように意識していたので、全回収の問題は解消したつもりになっていたため、見直しでもなかなか原因に辿り着けませんでした。

WAと言ってもデータセットの大半ではACが出ていたので、バグとなりうる要素はかなり限られているはずでした。これに気づけなかったのはちょっとヘコむやつです。悔しい。
（リストのスライスがコピーか参照みたいなところの確認ばかりやっていた。終了後すぐに気づくし）

終了後の提出 → ■

問題E – Roadwork

問題文を読むのに少し時間がかかる。出発座標は全部原点だったし、工事に引っかかった瞬間動くのをやめるのだった。思ったより易しい。

要するに、それぞれの通行止めに引っかかる条件は、出発時刻に関する不等式で簡単に書けます。あとは、時刻の状態数が多いので、あらゆる時刻を扱うのではなく興味のある時刻だけを相手にしないといけません。

時刻の左から、興味のある時刻だけを拾っていく実装。解説ではイベントソートという名前で紹介されていました。

TLE。

過去の経験から、とりあえずC++で書いて、コンテスト後に定数倍改善を検証して学ぶ方向で。

最初に書いたpythonコード → ■

まず、タスクをheapqで管理して、順番にpopしていっていますが、そもそも動的な値の追加・削除をする必要はありません。listを一度だけソートして走査していく方針に変更。（定数倍）

それでもどうにも不自然に遅いです。ここに原因がありました。

answer[b] = min(se) # se は set 型

C++のsetの最小値はO(log N)だと思っていたけど、pythonのsetは遅いのね。listより遅いO(N)なのかな？ pic.twitter.com/0Z5wMurngm
— maspy (@maspy_stars) May 26, 2019

（少し正確ではないかもしれませんが）C++のsetは、二分木ライクな構造をしており、挿入、検索等に$\log(\text{要素数})$の時間がかかります。またソート順が分かる構造なので、例えばiteratorの開始地点の値を見れば、$O(1)$で最小値が取得できます。

一方、pythonのsetはhash値に基づく実装であり、挿入、検索等は$O(1)$ですが、ソート順が分からず最小値の取得に$O(\text{要素数})$かかります。

つまり、定数倍どころか計算量オーダーが$O(N^2)$でTLEしていたことが発覚ｗｗ

python set型の基本的な知識を勘違いしていました。「アルゴリズムが分かっているのにTLEした」ときは、悔しいけど学習効果は高いですね。

最終的にこうなりました → ■

問題F – Frog Jump

これはコンテスト終了後に。コンテスト中は、D,Eで消耗してほとんど触れなかったが、難しい問題ではない。

右移動着地点全体は終着点を含む等差数列。左移動着地点全体も出発点を含む等差数列。

原点を含む等差数列は、交差$d$のものが大体$\lfloor\frac{N}{d}\rfloor$個。
$\sum_{d=1}^{N}\lfloor\frac{N}{d}\rfloor$は積分$\int_1^N\frac{N}{x}dx$で近似できて、$O(N\log N)$。したがって、一つ一つの等差数列の和を$O(1)$で計算できるなら、全ての等差数列を$O(N\log N)$で事前計算できます。同じ交差の等差数列を累積和でまとめれば、あとは容易。

提出 → ■