2026年5月18日月曜日

SMBCプログラミングコンテスト #1（AtCoder Beginner Contest 458）

　Eまで。またレート1800を割る。

コンテスト後のツイート

F - Critical Misread

　コンテスト中の方針で大まかなものはあっていたが、どこでWAになるか分からず、ランダムテストでACしている提出と比較した。

　ミスは次のようなものだった。
　たとえば、"bcb"と"c"がある場合に、"bcb"が出たらそもそもいけないのだが、"bc"や"bcb"もノードとして数えてしまっていた。
　そのようなものを削る前処理を行ったらAC。

　Aho-Corasick法を使う場合に、必要になることが多い前処理という気がするが、知らなかった。

　そして、AIに聞いたところ、Failure_pathを利用して"c"に印がついているなら、"bc"にも印がつくようにする、という構築を行うのが一般的らしい。勉強になった。

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

2026年5月14日木曜日

Polaris.AI プログラミングコンテスト 2026（AtCoder Beginner Contest 457）

　F以外の六完で久しぶりの黄パフォ。Gは公式解法と違うので嘘解法疑惑があるけれど、多分大丈夫？→とりあえず、ランダムテストではHack caseは発見できませんでした。

コンテスト後のツイート

F - Second Gap

　解説AC。
　コンテスト中、maxとsecondのindexを持てばDPできるのでは？　みたいなことは考えたのだが、上手く分からず実験をはじめて考察をやめてしまった。
　実験自体は悪くないのだけど、ちゃんと考察しないといけない。

　実際は、maxのindexだけ持ってDP（挿入DPみたいなやつ）できる。maxとsecondを持つDPが書ければ、そこに気付くのは難しくないはず。

　Gが解けたから助かったものの、こちらも解けなくてはいけない問題でした。
時刻: 0 件のコメント:
ラベル:

2026年5月11日月曜日

AtCoder Regular Contest-- 219

　Cまで三完だが、Aは嘘だった。DもEも思いつきにくい部分は思いついていたのだが。

コンテスト後のツイート


A - Similarity

　文字列Xの01を反転させたものをX'とすると、S中にX'が含まれないなら、Xを答えとして良い。
　ACした提出は、Sの文字を全探索してそれを調べたが、Sの要素が全て対になっているとき、これではダメ。乱択などしなくてはいけなかった。WAが出たら気付いてACはできていたと思う。

D - Grid Game

　解法ツイートを見てAC。

　コンテスト中、（一次元での）実験により、
・(i+j)%2==1の箇所しか影響しない
　ことには気付いていた。
　また、（K+1）での余りを考えて良いことも分かっていた。

　しかし、判定条件が分からず、交代和などを考えて迷走。分からなくなってEへ行った。

　実際は、NIMと同じなのでxorを取ると良かった。
　NIMに近いのでは？　と考えたことはあったはずなのに、なぜ試してみなかったのか。悔やまれる。

E - Equal Distribution

　解法ツイートを見てAC。

★「oが偶数個とxが偶数個で作られた配列があったとき、その連続部分区間でoとxをちょうど半分ずつ含むものが存在する」
　を使うことはコンテスト中に気付いていたのに、全体のハミルトン閉路を取ることを思いつかなかったという。

　外周から距離０、1、２の順に、oがちょうど半分か、一個少ないか、みたいなものを取って構成しようとしていた。

　この方法でもできなくはない気がするけど、外周ではAが右半分に、次ではAが左半分に……みたいなときに連結性が保たれない。連結性を保つような取り方はあるはずだけど、若干実装の手間が増えるし、コンテスト中はそもそも反例に気付いていなかった。

　★が本質だと思うのに、★に気付いても違う方針へ行ってしまったのは痛い。

　一番の鍵となる部分は思いついて実装していたため反省点も見出しにくく、冷静にならないと……くらいしか言えないのも辛いところ。
時刻: 0 件のコメント:
ラベル:

2026年5月9日土曜日

yukicoder 499 contest

　Fを考えていたが分からず、Dのみ一完。


No.3537 Thank You!

　解説AC。

　どのカードを1にするか決めたら貪欲で良い……というのはコンテスト中から分かっていたが、それは簡単に求められないと思って迷走してしまった。（安い方からあるところまで貪欲に買った後、それ以降で個数が一番多いものを1にする、とすれば良いと思ったが嘘でした）

　二分探索を使えば、実装はやや難しいが普通に計算できた。これは気付かなくてはいけなかった。
時刻: 0 件のコメント:
ラベル:

2026年5月8日金曜日

Next DP Contest

　F以外の4点以下の問題は正解。後は部分点を拾った。もう少し取れないとまずい。

コンテスト後のツイート

F - 集合 

　解説AC。テーマ一覧とArcAkiさんの記事を参考にしてAC。

　そもそも考察が難しい。
　最小値を使うか使わないかで考えると、その左側のみ、その右側のみ、両方を使う、で場合分けされるが、両方使う場合は最小値も必ず使わなくてはいけない。このことから、再帰を使って書けそうだと分かる。
　……という考察部分に全く気付けなかった。

　この考察通り、再帰で書こうとすると、Cartesian treeの順にやることになり、そこでは二乗の木DPを行うことになる、という流れ。

　テーマを見てしまっていたので、この考察が分かった後はすんなり書けたけれど、実際はその後の部分も簡単ではない気がする。

J - 個数と総和

　この問題と同じテーマというのを見てAC。
　「繰り上がりを持つ桁 DP」と呼ばれているのは知らなかった。

　類題をACしたときは理解していたのだろうけど、DPテーブルを使い回して解くという解法を忘れていた。結構汎用性がある解法のようなので、ちゃんと身に着けておきたい。





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

2026年5月7日木曜日

AtCoder Beginner Contest 456（Promotion of AtCoder Career Design DAY）

　Eまで解いたが、Eは分からず、時間をかけて無理矢理嘘解法を通した。レートが1800を割ってしまった。

コンテスト後のツイート

E - Endless Holidays

　結局敗因はよく分からないけど、多分、サイクル検出すれば良い、と言われていたら解けた気がする。dfsしても良いし、SCCを使っても良いし、出次数が正の辺を消していっても良い。

　曜日の概念があったせいで、一般的な有向グラフのサイクル検出問題とは別の問題に見えていたことが敗因だった気がする。曜日1から始める……みたいなところをコードから消せると気付けていなかった。
　自分がどんな問題を考えているのか、もっと一般化した問題はないか、一般化したら問題は解けなくなくなるのか、といったあたりを意識したい。

F - Plan Holidays

　セグ木で解けると知ってAC。
　公式解説では、min-plus 代数などと難しいことを言っているけど、左右の端を使っているか、使っていないか、で4通り場合分けしてセグ木に乗せればOK。

　これも、セグ木で解けると気付かなかったことが敗因。
　多分、クエリが与えられて、[l,r]の範囲での答えを求めよ、と言われていたら解けていた気がする。
　その問題が解けるならこの問題も解ける、と気付くのが大事。



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

2026年5月6日水曜日

yukicoder contest 聖光学院プログラミングコンテスト2026 day2

　A一完で睡魔に襲われ撤退。


No.3527 Minimum Abs Sum

　解説AC。
　最初はCHT（slope trick）に見え、その後も、係数が一番大きいところなどと考えて失敗。

　係数が全て1のときの解法は知っていたし、
・abs(a*x+b)=a*abs(x+b/a)
　という式変形も見たことがあったはず。
　それにもかかわらず解けなかったのは反省。

No.3528 Happy XOR Candy

　自力AC。
　総xorが打ち消し合うというのはどこかで見たことあったと思う。
時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)