7/17 School Daysを1話からちゃんと見た

ニコ動でSchool Daysが無料配信になっていたので見ていた. 実は最終回しか見たことなくて, 1話からちゃんと見るのは初めてだったりする. 1話見るごとに「誠死ね」という思いがどんどん募っていく作品だった. もう少し誠に葛藤とか苦悩とかがあればそんなに胸糞悪くなく見れると思うんだけどなー. 正直コメントなしで見るのは割とつらいかも. でも, 総じて面白かったです. 昔の名作をどんどん見てアニメ力上げていきたい.

アニメ「School Days」期間限定無料配信|ニコニコインフォ

Educational Codeforces Round 25

結局ABCDを解いておしまい. Bは後から落とされた.

• Problem - A - Codeforces [解答]

  0でsplitして, 1の数を数え上げて各桁の数にすればOK.

• Problem - B - Codeforces
  10 * 10の中の連続する5マスを全部チェックして, 'X'が4つと'.'が1つある箇所があればYES, そうでなければNO. と思ったのだがハックされた. 何がいけなかったんでしょうねぇ.

• Problem - C - Codeforces [解答]
  Aiを昇順にソートしてgreedy. それまでに解いた最も難易度の高い問題の難易度をkとする. 最初はk = Mとしておく. Aiを一つづつ見ながら, k * 2 >= Aiなら解ける, そうでなければ, 現状で解ける最大の難易度(k * 2)の問題を他のオンラインジャッジで解いてkを上げていく.

• Problem - D - Codeforces [解答]
  よくわからなかったので二分探索してsuitabilityの最大値を計算, そこから'?'を置換した. 問題のタグにgreedyって付いてたし, もしかしてもっと簡単にできるのかも.

• Problem - E - Codeforces [解答]
  1時間ぐらい考えていたけれど, 結局ACできなかった. どうやら辺を逆向きにすると解けるみたいなのだけど, なぜだかはよく理解できてない.

ABC061

• D: Score Attack - AtCoder Beginner Contest 061 | AtCoder [解答]
  辺のコストの符号を逆にすると, 頂点1から頂点Nまでの最短距離問題になる. 負の辺を含む最短経路問題なのでベルマンフォード法を使えば良さそう. 問題の設定では頂点1から頂点Nまでの中に負の閉路があるかを検出する必要がある. グラフ全体で負の閉路を検出するには, ベルマンフォード法の更新が頂点数以上起きたかどうかを見れば良い. しかし, 今回は1からNへの経路中以外に負の閉路があっても答えはinfにならない. というわけで, 1からNへの経路中だけに負の閉路があるかを判定する. これは更新をN - 1回行った結果とN回行った結果が一致するかを見れば良い.