AtCoder ABC277 (2)

本番で解けなかった問題を解いてみる。

atcoder.jp

D問題（44分）
  1. カードの数字はmod Mした数字とみなす（M=20なら21は1と同じ）→そもそも数字はMより小さい
  2. 連続した数値のカードを塊とする（3 4 5 5 6と7 7 8は別の塊）
  3. それぞれの塊の合計値を求める。合計値が最大の塊を除いたカードの合計値が答え。
  4. ただし、M=20の時19と0は連続できることに注意。

で解ける。1は勘違いで、M以上の数字が書かれていると上の方法で解けない（M=20の場合に35から16につながったり、合計値を求める時に数値がmod Mしていると変になる）。

E問題（40分）
  1. あるノードでスイッチを押すことは、そのノードで表世界と裏世界を移動することに相当する
  2. a=1の場合には表世界のグラフでつながる。
  3. a=0の場合には裏世界のグラフでつながる。
  4. 表と裏と言っているが、表のノード番号＋Nを裏のノード番号にするなどで大丈夫

と考えて問題変換すると、

  1. a=1の場合、uとvはコスト1の枝でつながっている。
  2. a=0の場合、u+Nとv+Nはコスト1の枝でつながっている。
  3. スイッチがuにあれば、uとu+Nはコスト0の枝でつながっている。

グラフの最短経路問題（1からN）として解ける。

C++ダイクストラで検索し、priority_queueを使った関数を拝借して解く。

今後の改善点

  • 自前でグラフ理論のライブラリを用意。
  • priority_queueの使い方。
  • struct edge{int to; int cost;};を簡単に初期化する方法→edge e{3, 5}。コンストラクタ書かなくてもedge e(3, 5)も動くみたい。