ラベル 平方分割 の投稿を表示しています。 すべての投稿を表示
ラベル 平方分割 の投稿を表示しています。 すべての投稿を表示

2026年7月4日土曜日

yukicoder contest 503

　Eを考えていたが解けず、Cのみ一完。

コンテスト後のツイート

No.3580 二成分の和

　解説AC。

　一目見て、連立方程式だから行列……と思ってしまったが、それが間違いだった。
　グラフの問題だと思えば、自然と、連結成分ごとに一つの要素の値を決め打つ、というのが思いつく。

　行列で上手くいかないと思えば、この解法に至るのがそう難しい気はしないんだが……。一旦思い込んだものを方針転換するのは難しい。

No.3581 分数対称差更新区間計数取得

　TLEが取れず、ChatGPTにPyPy→RUSTに変換してもらってAC。

　各クエリにおいて、変更すべき点が√i個に収まるので、BITで管理してACした。

　だが、解説を見ると、平方分割した方が高速になるらしい。言われてみればそういう高速化を要求されたことがあった。忘れていた。


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

2022年3月9日水曜日

AtCoder Beginner Contest 242

 　Eまで五完。

コンテスト後のツイート

F - Black and White Rooks

　解説放送を見てAC。

　コンテスト中、包除原理だと思ったが、詰められる気がしなかった（及び、Gの方がAC人数が多かった）ため飛ばした。

　意外とシンプルな包除で、多分解説を見なくても解けたと思う。
　解説を見ても何を前計算ができるかピンと来ず、毎回包除をやるのだから八乗になってしまうのでは？　と思ったが、自分で書いて見たら納得できました。こういうのは実際書いてみた方が分かりやすいですね。

　あと混乱していたのは、包除原理で「黒が使う行がk1行, 列がl1列。白が使う行がk2行, 列がl2列の場合の数」を求めるとき、そのk1, k2, l1, l2が小さいバージョンの答えを使う（それらを除いていく）のか？　と考えたこと。
（公式解説を見るとこれでも解けた模様。公式解説の「1. 動的計画法による解法」ですね。なんかこの方法も包除原理の一種と思っていた気もするけど、「これは包除原理じゃない」ということを頭に叩き込みたい）

　包除原理でそれは使わないのですね。
　「黒が使う行がk1以下, 列がl1以下。白が使う行がk2以下, 列がl2以下の場合の数」というものたちだけから「黒が使う行がk1行, 列がl1列。白が使う行がk2行, 列がl2列の場合の数」を求められる、というのが包除原理なのですね。

G - Range Pairing Query

　解説放送を見てAC。

　Mo’s algorithmは平方分割の一種と思っていたのですが、具体的には理解していませんでした。「二次元のクエリを先読み＆平方分割」と思って良いのかな。
　二次元クエリを平面上にプロットしてみると分かりやすかった。二つパラメーターがあるとき、困ったら平面にプロットしてみるのは鉄板ですね。

　参考：昔のMo’s algorithmの問題

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

2021年10月27日水曜日

サイシードプログラミングコンテスト2021（AtCoder Beginner Contest 219）

　Eまで五完。


F - Cleaning Robot

　解説放送を聞いてAC。
　方針が思いつけなかったけど、

　文字列一回で移動する量(x, y)が重要そう　→　(x, y)の何回かの移動で一致するものをひとまとめにして考えよう

　というのは結構自然に思える。

　理解できた後も、「どうしてこんな解法思いつくんだろう？」みたいな問題は仕方ないけど、分かってしまえば簡単、のような問題には食らいつきたいね。

G - Propagation

　平方分割と言われれば解ける。
　しかし、平方分割に気付けなかったのは問題。類題経験もあったのに。
時刻: 0 件のコメント:
ラベル: ,

2021年1月18日月曜日

パ研合宿2020　第2日「パ研杯2020」

　マラソン（ヒューリスティック）形式の問題が含まれるコンテストでは、まずその問題から見るようにしています。
　その問題にちょっと不備があった、というのが後の出来に多少は影響したかもしれないけど、Cで苦戦しDが解けない、というのは情けなかった。


C - A + B

　次数を考えれば良い。
　思いつけばシンプルだけど思いつかないと厳しい……というタイプの問題なので仕方ない面はあるけど、次数を考えるのは定石の一つなので、素早く思いつきたかったところ。

D - Animal Show

　動物aにアレルギーを持っている人が全員ショーを行ったら、動物aを使ったショーができる。ということは、人を頂点とし、ある動物に対して「アレルギーを持つ人」から「ショーで使う人」に辺を引いて、トポロジカルソートをすれば良い。（ちょっと戸惑ったけど、ここまではコンテスト中に分かった）

　ただ、これだと辺の数が大きくなり過ぎる。
　なので、グラフを陽にもたず、「各動物について、その動物のアレルギーを持っている人は何人か」「各人について、まだショーに使用できない動物は何種類か」というリストを持っち、それぞれが0になったら適切な処理をして……として解いた。

　これ、基本的にはKahnのアルゴリズムをやろうとしています。入次数が0になるところを探す、という処理をしている。
　ただ、そういうとことをしようと思っても、色々混乱して正しいコードにするのにはかなり時間がかかってしまった。

　公式解説はシンプルですね。
　頂点を増やした方が辺が減るのか。なるほど確かに。

E - 老朽化対策

　解説AC。
　なるほどとは思うものの、そもそも座標の最大値・最小値をあまりチェックしていなかったので思いつけなかった気がする。確かに、$5*10^4$とちょっと小さめなのは気になったけど……。こういうところにも気を配らなきゃいけないのね。

　最近、平方分割系の問題に続けざまに出会った気がする。（これとこれ）
時刻: 0 件のコメント:
ラベル: , ,
登録: 投稿 (Atom)