hotpepsiの練習帳

Codeforces 390

00:22

http://codeforces.com/contest/754

C. Vladik and chat

問題

• チャットのログがある
• 同一人物の連続する発言は1行にまとめられる (＝連続する行は発言者が異なる)
• 自分のIDは発言しない (＝発言中にハンドルネームがある場合、発言者はそれ以外である)
• 発言者が不明な場合がある
• 発言者を補え

方針

• 不定の行について考える
• strtokでトークンに分割して、ハンドルネームの場合、候補から外す (setで全IDを持っておいて、ハンドルネームがあったらeraseしていく)
• 残った候補をランダムで選んで、前後と違うハンドルネームならOK
• 10万回くらいやってみて、だめならImpossible
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/codeforces_3xx/cf_390/c.cpp

結果

ooo-- 1687 -> 1785

面倒でみんな諦めるだろうからと思ってやってみた。