BとEの二完。あとはFを考えていたが分からず。Eは上手い方法が分からず、a,b全探索でcの範囲を定め、その後、ミラー・ラビン素数判定法を使って判定、で通ってしまった。良かったのかなぁ。
No.3483 A Forbidden Fruit
自力AC。
自力ではあるのだけど、たとえば、「M個の中からr個選んだとき、外れ（の一個）が含まれない確率」が1-r/Mであることも計算しないと気付かなかった。
確率について直感が働いてないなぁ。
2026年3月28日土曜日
2026年3月26日木曜日
AtCoder Regular Contest++ 216
一問も解けず。
コンテスト後のツイート
AtCoder Regular Contest++ 216 AとCを行ったり来たりしていたが一問も解けなかった。
— titia (@titia_til) March 22, 2026
A ランレングス圧縮したとき、xをa+1+bに交互に変換できる、という操作と言い換えたが上手くいかない。
C 小さい数字から考えたい。0と1だけでも、0の個数の偶奇が絡んで上手くいかない。
A - Reversi 3
解説AC。
既出で解いたことのある問題だった。
時間が経っているので忘れているのは仕方ないし、この解法を思い付くのは難しいと思うので仕方ない面もあるが、初手の隣接xorを取るところすら思いつけなかったのはまずかった。
隣接xorを取った後の処理も思いつきにくいが、偶奇に着目するのはやってみなくてはいけない。
定石の組み合わせではあるのだが、調子良かったとしても本番中に自力で思いつけた可能性は低かった気がする。最初に問題を見たとき、これ既出じゃないの？ と思ったので、その疑いに従って検索した方が良かったか？（とはいえ、見つけるのは至難のわざという気もする）
2026年3月25日水曜日
AtCoder Beginner Contest 450
ABCDFの五完。なんとかFを解けて良かった。
コンテスト後のツイート
E 予めS_Nの長さを求めて、[l,r]のrに近い最も大きいindexを使って、再帰で小さい方へ帰着できると思ったがTLE&REが出てダメ。
— titia (@titia_til) March 21, 2026
F 遅延セグ木DP。戻って良いという条件のもと、1からNへ辿り着く方法を求めたい。スタート地点を2^Mとし、x→yが来たら、[x,y]を半分にし、yにその分を加算。DP[N]が答え。
E - Fibonacci String
コンテスト中のコードを修正してAC。
コンテスト中に見逃していたのは、[L,R]の文字の個数は[0,R]の範囲のものから[0,L-1]のものを引いて求められるということだった。基本的なことだけれどなぜか忘れて最後まで気付けなかった。
[L,R]のまま扱おうとしたことでlが大きい場合にREになるコードになっていたのも本質的にまずい。これも、ここを直すと自然と修正された。
これでREが取れ、再帰の変数を一個減らすことができ、メモ化再帰を用いてcodonでAC。
しかし、PyPyではACできず、なぜ？ と思ったが、メモ化再帰で使っているdictのせいで遅くなっていた。
再帰の回数は少なく、あえてメモ化する必要はない。各段階での文字の個数は前計算できるので、それを使えばPyPyでもACできた。
2026年3月21日土曜日
yukicoder contest 494 オムニバス
Cのみ一完。Dを最初に考えたが分からずCに行ったのだが、Dを分からなかったのはまずい！
No.3476 {2^n-1}-gon
円の中心を含まないものを引く。
円の中心を含まないものは、最も左の点を固定し、そこから半周以内にM個全てが収まっているようなもの。
全体の個数も、引くものも二項係数で求められる。
これ、概ね最初に考えた解法だったのだが、なんでNは2ベキ-1なんだろう？ とか、引く数はこれで良いのだろうか？ などと考えてしまい混乱。もっと落ち着いて自然に考えていれば解けたはず。
No.3474 Concat Decimal
自力AC。これは普通に解けた。
全ての(i, j)でなく、i<jなるペアのみなのがちょっと引っ掛けっぽいですね。
No.3473 AtCoder < CMS
解法ツイートを見てAC。自力では分からなかった。
2^M-1を含む場合を考えると、各bitごとに、0/1を割り振るもののうち、全て0を除いた場合の数と一致する。（ここが分からなかった！）
あとは、2^M-1を何個含むか考えれば良い。
式変形をすると二項定理が使える形になるので、それで計算すれば解ける。
難しいが、解けないのはダメ。
No.3477 Yet Another LIS Triangle
自力AC。
これは簡単でした。
No.3478 XOR-Folding Primes
自力AC。
2,k,k+2という素数の三数がたくさなあり、その間を行き来するしかない。
素数を列挙した後、行き先を考えてDP→行列累乗で解ける。
Mまでにkが含まれるがk+2が含まれない場合、2→kみたいな行き方がありうると思ってしばらく悩んでしまった。このときは、P_iがk+2になるので、ありえないのですね。
2026年3月8日日曜日
AtCoder Beginner Contest 448
Eまで。D・Eとも若干苦手な問題だったとは思うが、時間かかり過ぎてしまった。Eを飛ばしてFへ行った方が良かったか？
コンテスト後のツイート
AtCoder Beginner Contest 448 Eまで。D、E両方に苦戦して破滅。
— titia (@titia_til) March 7, 2026
C セグ木
D 座標圧縮してdfs。dfsは苦手意識があるが思いつけて良かった。（が、時間かかりすぎ……）
E mod 10007*M*9で上手くいった。行列累乗とか考えて苦戦。
F Moじゃダメだから2-opt焼きなましかなぁと考えていた。Moでいけるの？
F - Authentic Traveling Salesman Problem
自力AC。
コンテスト中、Moじゃダメだと思った理由は、MAX=2*10^7として、MAX√MAX>10^10だからダメだと思ったせいでした。
MAX√Nと比較しないとダメですね。
ただ、コンテスト後の実装でも、ミスで3ペナしてしまったので、コンテスト中にEを飛ばしていたら必ず通せていたとも言えなそう。
登録:
コメント (Atom)