ABC142

開始前37.0、Fを考えてるとき37.1、終了後37.2。開始前体が熱かった。昨日のyukicoder調子よかったから期待してたけど3TLEを出すなどの惨状で気分が転落した。本当につらい。こんな気分のまま寝るの?眠りにつくまでの30分から3時間くらいの時間をこんな気持ちで何もせず。うわあああああ!!!!

(追記)復習とゲームで眠くなるまで時間をつぶし、結果的にはそこまで苦しまず眠れた。よかったー。

A - Odds of Oddness

めちゃんこ難しいやん。奇数の個数を求める方針。n/2って書いたら偶数の個数だったのでnから引いた。

B - Roller Coaster

Bなのに10^5。でもAより簡単だった。

C - Go to School

遠まわしな言い方だけど、要するに、出席番号iの生徒はA_i番目に入ってきたということ。よくある書き方で b[a] = i; とすればよい。

D - Disjoint Set of Common Divisors

丁寧に説明されていて、よい。公約数は最大公約数の約数と同じことなので、最大公約数がどんな素数たちでできてるか調べて、K種類の素数が使われてたらK+1が答え。解けてみると、10^12という制約があからさま。

E - Get Everything

Dまで簡単だったのでこれもまさか超簡単なのかと思ってしまったが普通に簡単めなだけだった(なぜかMが12個しかないようなコードを書き始めてた)。鍵が2^N通りしかないのでそっちで考える(同じ鍵が複数あったら最安だけを使う)。O(N*(2^N)^2)でDPできるのでまあちょっと重めだけど、いつも5000^2とか100msかからんし問題ない。INFとして2^30を使うと和がオーバーフローすることに気づいてちょっと煩雑になってしまった。

F - Pure

ループを見つければよさそう(最小で2頂点からなるループだね)。問題は誘導グラフになってないときだけど、邪魔な辺があったらより小さいループが構成できてるよね。これをO(N)回繰り返せば条件を満たすものに必ず辿り着く!計算量も2乗程度なので余裕。ということで実装。閉路検出はよくわかってなくて苦手意識ある。探索中と探索済みのフラグを持ち、閉路が見つからなければ-1。閉路を具体的に求めるのもきつい。祖先に出会ったら祖先に戻るまで他のノードを探索せず頂点をvectorにpushしていく。余分な辺の発見は、std::setに現在のループを構成する頂点たちを入れといて(setじゃなくてvectorでいいって気づいたけど直すの手間なのでそのまま)、出てる辺が次の頂点でなくてかつループに含まれてるときそこで短絡してしまう(つなげなおす処理がけっこう複雑になってしまった)。それを高々N回繰り返せばいいはずだ。

しかしTLE。原因は、ループを発見してもなおループを発見しようとDFSしてたこと。直して提出するがまたTLE。1回のDFSの中で何回もループ発見することがありえる。直して提出するがまたTLE。ループの長さがNより大きくなったらthrowするようにして処理回数もN回に制限して提出、WA。うーん、解法が正しいならこうはならないはず。解法が間違ってるのかあ(あるいはまだバグがあるのかもしれないけど)。ギリギリまで考えてもわからず、とりあえずWAになってる無出力ケースで-1を出すようにしたのを最後に提出してみたが、まあWAだよね。うーん、どこに穴があるのか。そもそも、コードが汚いのがよくない。よほど理解がしっかりしてるときでないと汚く書いて時間短縮はないよなあ。そういうときは大抵きれいに書けるし。

(追記)解法はあってて、単純バグだった。結果的に閉路を検出して出力するだけのコードになっていたが、それで2個しかWAにならないんかい。バグが多いのは、このへんの処理の理解が浅いってことだからしゃーない。