geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

ABC213 参加記録

C - Reorder Cards

座標圧縮の問題です。

座標圧縮は昇順ソートして、小さい方から順に順位を割り振っていけばよいです。

 

例えば、{3 5 7 7 8 10}は、{1 2 3 3 4 5}です。

順序関係を崩さないように、小さい数字を割り当てていくと考えればよいかもしれません。

 

行と列は独立に考えられるので、それぞれについて座標圧縮を行います。

 

出力でi行目にはiの書かれたマスの座標を出力するというのができておらず、2WAしてしまいました。

入力の座標情報は残しておいて、座標圧縮の変換表を用意してACしました。

提出コード:https://atcoder.jp/contests/abc213/submissions/24869750

 

D - Takahashi Tour

まず、典型としてN頂点で辺の数がN-1の場合は木であること理解しておく必要があります。

 

問題文が少しややこしいですが、「番号が小さい方を優先させるDFS」を行い、訪れた順に都市の番号を記録し、それを出力すればよいことがわかります。

 

実装に手間取りましたが、実装は以下のようにしました。

まず、入力のグラフを隣接リスト形式で保存し、各都市について、接続する都市の番号を昇順ソートします。

都市1のみと接続する都市0を用意し、都市0からDFSを開始します。

都市uからvに移動した時に、「訪問した都市」を保存する配列にvを追加します。

また、都市vでの探索が終了し、都市uに戻ってきた時も都市uを配列に追加します。

これを、繰り返し都市0に戻ってきたら終了です。

なお、答えの最後には都市0が残るのでこれは出力しないようにします。

 

余談ですが、オイラーツアーでも似たような実装したことがありました。

 

提出コード:https://atcoder.jp/contests/abc213/submissions/24876471

 

E - Stronger Takahashi

今行けるマスの中でパンチ数が最小のマスは他の移動経路でそれよりパンチ数が小さくなることはないので、最小パンチ数を確定できます。(そうでなければ、そのマスに向かう他の移動経路上のマスの最小パンチ数が先に確定するはずです。)

よって、パンチ数をコストとしたダイクストラ法が適用できます。

 

通常のダイクストラ法だと、パンチした時が困ります。

そこで、「移動予定のマスが塀であったとき、パンチ数を+1して、そのマスを中心とした3×3に同じパンチ数で移動できる」ようにします。

何故3×3になるかと言うと、中心でパンチを放ったとすると、右上、左上、右下、左下のいずれかを含む2×2マスの塀を破壊可能であるためです。

 

計算量としては、マスの数がNKで、上下左右4マスへの辺と上下左右から更に9マスへの辺を辿るので、ざっくりO(36NKlog(NK))くらいでしょうか(自信はありません)。

提出コード:https://atcoder.jp/contests/abc213/submissions/24885588