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追記)解きました

感想

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