2026年4月16日木曜日

AtCoder Beginner Contest 452

　Fまで解けたが遅かった。

コンテスト後のツイート


G - 221 Substring

　自力AC。

　コンテスト中の方針であっていた。数字の個数＝数字の大きさならそのまま、個数が数字の大きさより大きければ、k 0 kと置き換えて並べる。
　その上で、Suffix array、各indexから0までの個数を調べていく。そのままだと重複が出るが、LCP配列を使えば重複は除ける。

　コンテスト中に失敗していたのは、自分のライブラリだと文字列Sの後ろに、最も小さい文字（今回は数字）を置いておかねばいけないところだった。あとは、SA[i]でi番目に小さいindexを表すのだが、その逆関数なのかどちらか分からなくなって混乱したところ。ただ、これは久しぶりにSuffix arrayを使ったのだからしょうがない気もする。

　後はすんなりできた。
　Fより時間かからなかったと思うので、F捨ててG行けば通せてたかなぁ。


時刻: 0 件のコメント:
ラベル: ,

2026年4月9日木曜日

Codeforces Round 1091 (Div. 2) and CodeCraft 26

　Cまで三完。過去最悪に近い成績。しかし、DもEも難しい気がしたが……。

コンテスト後のツイート

D. Flip the Bit (Hard Version)

　解説AC。

　隣接する値が異なる場合は1、同じ場合は0とする配列を持っておく。
「ある区間の反転は、この配列の二項を反転させるもの」と捉えるのは（この前のARCのAで出題されたので）覚えていた。

　さらに、この問題のようにindex iを含む区間の反転は、
★「iより左側とiより右側で反転させる」と捉えることができる。

　ここで、P[i]で配列を区切っていくつかの区間を持つと、
★「二つの別の区間から反転する」という操作なら全て行えることが分かる。

★ところで、最終的な値を0にしたいなら、Aの左右に0が広がっていると考えても同じ。

　そう捉えて区間を分割し、隣接項が違うものの個数を数えたものをSとすると、
・Sの異なる項から1ずつ引く
・Sの一つの項から1を引く
　の操作を行ってSの全ての要素を0にするとき、最低何回必要か？　という問題になり、これは、最大値で場合分けしたりheapqを使ってシミュレーションしたりすれば解ける。

　難しかった。
　★で書いた三つとも自力では思いつけなかった。隣接xorを取る部分は定石だけど、それ以降の処理にも難しい部分があると、なかなか正解まではたどり着けない。
時刻: 0 件のコメント:
ラベル:

Codeforces Round 1090 (Div. 4)

　全完したが順位はあまり良くなかった。そんなに遅かった気もしないのに厳しい。

コンテスト後のツイート



時刻: 0 件のコメント:
ラベル:

2026年4月4日土曜日

yukicoder contest 496

　Fを考えたが解けなかった。


No.3492 区間冪乗加算一点取得

　解説AC。

　まず、D<=100に気付かなかったのが敗因。だが、解説を見ても、なかなか理解できなかったのは良くない。内容的には、D<=100に気付いたなら解けなくてはいけない問題だった。

　ただ、D<=100でクエリ問題だからやることが決まってくるから解法に気付きやすいというだけで、(i+C)^Dののd次数目が、CやDが変わっても似た形で表せるというのは意外だった。立式をすれば分かることとはいえ、こういう観点で見たことがなかったので面白かった。

No.3493 等比数列の和の素因数

　解説AC。

　いまだにフェルマーの小定理やオイラーの定理があやふやなのが敗因。
　等比数列の和の公式を考えた後、オイラーの定理を使う方向で考察を進めなくてはいけなかった。ちゃんと立式して、落ち着いて考えるべき。

　


時刻: 0 件のコメント:
ラベル:

2026年3月29日日曜日

Nebius Round 2 (Codeforces Round 1088, Div. 1 + Div. 2)

　C1までとDの四完。

コンテスト後のツイート

E. Minimum Path Cover

　解法ツイートを見てAC。
　gcdたちのうち必要な値を何個か持たなくてはいけないと思ったが、それらをlcmで代用することが可能だった。
　言われれば確かに……。

　木DPのとき持つ値は一個で良いはず！　という気持ちになれば思いつけたはず。TLEになるだろう提出の結果を待っていたのはダメでどうにか一個の値にできないか？　と粘るべきだった。
　


時刻: 0 件のコメント:
ラベル:

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として累積和を取ったとき（ゼータ変換したときの値）をそのまま持って計算し、最後に一回だけメビウス変換を行った。

　集合に関するこのあたりの変換が分からなくなったときは、この問題のりんごさんの解説放送を見るのが手っ取り早いと思う。

　
　
時刻: 0 件のコメント:
ラベル: , , ,

2026年3月26日木曜日

AtCoder Regular Contest++ 216

　一問も解けず。

コンテスト後のツイート


A - Reversi 3

　解説AC。
　既出で解いたことのある問題だった。
　時間が経っているので忘れているのは仕方ないし、この解法を思い付くのは難しいと思うので仕方ない面もあるが、初手の隣接xorを取るところすら思いつけなかったのはまずかった。
　隣接xorを取った後の処理も思いつきにくいが、偶奇に着目するのはやってみなくてはいけない。

　定石の組み合わせではあるのだが、調子良かったとしても本番中に自力で思いつけた可能性は低かった気がする。最初に問題を見たとき、これ既出じゃないの？　と思ったので、その疑いに従って検索した方が良かったか？（とはいえ、見つけるのは至難のわざという気もする）

　






時刻: 0 件のコメント:
ラベル:
登録: コメント (Atom)