Cまで三完。
No.2666 Decreasing Modulo Nim
解説AC。
実験コードを書いたあと何も進まなかったけれど、「Aliceが最初にmの倍数を選択したらどうなるか？」と考えて、各A[i]をA[i]%mにしたものへ帰着できることは思いついて良かった。
それ以降は難しいが、mで割った余りに帰着した後なら実験でどうにかなったかもしれない。
2024年3月11日月曜日
トヨタ自動車プログラミングコンテスト2024#3（AtCoder Beginner Contest 344）
Eまで五完。
コンテスト後のツイート
トヨタ自動車プログラミングコンテスト2024#3（AtCoder Beginner Contest 344） Eまで。体感ではDが簡単でEが難しかったのだが、AC人数は配点通りといった感じなので自分の感覚がおかしかったよう。
— titia (@titia_til) March 9, 2024
C 全列挙
D DP
E 座標圧縮して、左右を管理。
F - Earn to Advance
解法ツイートを見たが、大体コンテスト中に考えていた内容だった。
所持金を増やす量を今まで通ったマスのmaxとして良いことには気付くのが重要。この値を使ってDPしようとも思ったのだが、dictでDPするのがちょっと不安で、座標圧縮しなくてはいけないのか？ などと考えてDPを避けてしまった。
さらに、DP[それまでのmax]に対する値として、行動回数と所持金を両方持たなくてはいけないのか？ 一次元化できるか？ と混乱してしまった。
公式解説を見ると、(行動回数, 所持金)が最も良い値を持てば良いらしいけど、気付きにくいね。行動回数は多いけどお金がたくさん……みたいなことは考えなくて良いことの証明は熨斗袋さんのツイートが分かりやすいと思います。
2024年3月10日日曜日
Codeforces Round 931 (Div. 2)
D2まで。Div.2で二桁順位を取ったのは久しぶり。2100には届かなかったがレートも回復して良かった。
コンテスト後のツイート
D1 高々長さ3で十分そう（未証明）。長さ2と長さ3（n,最大bitのみのやつ,m）をチェック
— titia (@titia_til) March 1, 2024
D2 実験すると、bit_countが偶数のときに勝てる。最大bitのみのやつを投げればOK
E. Weird LCM Operations
解説AC。
とりあえず、(x,y,z)という三つの数が互いに素なとき、この三つの数について処理を行うと、この三つの数について条件を満たすことに気付かなくてはいけなかった。
さらに、(x,x+1,x+2)でxが奇数のとき、この三つの数は互いに素なことを利用したい。
そう考えると、解説のような12で割った余りについて分類する方針にたどりつけそう。
基本的には、色々実験して解法を見つけていくしかなさそうなので、コンテスト中に解き切るのは困難だったか。
2024年3月7日木曜日
Codeforces Round 932 (Div. 2)
Dまで。
このコンテストで久しぶりに紫から薄橙へ戻れた。紫に落ちていたときは非常に辛かった。戻れて良かった。
コンテスト後のツイート
Codeforces Round 932 (Div. 2) Dまで。
— titia (@titia_til) March 5, 2024
A sかs[::-1]+sか。
B 全体のMEXと同じMEXとなる配列二つに分割できるか？
C bでソート。DP[i][x]をiまででx個作れるときのコストのに似たやつとする。コストではなく、そこまでのAの合計-B[i]を入れると判定できる。
D 図を描くとそれぞれ線分なので足し引き。
E. Distance Learning Courses in MAC
解法ツイートは見たけど、コンテスト中に考えていたことで合っていたのでほぼ自力AC。
上位bitから見ていく。
たとえば、あるクエリで、3つ目のbitについて考えているとき、[6,10]と、[9,11]のどちらから3つ目のbitを取るかというと、後者から取るべきである。そうすると、前者から7が取れるため、以下のbitは全て立てられることが分かる。
こういう風に考えると、[6,10]から3つ目のbitが立っているものを選択するときは、他に3つ目のbitが立っている区間がないときである。そして、そのときは（3つ目のbitが立っている）[8,10]だけ考えれば良いことが分かる。
なので、他に３つ目のbitが立っているときは処理を終わらせることにすれば、次、２つ目のbitを考えるときは、[6,10]を[8,10]に更新して考えて良い。
そうやって更新していくと、ここでこの区間からこのbitを選択するのか？ ということを考えずに済む。
というわけで、（こういう更新をした上で）
・ある区間にそのbitが立っているものが何個あるか？
・ある区間にそこで更新を終えてよいやつ（さっきの「7」みたいなものが含まれるやつ）があるか？
が分かれば良い。
これはセグ木を二つ使えばできる……と思って実装していたが、PyPyではTLEやMLEが取れなかった。
落ち着いて考えると、両方累積和で処理できますね。セグ木なしで実装してAC。
アイディアは間違っていなかったけど、コンテスト中はセグ木実装しか考えていなかったので、コンテスト中ACするのは困難でした。
2024年3月5日火曜日
yukicoder contest 419
A一完で終了。Codeforcesと被っていて、現在、Div.2もRatedなのでそっちに集中したかったという事情もあるが、Bは結構考えたけど思いついていなかった。
No.2656 XOR Slimes
隣接同士の合体しか考えなくて良いとどこかで見てAC。
言われれば証明するのは難しくなかったけど、全く思いついていなかった。二乗の制約から思いつくこともできそうですね。
2024年3月3日日曜日
AtCoder Beginner Contest 343
DまでとFの五完。Eが解けなかった。
コンテスト後のツイート
AtCoder Beginner Contest 343 Eが解けずGは見ていない。
— titia (@titia_til) March 2, 2024
C 全列挙
D 種類数と各数字が何回出ているかを持つ
E 全探索。体積の計算をちゃんと書いたつもりなのにWA二個が取れない。
F セグ木
E - 7x7x7
解法ツイートを見て理解、AC。
a1, a2, a3を(0, 0, 0)に固定し、b1～c3を０～20あたりで全探索したがダメ。E869120さんのこのツイートを見て、負の数も考えなくてはいけなかったと知った。
負の数も探索したらAC。
いや、難しいね。
正の範囲だけ探索して一般性を失わないのかと思ってしまった。立体感覚がないとこれに気付くのは難しそう。
G - Compress Strings
解説AC。
少し解説を見てしまったけど、自力で解けなければいけない問題でした。ただ、解こうとしたら、「S[i]とS[j]で何個重複させられるか？」を前計算するパートで文字列アルゴリズムが必要がない気がしたりして混乱……。
また、自明な枝狩りを入れないとTLEになってしまい、結構困りました。
2024年3月1日金曜日
Codeforces Round 930 (Div. 1)
A一完。Bに非常に苦労し、コンテスト後にACコードを書き終った。でも、時間ギリギリで通していたとしても多分レートはマイナスですね。
コンテスト後のツイート
Codeforces Round 930 (Div. 1) A一完でさようなら。
— titia (@titia_til) February 29, 2024
B 残り一時間くらいで計算方法は分かったのに答えが最後まで合わなかった。累積和の添え字？
A. Bitwise Operation Wizard
「? i i j j」
とすることで、P[i]とP[j]の比較ができることが重要。
・まず、最大値を探す。
・次に、最大値|P[i]が最大になるiを列挙する
・それらの中で最小のiを探す
として解いた。
B. Pinball
実験すると、
>で始まったのなら、次に反射するのは、それより右にある<、その次に反射するのは、一番はじめの>より左にある>……のようになる。
これで何個の文字とぶつかるかは、累積和と差分計算を頑張ればできる。
しかし、残り50分あたりで頑張ればできることに気付いたのに解き終わらなかった。コンテスト後15分くらいでようやくsampleが合い、それでACでした。
登録:
投稿 (Atom)