2026年10月6日火曜日

AtCoder Regular Contest 231

　Bのみ一完。それも遅い。

コンテスト後のツイート

A - Two Dimensional Invader

　解説放送を見てAC。

　言われてみればなるほど。x座標とy座標を分けて考えるという発想はあったが、思いつけなかった。
　BITは「更新O(logN)区間取得O(logN)」ですが、これは普通にやった場合「更新O(1)取得O（N）」、累積和を使った場合「更新O(N)取得O（1）」の中間あたりを取っていると考えられる……みたいなのと似ている。

　O(N^2)をO(N)とO(N)に分解することもそこそこありそうなので典型的とは思うけど、一問目でパッと見て思いつけるものでもないねぇ。Bがスムーズに解けて、落ち着いて臨めたら違った可能性はあるかなぁ。

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

2026年9月24日木曜日

AtCoder Regular Contest++ 230

　一問も解けず。

コンテスト後のツイート

A - Meeting on Tree

　解説を読んでも式変形が理解できず、ChatGPTと相談して式変形を理解し、AC。

　技巧的で難し過ぎるが、

・minは扱いにくいので、minのない形へ変形する
・Σの中に二項係数の積があるときは、Vandermondeの畳み込みの適用を疑う

　といったあたりを押さえていれば解くのは不可能ではないかも？

　ただ、そもそもVandermondeの畳み込みという公式を知らなかった（覚えていなかった）のでコンテスト中は解きようがなかった気がする。

　いやぁ……。
　一応たくさん解かれているから、自力で解くためにはどうしたら良かったのだろう？　と考えてみたけど、正直なところ、式変形を追うことは一応できるけど、自力で導出するのは不可能なレベル、と思えてしまう。
　このタイプが頻出問題なら、似た問題を短期間に十回とか解けばできるようになるかもしれないけど（それでも一年後には解けなくなりそうな気も……）、そういうこともないからなぁ。
時刻: 0 件のコメント:
ラベル: ,

2026年9月23日水曜日

Codeforces Round 1122 (Div. 3)

　Eまで。Dから難しい……。

コンテスト後のツイート

F. MEX Replacement

　苦労したけど自力AC。

　答えを二分探索する。
　MEX xを作りたいなら、[0,x-1]が全て1個（以上）必要。そのためには、[0,x-2]まで全て2個必要、と差がsaならpow(2,sa)倍の個数必要になっていく。
　そして、余ったものは、0に変えて使うことができる。
　これらを使うと、自分以下のそれぞれに必要な個数が何個か、というのを持って大きい方からシミュレーションしていく（それがあまりにも大きくなったらその時点でダメ）ことで、「あるxを作れるか？」という判定問題が解ける。

　答えで二分探索して大きい数字から見ていけば解けそう、という大まかな方針が分かった後も実装に苦戦。なかなか難しい問題という気がした。
　






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

2026年9月16日水曜日

Codeforces Round 1121 (Div. 2)

　Dまで四完。レートが上がったが、昨日の大失敗を取り返すことはできず。

コンテスト後のツイート

E1. A Prime Flood (Easy Version)

　Aの最小値、最大値が分れば、f(A)の値は求まる、ということはコンテスト中に分かっていた。
　DP[最小値][最大値]とDPすれば、fの値を求めることができるという情報を見てAC。

　確かに、言われてみればDPできるが、コンテスト中は全く考えなかった……。
　Easy versionの制約がn<=3000である理由を追求するべきでした。



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

2026年9月15日火曜日

AtCoder Heuristic Contest 071

　187位。
　最初は焼きなましを考えていたが上手くかず。方針転換しこの解法を思い付いたときは割と筋の良い貪欲を思い付いたと思ったが、実際はイマイチでした。

コンテスト後のツイート

　上から置き方を確定させて良い、とは気付いていたのに、実際の解法に生かせなかったのがまずかったか。
　分割してDPとか、上からビームサーチなどという解法が流れてきて、確かに……という気持ちになった。



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

Codeforces Round 1120 (Div. 2)

　C1まで。
　Div. 1とDiv. 2が分かれている回でDiv. 2に出なくちゃいけないこと自体悔しいのに、そこで大失敗してしまった。

コンテスト後のツイート

C2. Floor of MEX (Hard Version)

　結局、次の問題が解ければ良い。

　自然数1,2,...,nからいくつかを選ぶ場合の数のうち、 
・[l_i,r_i]から少なくとも一つ選ぶ 
　という条件Q個を満たすものの個数を求めて下さい。

　これをO(n+Q)くらいで解ければ良い（logが付いても良い）のだが、解けなかった。

　コンテスト中は包除原理を主に考えていた。
　これらの条件のうち、満たさない個数が偶数個の個数は求まるのだろうか？　などと。この方針は筋が悪かった。

　これはもっと直接的にDPで求めることができる。

・DP[i]を、「1...iについて条件を満たし、iを選んだときの求める個数」

　とすれば良い。
　こうすると、[l_i,r_i]から少なくとも一つ選ぶという条件は、「r_iより大きいjについて考えたとき、その一つ前に選んだ数はl_i以上である」という条件に直すことができ、それを利用すると累積和を使えばDPが回る。

（なお、DP[i]=「1...iについて条件を満たす場合の数」としても答えを求めることができるが、ちょっと遷移が複雑）

　これくらいの問題は簡単に解けなくちゃいけないんだろうけど……。筋の悪い解法にハマって抜け出せなくなってしまった。

D. Culling Game

　解説AC。

　「後ろから見る」という方針を知っても自力では答えに辿り着けず。

　降参位置を管理して解くのだが、そうできるポイントは、

　「ある降参位置で新しいチャンピオンが勝てた場合、そのチャンピオンのpowerは、以前のチャンピオンのpower以上になる。そのため、それより右にある降参位置を順に再評価できる。」（ChatGPTに整理してもらったもの）

　ということだった。
　これに気付ければあとはデータ構造を使ってがんばる問題になるが、その実装もなかなか大変だった。


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

AtCoder Beginner Contest 475

　F分からず、G間に合わずで五完。

コンテスト後のツイート

F - Rectangle Filling

　解説放送を見てAC。
　「Bounding Boxを見る」を全く思いつかなかった。色を塗る長方形で、一番上（下左右）の辺が全部#だと縮めて良い、ということには気付いていたのだが。

　F飛ばしたのは正解でしたね。

G - Has Many Divisors

　コンテスト中の方針でAC。
　最初の素数いくつかのベキを決め打ち、それ以降の素数を高々一個できるだけ使う感じでやった。
　コンテスト中は、実装ミスで、決め打った素数と一個ずつ順に使う素数の間に使わないものがでていたりしたのがひどかった。そういうミスがなかったとしてもTLEとの勝負があったから通せてたかは分からないけど、惜しかったねぇ。
　F飛ばした判断自体は間違ってなかったと思う。
　



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