ラベル 遅延セグメント木 の投稿を表示しています。 すべての投稿を表示
ラベル 遅延セグメント木 の投稿を表示しています。 すべての投稿を表示

2026年1月22日木曜日

AtCoder Beginner Contest 441 (Promotion of Engineer Guild Fes)

　Fまで。
　Fは初めから解法は合っていたので、どうしたら良かったのか悩む。定数倍高速化を頑張るより、codonを試す方が良いんだろうか？

コンテスト後のツイート

G - Takoyaki and Flip

　解説・解説放送を見てAC。

　遅延セグメント木を使うとは分かっていたが、基本的なことからおかしかった。
　もつデータを（最大値, flipしているか）だけで良い気がしていたが、それだと、複数の皿が「全て表か、全て裏か」の二通りの状態しか表せないので明らかに間違っている。

　それを解消するため、表の皿が何枚で裏の皿が何枚か、というのをもつようにすれば自然と遅延セグメント木に乗る。

　ただし、遅延させるものは、

・(a, b)　a回flipした後、b加算

　なのだが、(a, b)の後に(c, d)を行うのと、(c, d)の後に(a, b)を行うのとで結果が違うことに注意が必要だった。
　自分が解いてきた問題は、ここが可換なことが多かった気がする。順番に注意しなくてはいけなかった。

　ところで、PyPyだと1873msなのだが、codonだと301msでした。codon凄い！


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

2024年11月14日木曜日

Codeforces Round 971 (Div. 4)

　G1まで。

コンテスト後のツイート

G1. Yunli's Subarray Queries (easy version)

　そもそもクエリの種類がn種類しかないのにMoを使ったのはおかしかった。
　順番に求められますね。

G2. Yunli's Subarray Queries (hard version)

　こたつがめさんの放送の振り返りを見てAC。

　Div.4だから、という先入観があったからかもしれないけど、遅延セグ木を使うと思いつかなかった。
　典型ではあるかもしれないけど、簡単ではないね。


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

2024年7月31日水曜日

AtCoder Beginner Contest 322

　Eまで五完。

コンテスト後のツイート


F - Vacation Query

　コンテスト後、Pythonで遅延セグ木を使った実装だとTLEになる……という話を聞いて避けていたのをようやく実装。
　普通に遅延セグ木で通りました。（ただし、二重配列にしないという工夫はしている）

　なお、ツイートで書いている解法だと、遅延セグ木に乗せるものが足りていないですね（多分、実際に実装したら気付いたでしょう）。

　演算が多要素×多要素の場合も簡単に書けるように、遅延セグ木をライブラリ化しておくべきですね。


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

2024年6月9日日曜日

サントリープログラミングコンテスト2024（AtCoder Beginner Contest 357）

　Eまで五完。

コンテスト後のツイート

F - Two Sequence Queries

　自力AC。

　コンテスト中、遅延セグメント木を使えば解けると気付き、十分時間もあったのに解き切れなかった。
　いい加減に実装して数値を合わせようとするのではなく、ちゃんと、何が何個足されるのか考えてから実装すべきだったか。


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

2024年4月4日木曜日

ユニークビジョンプログラミングコンテスト2024 春（AtCoder Beginner Contest 346）

 　Fまで六完。

コンテスト後のツイート

G - Alone

　解説・解説放送を見てAC。

　各数字のx個目を見て、その数字を一つだけを含む区間がどこなのか？　というのを求める方法は分かっていたが、重なる区間の処理をどうすれば良いかが分からなかった。

　それが長方形区間に対応する→平面走査　と考え、遅延セグ木を用いれば処理できる。
　ただ、平面走査した後も、どう遅延セグ木を用いれば良いかは解説を見なければ分からなかった。ただ、ここは典型問題で、 （公式解説にも書いてある通り）Library Checkerにもあった。




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

2022年8月31日水曜日

AtCoder Beginner Contest 265

　Eまで五完だが、Eは嘘でした。

コンテスト後のツイート

E - Warp

　解法ツイートを見て改めてACした。

