Jump全体感想Dでバグはまり...。簡単に解けるはずの問題なのに...。いうデータセットで落とされているのかを確認しながらのデバッグが出来ないので、大ハマりしちゃうときもありますね。開き直ってFに進んだ方が良かったかもしれない。Switches$\mathbb{F}_2$上の線形代数っぽい問題。行列の階数を求めるのかな?などと。経験上、ABCコンテストのC問題はそんなに難しくない。そもそも電球が$10$個以下しかないので、全部シミュレーションするだけでした。あとは記号がごちゃごちゃしているのと戦う感じで。[0,1]の2値のN個組に関する探索。repeat=N)などと書くと、N重ループや再帰を使わず簡潔に書けます。range(1<<N):として2進表示をスイッチの状態とみなす方法もあります。equeue左右からいくつ取り出すかを固定すると最大価値が計算は簡単で、あとは全部調べるだけです。breakここで$N=1$のときに、全回収の場合が処理抜けしています。L+R=Nは処理に入れるように意識していたので、全回収の問題は解消したつもりになっていたため、見直しでもなかなか原因に辿り着けませんでした。WAと言ってもデータセットの大半ではACが出ていたので、バグとなりうる要素はかなり限られているはずでした。これに気づけなかったのはちょっとヘコむやつです。(リストのスライスがコピーか参照みたいなところの確認ばかりやっていた。Roadwork問題文を読むのに少し時間がかかる。出発座標は全部原点だったし、工事に引っかかった瞬間動くのをやめるのだった。要するに、それぞれの通行止めに引っかかる条件は、出発時刻に関する不等式で簡単に書けます。あとは、時刻の状態数が多いので、あらゆる時刻を扱うのではなく興味のある時刻だけを相手にしないといけません。時刻の左から、興味のある時刻だけを拾っていく実装。解説ではイベントソートという名前で紹介されていました。過去の経験から、とりあえずC++で書いて、コンテスト後に定数倍改善を検証して学ぶ方向で。■まず、タスクをheapqで管理して、順番にpopしていっていますが、そもそも動的な値の追加・削除をする必要はありません。listを一度だけソートして走査していく方針に変更。(定数倍)それでもどうにも不自然に遅いです。ここに原因がありました。N)だと思っていたけど、pythonのsetは遅いのね。2019(少し正確ではないかもしれませんが)C++のsetは、二分木ライクな構造をしており、挿入、検索等に$\log(\text{要素数})$の時間がかかります。ソート順が分かる構造なので、例えばiteratorの開始地点の値を見れば、$O(1)$で最小値が取得できます。pythonのsetはhash値に基づく実装であり、挿入、検索等は$O(1)$ですが、ソート順が分からず最小値の取得に$O(\text{要素数})$かかります。set型の基本的な知識を勘違いしていました。「アルゴリズムが分かっているのにTLEした」ときは、悔しいけど学習効果は高いですね。Jumpこれはコンテスト終了後に。出発点を含む等差数列。原点を含む等差数列は、交差$d$のものが大体$\lfloor\frac{N}{d}\rfloor$個。N)$で事前計算できます。同じ交差の等差数列を累積和でまとめれば、あとは容易。32分5完で114位でした。91分6完(3ペナルティ)で47位でした。形式的べき級数解説pythonその他タイトルとURLをコピーしました。