きろく

特筆すべき記録のまとめ

Chokudai SpeedRun 002:I - カツサンドくん β

問題

atcoder.jp

解法

食べ物を 1 ~ N の順番に見ていく.また,最初の暫定的な「最強の食べ物」を食べ物 1 としておく.今,食べ物 i を見ているとき,どちらが勝つかどうかは簡単な四則演算で求まる.もし,食べ物 i が勝つときは暫定的な「最強の食べ物」を食べ物 i に変更する.なぜならば,食べ物 1 ~ (i - 1) は絶対に「最強の食べ物」になりえないから.そうでないときは変更しない.この処理をした後,決まった暫定的な「最強の食べ物」が他の全ての食べ物に勝つかどうかを調べる.これは,引き分けとなってしまう場合を見つけたり,食べ物 a が食べ物 b に勝ち,食べ物 c が食べ物 a に勝ったからと言って,食べ物 c が食べ物 b に勝てるとは限らないから.全体で O(N).

解答

atcoder.jp

f:id:babcs2035:20190526145711p:plain