練習メモ2-2

めも。２月で二回目という意味。
yukicoder 482
https://yukicoder.me/problems/no/482
ソートの最小回数を判定する。
UFしてグループ数-１を足したら通った。

yukicoder 483
https://yukicoder.me/problems/no/483
無向グラフで一つの連結成分に2つ以上閉路があるとダメ。
情けないことに解法はわりとすぐにわかったのに実装できなかった。
関節点に似てるからDFSでいけそう！と思ってずっとDFSを考えていたのだが、ordが二回以上更新されたらダメ、みたいな変な嘘解法しか思いつかなかった。
でも結局難しいことする必要はなくて、ある連結成分について
辺の数 > 頂点数
なら絶対に２つ以上閉路があるのではい、という。
https://yukicoder.me/submissions/149452

冷静になれば解けるのになあという問題が解けないの、非常に悲しい。

[追記]
DFSなら単にぶつかった回数を２で割ると閉路の数になる。
https://yukicoder.me/submissions/149506
また、マッチを左側、座標を右側とした二部グラフの最大マッチングがマッチの本数と等しいか判定する問題に帰着して解くこともできる。
http://yukicoder.me/submissions/149854

CF　382 div2 D
http://codeforces.com/contest/736/problem/B
ゴールドバッハ予想を知っているかどうか。
さすがにひどい。

TopCoder 707 div1 easy
僕は
ababababab...
cdcdcdcdcd...
e
f
g
h
i
...

でやった。チャレンジの感じからすると１０通りくらいは解法がありそう。
テストしたのでさすがに通ったが、40分くらい何も思いつかないみたいな時間があったので点数は低かった。写経をミスったので-25もくらった。ただまあわりと面白かったのでいいかな。構成ゲーはチャレンジが面白い。

実力の向上が横ばいになりつつある感が強く、険しい。