2026年10月16日金曜日

オムロンプログラミングコンテスト2026 （AtCoder Beginner Contest 479）

　Eまで五完。

コンテスト後のツイート

F - Narrow Passage

　概ね自力でAC。解法ツイートは見たけど、それはあまり参考にせず解いた。
　結構時間がかかったので、Gに行かずFに集中していれば解けたかは微妙なところ。

　S[i]→T[i]へ線を結んだものを考える。
　基本的には、abs(S[i]-T[i])の和だが、交差している場合をどうするか。

・a→b(a<b)とc→d(c>d)が、逆向きに交わっている場合、答えを+1（交差するときの操作）し、a+1→bとc-1→dの操作と捉える。
・a→b(a<b)とc→d(c<d)が、c<a<b<dのように、抜かしている場合、答えを+1し、a-1→bとc+1→dの操作と捉える。

　のようにすれば良い。
　交差の回数はBITを使えば求めることができる。
時刻: 0 件のコメント:
ラベル:

2026年10月9日金曜日

Codeforces Round 1125 (Div. 3)

　Gまで。

コンテスト後のツイート

H. A Problem to Warm Up the Eyebrows

　解説AC。
　解説も自力では解読できず、ChatGPTに説明してもらってACした。

　解説は式変形で解こうとしているが、式変形から導出するのは難しい。
　主客転倒で解けないか？　と疑わなくてはダメ。

　A[i][j]*A[x][y]が何個寄与するか？　と考えると、そのbounding boxの上下左右に何個行や列があるか？　を見れば答えが求まることが見えてくる。
　そう思えば、具体例を考えるとどれくらい寄与するかが見える。

　難しいが、主客転倒というアイディアさえ思え付けば無理な問題ではなかった。



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

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