2026年4月24日金曜日

Educational Codeforces Round 189 (Rated for Div. 2)

　Eまで五完。

コンテスト後のツイート

F. String Cutting

　解説AC。
　コンテスト中に考えていた方法はダメだった。誤読で間違えただけだったら、ちょっと直せば通るはずだけどそれでは無理で、根本的に間違っていた。

　気付いていなかったのは、
・各開始位置indexについて、S[index:?]を考えるとき、n,k,lの条件から?は定まる。（そもそもその開始位置では条件を満たさないものもあるが、それも判定できる）

　ということ。
　言われてみれば当たり前ですね。

　これを使えば、Suffix-arrayとLCP配列を使ってどの開始位置が最適かを調べることができる。
　Suffix-array配列をSAとすると、SAの中でできるだけ後ろにある開始位置が良い。その長さがLCP配列より大きければそれが答え。そうでなければ、SAの一つ前の開始位置のものの方が良いかもしれないので比較していけば良い。







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

2026年4月21日火曜日

AtCoder Regular Contest 217

　AB二完。Bはまあまあ速かった。実験したら解ける問題はある程度速く解ける（こともある）らしい。

コンテスト後のツイート

C - Greedy Customers 2

　公式解説を読み、解説放送を見てAC。

・所持金のmultisetが同じなら、人がどういう順番で来ても買う商品のsetは変わらない

　というのが気付くべきポイント。これにも気付いていなかったので、コンテスト中のACは遠い。

　その後はDPなのだが……。

　品物がk個以上売れる確率を求めたいというのは良い。
　が、k回そういうDPを行うというのは意外だった。

　DP[i][j]でA[i]以上のお金をj人が持っている確率、とすれば、kを固定していれば遷移が回るというのは分かりやすい。が、kを固定しないと回らない（のか？　少なくとも解説ではそうなっている）というのが混乱しやすい気がした。

　なお、PyPyではTLEしたため、codonでACした。




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

2026年4月19日日曜日

キーサイト・テクノロジープログラミングコンテスト（AtCoder Beginner Contest 454）

　Eまで五完。

コンテスト後のツイート

F - Make it Palindrome 2

　解説放送を見てAC。

　結局のところ、「区間加算がきたら差分を取って考える」ができていなかった。この典型にはいつもやられている気がする。

　今回は忘れていたわけではなくて、コンテスト中、差分を取って考えてみようとはしたのだが上手くいかないと思ってやめてしまっている。
　しかし、区間の話を二点の足し引きにできているという時点で前進しているのだから、捨てたりせずちゃんと思考を進めるべきだった。

　あまり意味のない言い換えに思えたとしても、やっておかなくてはいけない。

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

2026年4月17日金曜日

AtCoder Beginner Contest 453

　Eまで五完。
　順位表を見てGまで行ったが、Gは未履修で、思い付くのは不可能だったように思う。実装も非常に大変だった。

コンテスト後のツイート

G - Copy Query

　解説AC。
　永続セグメント木を初めて勉強し実装した。
　遅延セグメント木などを理解していれば理解することは難しくないが、実装はかなり大変だった。

　セグ木の値、各nodeの左側の子、右側の子、親、その区間の左端と右端、各Versionの根の値などを更新があるごとに追加していく。ちょっとTrie木のような実装を行った。


　


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

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 件のコメント:
ラベル:
登録: コメント (Atom)