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を使って解ける。
　しばらく気付けなかったが、階差数列を考えると気付けて良かった。
時刻: 0 件のコメント:
ラベル:

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。久しぶりにこのライブラリを使う機会と出会った。

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






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

2025年12月14日日曜日

Codeforces Round 1070 (Div. 2)

　Dまで。

コンテスト後のツイート


F. Omega Numbers

　滅茶苦茶苦労したが、WAを量産した一番の原因が、200000を20000と書き違えていたことだというね！　これで二時間以上使っているのひどすぎる。

　解法自体も難しかったが、必ず身に着けておくべきなのは、
「数列Aにおいて、約数がxになるような(A_i,A_j)のペアの個数」がカウントできるということ。それができたとしても難しいのだが、後は自力で思いつくべきなのだろう。
時刻: 0 件のコメント:
ラベル:

2025年12月7日日曜日

パ研合宿2021　第2日「SpeedRun」

　A~HとJで九完。

コンテスト後のツイート

J - Min-Max Sequence

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

K - Bracket Inserting 

　括弧列は根付き木と捉えることができる！
　それさえ知っていれば、木DPと気付くのは難しくない。

L - ジグザグ道

　辺を基準にしたダイクストラ法でAC。
　実装が面倒だけど、やること自体は難しくない。

M - Deque and Inversions

　解説AC。実験したが何も思いつけなかった。
　どういうときに値が増えるか？　期待値は？　といったあたりを考えるべきだったか。

N - Polynomial Comparison

　解説AC。
　kのx乗を考える→k進数で考える、というのは自然な発想。
　自力で解けなくちゃいけない問題でした。スピードランでなかったらもっと解かれているはず。

O - Golf

　解説AC。
　Suffix arrayやLCP配列を知っていれば簡単かと思いきや、全然そんなことはなかった。
　解説をちょっと見て、Suffix arrayを使うということをヒントに自力で解こうとしたが撃沈。クエリ先読み＆平面走査が必要とは気付けなかった。
　確かに典型度は高いが、考える要素もあるし、実装も大変だった。
　
時刻: 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 件のコメント:
ラベル:
登録: コメント (Atom)