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 件のコメント:
ラベル:

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