Fを考えたが解けなかった。
No.3493 等比数列の和の素因数
解説AC。
いまだにフェルマーの小定理やオイラーの定理があやふやなのが敗因。
等比数列の和の公式を考えた後、オイラーの定理を使う方向で考察を進めなくてはいけなかった。ちゃんと立式して、落ち着いて考えるべき。
titiaのノート
2026年4月4日土曜日
2026年3月29日日曜日
Nebius Round 2 (Codeforces Round 1088, Div. 1 + Div. 2)
C1までとDの四完。
コンテスト後のツイート
C1 -1には使っていない数を順番に入れて良い。A[i]がBのどの範囲にあれば良いか分かるのでチェック。
— titia (@titia_til) March 28, 2026
D bitごとに考えて良い。後ろから見るとk個以上入っているbitが確定していく。
E 木DPするしかなさそう。そこまでのスコアと、gcdとして必要そうな値を持ったがTLE on pretest30でした。
E. Minimum Path Cover
解法ツイートを見てAC。
gcdたちのうち必要な値を何個か持たなくてはいけないと思ったが、それらをlcmで代用することが可能だった。
言われれば確かに……。
木DPのとき持つ値は一個で良いはず！ という気持ちになれば思いつけたはず。TLEになるだろう提出の結果を待っていたのはダメでどうにか一個の値にできないか？ と粘るべきだった。
2026年3月28日土曜日
yukicoder contest 495
BとEの二完。あとはFを考えていたが分からず。Eは上手い方法が分からず、a,b全探索でcの範囲を定め、その後、ミラー・ラビン素数判定法を使って判定、で通ってしまった。良かったのかなぁ。
No.3483 A Forbidden Fruit
自力AC。
自力ではあるのだけど、たとえば、「M個の中からr個選んだとき、外れ（の一個）が含まれない確率」が1-r/Mであることも計算しないと気付かなかった。
確率について直感が働いてないなぁ。
No.3484 Just a Maze Game
大体自力ACだが、Wと書くべきところをMと書いたり、W=5, 7だけ書いてW=3の場合を書き忘れたりと、ミスが多かった。
No.3486 Draw a Rainbow
解説AC。
最初解説を見て、ゼータ変換やメビウス変換を理解できていないから解けなかったのかと思ったが、実際はDPの方針が立てられなかっただけでした。反省。
ゼータ変換やメビウス変換は、（今回のように集合に関するものの場合）bitごとの累積和やimos法なだけなので、全く恐れる必要はない。フーリエ変換と違って集合や約数の畳み込みは難しくない。（フーリエ変換はいまだに難しい……）
なお、今回の自分の解答ではBitwise OR Convolution自体は使わず、DPとして累積和を取ったとき（ゼータ変換したときの値）をそのまま持って計算し、最後に一回だけメビウス変換を行った。
集合に関するこのあたりの変換が分からなくなったときは、この問題のりんごさんの解説放送を見るのが手っ取り早いと思う。
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)