　（A, B）をi回、(C, D)をj回、(E, F)をk回使ったときは何通り？　という非常に自然なDPで良かった。
　最初見たとき包除原理に見えてしまい、そこから方針転換できなかったのは反省。

F - Manhattan Cafe

　解説放送を見てAC。

　単純なDPを累積和で高速化する問題だが、単純なDPすら思いつかなかった。
　というか、そもそも誤読していた。（格子点の数も二つだけと思ってなかったし、制約ももっと大きいものと思っていた）

　N次元空間などと言われると、苦手意識があるためまともに考えられなくなる気がする。空間把握などが必要な問題が解けないのは仕方ない部分もあるが、今回の問題は、定義に従ってDPを組むだけなので、空間把握などは不要な問題だった。

　苦手意識があると、つい考えることをやめてしまいたくなるが、ちゃんと問題を読み、定義に従って考えよう。

G - 012 Inversion

　解説放送を見てAC。

　セグ木を使いそう、というのは一目で分かった。セグ木の各要素として何を持てば良いか、というところで詰まってしまったが、これも自然に考えれば分かるものだった。落ち着いて考えれば自力で思いつけたと思う。

　ただ、実装には苦戦した。遅延セグ木を使うのだが、可換性が成り立たない演算があるため、自分のライブラリ（これ自体あまり整備されていないのだが）を修正しないといけない部分が多かった。この辺は慣れておきたい（遅延セグ木の整備もすべきか……）。

　難しくはないのだが、実際に通すのは結構大変。
時刻: 0 件のコメント:
ラベル: ,

2022年6月13日月曜日

エイシングプログラミングコンテスト2022（AtCoder Beginner Contest 255）

 　ABDEの四完で終了。Fは解きたかった。

コンテスト後のツイート

C - ±1 Operation 1

　コンテスト後、愚直解を書いて比較してAC。

　解法はツイートした方法で良かったが、Dが負の場合にもx%Dみたいな計算をしていたためWA。その部分をx%abs(D)に直したら通った。

　コンテスト中にコードを読み返して気付かないのはまあ仕方ない。ABCのCで愚直解を書くのはちょっとという気持ちになり後の問題へ行ったのも変なことではないと思う。まあ、あまり気にせずに。

F - Pre-order and In-order

　解説は読んだけど実装方法が今一つ分からず、自分の方法でAC。
　「通りがけ順（in-order）」というのは知らなかったけど、二分探索木とセットで理解しておくべき概念だったようです。

　ツイートに書いたように、

・頂点xがIでk番目に出現するとすると、Iでk-1番目までに出現する頂点が左側子孫、k+1番目以降に出現する頂点が右側子孫

　である。

　この境界はPにおいても境界になっており、その境目の直後の頂点が（存在すれば）xの右側の子になる。（左側の子は、Pにおいて次の点）
　なので、Pでこの境目のindexが何になるかが分かれば再帰で書けるが、コンテスト中はこの境目を求める方法が思いつかなかった。が、冷静になれば、これは二分探索で求められますね。

　解説ではO(N)でやっているようなのだけど理解できていません。

G - Constrained Nim

　自力AC。

　座標圧縮が本質の問題。

　Grundy数は基本的には1ずつ増える。ただし、問題文中の禁じ手に該当する個数の山があった場合は、定義通りにGrundy数を求れば良い。

　その際、今までに出現したGrundy数のうち、二回以上登場したものについて何回ずつ登場したかを覚えておくと、計算時間も間に合う。基本的には各数字は一回ずつ登場するので、二回以上登場するものは多くない（高々M回である）。

Ex - Range Harvest Query

　解説の遅延セグメント木の解法でAC。

　座標圧縮して遅延セグメント木を使えば良い、と言われればすぐ解けなきゃいけないのに、解説を読んでもなかなか理解できなかったのは反省。

　セグメント木の各ノードに「対応する区間ですでに収穫された実の個数」を持つ、ということをベースに考えれば、LAZY配列には「最後に収穫が行われた日付」を入れておくことで更新が可能になる、と分かりました。
時刻: 0 件のコメント:
ラベル: , ,
登録: 投稿 (Atom)