Codeforces Round #25 (Div 2 only)

例によってレート変動しないけど参加できるというあれ。

Result

2AC 00:16 / 00:23 / (4WA) / (7WA) / -
penalty 39

216位


あ、あれ……レート変動してたら大敗北だったんじゃ……

A. IQ test

PCの再起動しようとしたら更新インストールに時間かかって10分超の遅刻w

問題

n個の自然数が与えられる。
この中には一つだけ偶奇の異なる整数がある。それは何番目かを求めよ。

試行錯誤

evennessってなんだろ。偶数だけ探す?いや、偶奇の異なるものを探すのか。
そのようなものは一つだけであることが保証されているらしい。


奇数を数えて、仲間はずれをどちらか決定する方針。
書いた。送信。AC.

B. Phone numbers

問題

n桁の電話番号が与えられる。
これを、2桁または3桁の数字を組にするようハイフンを挿入せよ。
答えが複数ある場合、好きなものを出力せよ。

試行錯誤

桁が偶数だったら全部2桁ずつ区切ればいい。
奇数だったら最後だけ3桁にすればいいかな。


nが3以下の時は場合分け……
書いた。


あ、上の場合わけ全く要らなかったorz
送信。AC.

C. Roads in Berland

問題

n個の都市が双方向に通行可能な道路で結ばれている。
全ての2都市間の最短距離が与えられる。


ここに、k本の道路を新たに作る。
道路を一本作るたびに、全ての二つの都市の組の間の最短距離の和を出力せよ。


n,k≦300を満たす。
かつ、全ての距離は1から1000の整数である。

試行錯誤

1回毎にWarshall-Floydかな?あ、nが大きいからさすがに間に合わない。
というか題意の把握は合ってるんだろうか。
一回Warshall-Floydの愚直な解法を書いてみる。サンプル合った。理解は正しいようだ。


うーん?ちょっと考える。
a-bのエッジが更新されるとして、変化しうる最短距離は
i-jがi-a-b-jになるケースしかないような。


書いた。これでもサンプル通った。
送信ー。WA.


あれ、流石に方針違うのかなあ。
図を書く。
i-a-b-jにおいて、i-aが最短距離であることは保証されてる。b-jも同様。


なんだろ、ループを2回繰り返してみる。WA.


あ、i-b-a-jになる場合もあるじゃんorz
訂正。送信。WA.


でもちょっと先のケースまで進んだ。
えー間違ってないだろこれー。infが小さすぎるとかintから溢れてるとか?
や、そもそもinfは使ってない。
距離の和の最大値は、300*300*1000なので9000万なのでオーバーフローする訳はないよなあ。


えー。
これって、エッジの更新がなくなるまで繰り返すーとかやらなきゃダメ?
そんなん書くのめんどい……

D. Roads not only in Berland

問題

n個の都市のうちいくつかがn-1本の双方向に通行可能な道路により結ばれている。
1日ごとに、1つ道路を壊し、新たな道路を1つ好きな都市と都市を結ぶように作ることができる。
全ての都市が行き来できるようになるまでにかかる最短の日数と、道路の作り方と壊し方を求めよ。


n≦1000を満たす。

試行錯誤

エッジがループしている部分を検出して、そこからつながってない都市へエッジを張り替えればよいはず。
都市間が行き来できるかはunion-findを使って、ループの検出は再帰で書けばいいかな。


結構量が多くなってしまったけど書いた。サンプル合った。送信。
Runtime Error(case 3)
えー。今回酷いなあ。


Runtime Errorって何さ。再帰が溢れてるのか、vectorから要素を削除するときにイテレータが変なとこを指してるのか。
union-findを書き間違ってたりする?しないなあ。


原因がわからないのでsubmitデバッグ開始。

  • make_pairを使わずに書いてみる。RE.
  • iteratorが変なとこを指してる場合削除しないようにする。WA.

え、WAになった。
そもそもiteratorが変なとこを指すのはループの検出が出来なかったとき。
んなこたーありえないだろうが。


単純グラフだよな?二重辺とかないよな?
問題文読み直す。ないよな。意味わかんねえ。

  • ループが検出できてなかったらその時点でプログラム終了するように。WA.

あーやっぱりループの検出失敗してるっぽい。
意味がわからない。
エッジがn-1本だから、連結なら木になるはずで、非連結ならどこかに閉路が必ず存在するはず。合ってるよなあ?


その後もデバッグサブミットを繰り返してたら時間終了。