titiaのノート: トポロジカルソート

　二点の交換しかできないので、たくさん門松列になっていないものはそもそもダメ。少なくとも一つはダメなところを交換に使わなくてはいけないから、「ダメなところとそれ以外のどこか」を交換する全探索すれば良い。交換後に門松列列になっているかどうかは、元々門松列になっていて交換に絡まないところはチェックしなくて良いので、「ダメだったところ」と「交換した箇所の周囲」だけチェックすればOK。

　この「たくさん」とか「周囲」というのが具体的にどれだけか考えるのがややこしくてWAを出したけれど、安全を取って大き目に取ればACできました。

　最初から大き目に取るべきでした。

No.1370 置換門松列

　公式解説と同じことを考えていたけれど、同じことをやっても（Phase 1のチェックをしていても）A[i]=A[i+2]となるケースを除けない気がしてしまった。

　トポロジカルソート順に決めたとき、別の数に同じ数字が割り当てられる可能性がある気がしてしまったせいだと思うんだけど、そんなことは起こり得ない。

　検証したら気付いたと思うので、変に悩まず、図を描いたり実装したりすべきでした。

2021年1月18日月曜日

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

　マラソン（ヒューリスティック）形式の問題が含まれるコンテストでは、まずその問題から見るようにしています。

　その問題にちょっと不備があった、というのが後の出来に多少は影響したかもしれないけど、Cで苦戦しDが解けない、というのは情けなかった。

コンテストへのリンク

コンテスト後のツイート

C - A + B

　次数を考えれば良い。

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

D - Animal Show

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

　ただ、これだと辺の数が大きくなり過ぎる。

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

　これ、基本的にはKahnのアルゴリズムをやろうとしています。入次数が0になるところを探す、という処理をしている。

　ただ、そういうとことをしようと思っても、色々混乱して正しいコードにするのにはかなり時間がかかってしまった。

　公式解説はシンプルですね。

　頂点を増やした方が辺が減るのか。なるほど確かに。

E - 老朽化対策

　解説AC。

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

　最近、平方分割系の問題に続けざまに出会った気がする。（これとこれ）

登録: 投稿 (Atom)

2021年1月30日土曜日

Educational Codeforces Round 103 (Rated for Div. 2)

B. Inflation

E. Pattern Matching

yukicoder contest 280 (門松コンテスト)

No.1369 交換門松列・竹