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 件のコメント:
ラベル: , ,

2025年11月22日土曜日

yukicoder contest 489

　Cまで三完。


No.3375 Binary Grid

　解説を見てもよく分からず、テストケースを見てデバッグしてAC。苦労した。

　再帰構造は明らかなので、それを使って計算するしかない。

　しかし、帰り道でどう再帰するかが難しい。
　(x,y) から(R,C)へ移動するとき（x>=R,y>=Cとする）、R行の中で、yからCの間に通れないマスがあるか？　を考える。
　なければ、max(x-R,y-C)が答え。

　R行の中で、最も大きい通れないマスの列番号kとしたとき、（R,k）から下に行った先で初めて進めるマス、そこを必ず通らなくてはいけない。
　それを使えば再帰できる。




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

Codeforces Round 1065 (Div. 3)

　pretestは全完したが、HをHackされてしまった。

コンテスト後のツイート

H. Shiori Miyagi and Maximum Array Score

　枝狩りの値を20→15にしたらHack caseは通った。→その後、uphackされました。

　正しい解法は、セグ木（or BIT）を使ってDPの高速化らしい。理解できていないけれど、そう言われると確かにできそうな気はしてきた。
時刻: 0 件のコメント:
ラベル:

2025年11月19日水曜日

オムロンプログラミングコンテスト2025 #2（AtCoder Beginner Contest 432）

　ABCEFの五完。レートを上げるためにはもう一問必要だった。


D - Suddenly, A Tempest

　自力AC。
　長方形のxmin,xmax,ymin,ymaxをもって分割していき、連結性はUnion-findで求めた。公式解説を見たところ大体同じ方針だった。
　実際にやろうと思えば難しくない方針だけど、実装はそれなりに大変だし、飛ばしたのは正解だと思う。

G - Sum of Binom(A, B)

　FFTを使うと聞いても分からず、解説放送を見てAC。頻度を見てFFTする手法は既知だったのだが……。

・FFTを使いそうだと気付く
・FFTが使えるように式変形する

　のどちらもできていなかった。
　が、こういう二乗の形を畳み込みしてFFTに持っていく問題は結構あるし、式変形も言われてみれば納得できるもので、分かりづらくはない。
　FFTに慣れていないのが出てしまった、という感じ。
　
時刻: 0 件のコメント:
ラベル: ,
登録: 投稿 (Atom)