AtCoder Beginner Contest 010

　一日でも放置したらやらなくなりそうなので。

結果

　399/400　52:09　46位相当

　開始時刻　2017/07/25 15:04:00　提出履歴

A: ハンドルネーム - AtCoder Beginner Contest 010 | AtCoder

　0:53(AC)

　文字列クラスのありがたみを感じる問題。何も考えずにS+"pp"でAC。

B: 花占い - AtCoder Beginner Contest 010 | AtCoder

　5:54(AC)

　1<=a<=9なのでmapを使ってもいいかもしれない。a%2==0かa%3==2だと「嫌い」が出てしまうので、そうならないようにaを調整して、最後にちぎった総和を出力。

C: 浮気調査 - AtCoder Beginner Contest 010 | AtCoder

　13:15(AC)

　(txa, tya)→(x, y)→(txb, tyb)の順に動いてT分に間に合うパターンが一つでもあればYES、そうでなければNO。

D: 浮気予防 - AtCoder Beginner Contest 010 | AtCoder

　52:09(WA, 99/100)→96:37(TLE, 99/100)

　とりあえず最初は100点方針が思い浮かばず、各友人関係について、解消する・しないで場合分けする2^Eの全探索をして99点を貰いに行く。書いているうちに、グラフの最小カット問題に帰着できそうな気がしてくるけど、パスワード変更がどういう意味を持っているのかわからず、とりあえず後回しで99点解答を実装。

　時間をかけてパスワード変更について考察する。メッセージを受け取ることが最終目的なので、そういう状態に遷移する辺を考え、それがパスワード変更によって切られると考える。すると、一連の問題が最小カット問題に帰着できた。

　…帰着できたけど、実装できずにまごつく。よくわからないままにコードを組み、TLEを吐いて終わった。フォード・ファルカーソンのアルゴリズムってどうやって実装するの…。

　（7/29追記）解きました。

感想

　グラフの問題は考察もさながら実装が難しいのでつらいです。夏休みの間に主要なグラフ関連のアルゴリズムは抑えたいなぁ。