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 件のコメント:
ラベル: ,
登録: コメント (Atom)