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

2025年11月12日水曜日

Codeforces Round 1063 (Div. 2)

　D2まで。

コンテスト後のツイート

E. Plegma

　何をやっても通りそうな問題なのに通せなかった。


　思いつくかどうかの問題なのであまり反省しようがない。
　secondへ持っていく情報を最大限生かすにはどうしたらいいだろうか？　みたいなことを考えるべきだったか。





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

2025年11月7日金曜日

AtCoder Beginner Contest 430

　Fまで。

コンテスト後のツイート

G - Range Set Modifying Query

　解説放送を見てAC。
　Segment Tree Beatsを初めて実装した。非常に苦労した。

　そもそも、何を持つ必要があるか理解するのが難しい。

SEG=[0]*(2*seg_el) # max(bit_count)が最大なものの素の値
SEG2=[ALL]*(2*seg_el)# SEG[i*2]とSEG[i*2+1]での共通bit
SEG3=[0]*(2*seg_el) # bit_count()の最大値
SEG4=[0]*(2*seg_el) # 最大値を取る要素数

LAZY0=[0]*(2*seg_el) # 遅延伝搬すべき要素。追加の場合。SEG2が1のbitのみ、下へ伝播する。
LAZY1=[0]*(2*seg_el) # 遅延伝搬すべき要素。削除の場合。SEG2が1のbitのみ、下へ伝播する。

　と定義してやったが、LAZYが二つ必要なことに気付かず、ずっと悩んでしまった。
　ちゃんと抽象化していたとしても、ここで悩んでしまったと思う。

　そして、最後まで引っ掛かったのは、[L,R)の範囲外でも、updates内で下のノードへ行かなくてはいけないときも、遅延伝搬を行わなくてはいけないところでした。
　ここはデータ構造を理解していれば（あるいは、ライブラリを整備していれば）引っ掛からなかったはずのところ。こっちのミスは減らせますね。



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

2025年11月3日月曜日

Pinely Round 5 (Div. 1 + Div. 2)

　Dまで。

コンテスト後のツイート

E. Left is Always Right

　非常に苦労してAC。
　コンテスト中の考察は正しかった。あとはそれを数え上げるだけだった。

　ただ、自分は、index i-1まで0が続き、index iで初めて1が登場するという、このindex iで場合分けしてた仕上げようとしていた。
　すると、終盤が繰り返しのパターンではないとき、それぞれについて、計算量が[i,n)の長さ程度かかってしまう。その中にある0,1,？の個数を見て、?が何個以下0になる……という二項係数の和になってしまうため。

　そうではなく、計算量を良くするためには、繰り返しパターンでないときは一気に数え上げられる、という発想の転換が必要だった。
　index n-kまで0が続いたのなら、残りは、0や1がk/2個以下ならどんな並びでも良い。なので、場合分けをしないことで一気に数え上げることができる。

　こうすると計算量を減らせる。
　このことに長いこと気付けなかった。公式解説を見ても、二項係数の和で表せる、としか書いていないのが辛い……。二乗ではあるけれど二項係数の和では表せたので、公式でどうにかなるのでは？　などと考えてしまった。


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