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追記)解きました。
感想
グラフの問題は考察もさながら実装が難しいのでつらいです。夏休みの間に主要なグラフ関連のアルゴリズムは抑えたいなぁ。