2026年1月13日火曜日

AtCoder Beginner Contest 440 (Promotion of Engineer Guild Fes)

 ABCDFの五完。

コンテスト後のツイート

E - Cookies

 コンテスト中に書いていた方針でAC。
 コンテスト中、例題を解いた経験があると思ったが、実際正しかった(どの問題かは探せなかったけど)。そして、Aを降順にソートして、[K,0,0,0,0]からはじめて、一つずつずらしていく探索をすれば良い……という方針もできていた。

 ただ、コンテスト中は、Kの値が大きいことに混乱して、[K,0,0,0,0]のような配列で扱えると気付かず、Counterを持ち出していた。そのため実装でCounterのhashを求めなければいけなくなったりし混乱。
 そして、hash値を求めているのにその値を使い忘れたり、値が0のときはじくのを忘れたりしてWAが取れぬまま終了した。

 コンテスト中は混乱して、正しいことを書いているのか分からなくなっていたけど、落ち着くことさせできればコンテスト中に通すことも可能だった気がする。






2026年1月3日土曜日

Educational Codeforces Round 186 (Rated for Div. 2)

 Eまで。終了後F1は通った、と思ったらシステムテストで落ちた。

コンテスト後のツイート

F2. Christmas Reindeer (hard version)

 自力AC。見直したら難しくなかった。

 各桁について、何個使うのがギリギリなのかが分かるので、ギリギリのときと、それ以上が確定したときに分けてDPしていく。ギリギリのときは何個使えば良いか? が分かるので、それより大きい個数を使うときは確定。同じ個数を使うときはギリギリ。二項係数で計算する。
 これも桁DPの一種といって良いかな。

 コンテスト中、30分残っていたら解けて良かった気もするけど、問題把握に結構時間かかってしまったなぁ。


2026年1月1日木曜日

yukicoder contest 286

 Cまで。


No.1425 Yet Another Cyclic Shifts Sorting

 自力AC。
 二種類あれば隣接要素SWAPができそうなので、答えは高々2。0回の判定は簡単なので、1回でできるかどうかを調べれば良い。

 一回でできるかどうかは、ソートした配列と比較し、最大値が一致していれば消していく。
 残った配列について、ソートしたものを巡回したものになっていれば良いので、ローリングハッシュを使って判定した。

 が、解説を見たらもっと簡単にできたらしい。なるほど。

 ところで、なぜタグが「動的計画法」なのだろう? 解けたと思った後タグを見たらそう書いてあって、何か間違っているのでは? と疑心暗鬼になりながら実装した。
(タグに頼るのはいけないかもしれないけど、yukicoderのタグはいつも出したまま問題を考えています)

No.1426 Got a Covered OR

 解説AC。
 A_iが全て正、という条件の扱い方が難しい問題。

 包除原理で扱うのかな? とは思ったものの、DPで包除原理でやるのかと考えてしまってダメだった。

・範囲を分割できること
・それぞれの範囲について、二項係数を使って計算していける

 ことに気付ければ解ける。
 bitの中で条件を満たさないものの個数で包除すれば良い。

 方針が分かれば難しくない。何で包除すれば良いかを考えるのが大切だった。

No.1427 Simplified Tetris

 解法は自力で分かったが、ACするのは苦戦した。

 盤面が与えられたとき、ちゃんと置けるかどうかは、この問題と同じ。
 なので、元の盤面の候補を全探索したい。

 ブロックが入っているマスの前後に何マスあるか? をDFSで調べれば良さそうだが、何列必要かが分からない。高々2列で十分だろう、と思ったらWAで、3列必要な場合があった。

 そして、それで全探索するとTLEしてしまったため、ずるいけれど時間で打ち切る処理を入れてAC。

 解説を見ると、もっと上手にやる方法が書いてあった。気付かなかった。

2025年12月29日月曜日

Good Bye 2025

 Eまで。

コンテスト後のツイート


F. Conquer or of Forest

 コンテスト中に考えていた方針でAC。

 まず、白いnodeと親nodeを切る。
 そして、それらを一列に並べれば条件を満たす。(どのnodeからどのnodeへ繋いでもOK)

 結構人工的な条件なので、そこから何かを考えようとするのではなく、それっぽい必要条件を探すのが大事だった。
 一列に並べた結果、問題文の条件を満たす証明は分からないけど、それっぽくはなっている。

 コンテスト終盤にこの条件では? と思ったが、数え上げが間に合わなかった。

・ROOT以外の連結成分について、どの頂点を親と結ぶか
・葉以外の連結成分について、どの頂点を親にするか
・ROOTと葉以外の連結成分について並び替え

 を掛け合わせればOK。
 三番目がよく分からず時間切れ。
 (連結成分数)!みたいなのがいるとは思ったのだが、(連結成分数-2)!だったとは。落ち着けばできたと思うけれど、この条件自体が正しいという確証もないこともあり落ち着けなかった。




2025年12月26日金曜日

ユニークビジョンプログラミングコンテスト2025 クリスマス(AtCoder Beginner Contest 437)

 Fまで六完だがEに手こずった。

コンテスト後のツイート

G - Colorful Christmas Tree

 解説放送を見てAC。

 コンテスト中、フローは少し考えたのだが、使い方が分からなかった。

 次数を見れば最終的に何の色になるか分かるとは思ったが、その間の色を全部使うと気付けなかったのが敗因か。それに気付ければ自力でフローに思い至れた可能性はある。



2025年12月17日水曜日

yukicoder contest 490

 Gのみ解いて撤退。


No.3391 Line up Dominoes

 一応自力AC。
 DPで解く。DPで遷移したときの要素は区間和になることが分かるので、毎回累積和を取って流し込んだ。
 PyPyだとMLEになってしまったので、RUSTに直してもらいAC(コンテスト中だとできないが……)。
 解説を読むとPyPyでも普通にACできるようなのだが、よく分かっていない。

No.3392 Count 23578 Sequence

 自力AC。
 階差数列を考えると、回文の個数を数える問題に帰着できるので、Manacherを使って解ける。
 しばらく気付けなかったが、階差数列を考えると気付けて良かった。

2025年12月15日月曜日

AtCoder Beginner Contest 436

 Eまで。Fが解けずダメでした。

コンテスト後のツイート

F - Starry Landscape Photo

 使う数字の最大値を考えると、それ以下の数字は全て使い、それより大きい数字は消えている。
 なので、使う数字の最大値が大きい順に考えて、一つ一つ消していけばOK。

 コンテスト中は、左端を固定したり、DPを考えたり、使う数字の最小値を考えたりしていた。
 使う数字の最小値を固定する方針にしばらく時間を使った後、最大値を固定する方針も考えたはずなんだけど、なぜか上手くいかない気がしてしまった。
 今見ると、難しく思えないのだが……。なんで解けなかったのか分からない。

G - Linear Inequation

 解説放送を見てAC。

 形式的ベキ級数を使うと聞き、立式まではできたつもりだったのだが、1+x^a+x^(2a)+...をM次の項までで打ち切るなどと考えてしまったのがダメ。
 1+x^a+x^(2a)+...と無限に続くもの同士の積と考えるべき。

 そして、さらに重要なのは、「そのM次以下の係数の和」を、Aに1を付け加えることで、M次の係数と解釈できるようにするところ。全く思いつかなかったが、形式的ベキ級数に慣れている人にとっては典型なのでしょう。

 あとは、Bostan–Mori法を使って処理すればOK。久しぶりにこのライブラリを使う機会と出会った。

 形式的べき級数にもっと慣れないとダメですね。