2025年12月7日日曜日

パ研合宿2021　第2日「SpeedRun」

　A~HとJで九完。

コンテスト後のツイート

J - Min-Max Sequence

　解説AC。
　連結でさえあればどのようなxとyに対しても、「他を変えずに、xとyを入れ替える」という操作が可能だと気付けるかがポイント。単純に行って帰って……と交換したら良さそうだが、自己ループなどがあると壊れるのが難しい。

K - Bracket Inserting 

　括弧列は根付き木と捉えることができる！
　それさえ知っていれば、木DPと気付くのは難しくない。
時刻: 0 件のコメント:
ラベル:

2025年12月2日火曜日

Educational Codeforces Round 185 (Rated for Div. 2)

　Cまで三完。途中ややいい加減にやってしまったところはあるけれど、Eは真面目に考えたのだけど解けなかった。


E. Binary Strings and Blocks

　包除原理を使う問題にしか思えなかったけど、違ったようでびっくり。

　正しい解法は、DPでした。
　最後に色が変わった箇所がiとしたときの塗り方の個数をDP[i]とすると、[l,r]の条件から、次にどこまでで色が変わらなくてはいけないのか？　が分かるので、そこまで一気に（セグ木などを使い）加算していく。
　言われてみれば自然なDPだけど、1マス1マス決めていくことしか考えていなかったせいか、全く思いつかなかった。

　何個条件に違反しているか？　という包除原理を考えていたけど、これだと、ある区間と別の区間に交わりがあったとき、両方に違反しているか？　などを上手く数えられないので上手くいかないのですね。
時刻: 0 件のコメント:
ラベル:

2025年12月1日月曜日

AtCoder Regular Contest 211 (Div. 2)

　AB二完で青に落ちる。ABCで黄色に上がった次の日のARC/AGCって悪い成績をとりがちなのかも。

コンテスト後のツイート

C - Forest

　コンテスト後半に最大値が大事だと気付いたとき、まず思いついた解法が正解だった（証明は、公式解説を見るまで分からなかったが）。
　ダメな気がして棄却してしまったが、反例が見つかったわけじゃないし実装すべきだった。
　こういうのが反例になるだろう、と考えていたものはあったが、具体的に構築できたわけじゃないかった。どちらかというと、それが反例だとすると実装が複雑になりそうでおかしいと思うべきだった。左右から最大値をその場所へ寄せていけるか？　みたいなことがキーになりそうだと思って実装していたけど、そう考えたときすっきりした条件にまとまらなかったのもおかしい。

　複雑なことを考える前にまず実装して投げてみるべきだった。既にBでペナルティを出しているわけで、ペナルティの個数を気にするような状況ではない。それっぽい解法が思いついたら投げて、ACかWAか様子を見るべき状況だったはず。

　普段、余裕があるときなら確信がなくても実装して一度投げていると思うのに、なぜしなかったのか。
　焦り過ぎていた。

D - Michishirube

　DFSというキーワードをヒントにAC。

　コンテスト中は、橋で分解した後どうしようか、と考えていた。コンテスト終了直後にDFSすればいいのでは？　と浮かんだけど後の祭りだし、それも、橋で分解した後DFSすると良いかも？　と思った感じなので、橋を使わずにDFSすることに思いいたるまでにはまだ時間がかかったと思う。

　ただ、こういう問題でDFSを考えるのは定石なのだから、考えてみなくてはダメだった。
　そもそも、LOWLINKが必要と思っている時点で筋が悪い。ARCでLOWLINKを使う問題は出ないのでは？（出る可能性はあるけど、そこそこ低いはず）　と考えても良かった。



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

2025年11月28日金曜日

estie プログラミングコンテスト2025 （AtCoder Regular Contest 210）

　Cまで三完。Aが難しかった。

コンテスト後のツイート

E - Subset Sum Gaps

　解説放送を見てAC。
　かなりシンプルな解法だった。

　部分和を考えるのだから、今までの和を全てもって、そこに一つずつ追加していくという考え方は自然。
　それを区間（区間の最小値・最大値・個数を持つ）で行えば良かった。計算量は分からなくても、1.01倍というのを生かそうと思えば区間を考えようと思うのは自然だろう。
　1.01倍というのを見て数学問っぽいかと思い避けてしまったけど、Dよりは可能性があったか？
時刻: 0 件のコメント:
ラベル:

2025年11月27日木曜日

AtCoder Beginner Contest 426

　Fまで六完。

コンテスト後のツイート


G - Range Knapsack Query

　解説放送を見てAC。
　自力で思いつくのは難しいが、知ってしまえば単純な内容。

　分割統治で答えを求める……と言われてもなぜそれで計算量が落ちるのかピンと来なかったが、noshiさんによるDisjoint Sparse Tableの図を見ると分かりやすかった。

　これをデータ構造として持つのがDisjoint Sparse Tableですね。今回はクエリ先読みできるので分割統治で、この図のようなことをやる（上のノードから下のノードへ分割し、潜っていく）とOK。

　なお、実装にも苦戦しました。分割統治したデータを持とうとするとMLEしたのが一つ。また、クエリでl=rの場合での場合分けが必要で、そこにもなかなか気付きませんでした。
時刻: 0 件のコメント:
ラベル: , ,

2025年11月25日火曜日

ユニークビジョンプログラミングコンテスト2025 秋（AtCoder Beginner Contest 425）

　Fまで六完。
　Gも考察の方向性は間違っていなかった模様。

コンテスト後のツイート

G - Sum of Min of XOR

　解説放送を見てAC。
　コンテスト中は、Binary Trieを使うことを思い付いていたらしいが、今考えていたときは思い付けなかった。

　しかし、Binary Trieを使うと思いつけたのなら、Binary Trieに区間を入れていくだけなのでそれほど難しくない気がするのだけれど、コンテスト時はどうして分からなかったのだろう？

　解説を見た今だと、考察も必要なアルゴリズムもそこまで難しくないため、解けなきゃいけない問題に見える。



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

2025年11月24日月曜日

AtCoder Beginner Contest 433

　Fまで六完。

コンテスト後のツイート

G - Substring Game

　コンテスト中は、Suffix arrayやLCP配列を使う、というところは合っていたけど、木になるということは理解していなかった。再帰で解けると思っているんだから、木構造になると分かってはいたはずではあるけれど……。

　解説放送を見てSuffix treeを使ってAC。
　Suffix treeは初めて書いたけれど、Suffix array・LCP配列・Trie木を理解していれば難しいところはなく、時間をかければ自力で解けたはず、とは思う。
　ただ、解けたとしてもEやFより時間かかっただろうから仕方ないか。





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