問題ページ Aizu Online Judge Arena 解法 １つ目の削除方法が可能なペアに2つ目の削除方法を適用する意味はあるのか考えると、操作回数で得できるわけではなく無駄にペアが多く消えているので得することはなさそう（要証明）。なので、1つ目の削除方法が可…

問題ページ Aizu Online Judge Arena 解法 あみだくじで最終的にどこにたどりつくかのみが重要なので途中の横線の位置を気にする必要はない。縦線3本のあみだくじでは 3!=6通り の置換にまとめられる。 恒等写像にならないような置換の組み合わせを考える。(…

問題ページ Aizu Online Judge Arena 解法 拡張dijkstraをする。頂点を(i番目の街灯,コストj)とする。 遷移について 始点から街灯 始点と街灯のマンハッタン距離のコストをかけて街灯を明るくする必要がある 街灯から終点 街灯と終点のマンハッタン距離のコ…

問題ページ Aizu Online Judge Arena 解法 1回操作すると文字列の長さは少なくとも半分になるので操作回数はO(log|S|)程度になる。 x回操作するために文字列s中にどのような文字列が必要か考える。x=1では文字列sの部分文字列としてtが存在していれば操作が…

問題ページ Aizu Online Judge Arena 解法 価値が低いものを価値が高いものより優先する意味はない。各色iで取る可能性のあるボールは価値が高い上位l[i]のみに絞られる。さらにこのボールの中から価値が高いボールをM個選べば答えが求められる。 ナップザッ…