2

ABC218 茶色コーダーが解けた所まで+あと1問

7 min read

AtCoder Beginner Contest 218

https://atcoder.jp/contests/abc218

ABC218の問題を、本番で自分が解けた所+1問の解説です。
初めて色がついたので投稿してみました。
茶色を維持しつつ、次は水色を目指したい。

A - Weather Forecast

https://atcoder.jp/contests/abc218/tasks/abc218_a

文字列のスライス

  • S[i]S[i]で、i+1i+1文字目が抽出できる
  • 0indexなので注意
  • 後はif文で条件に従ってあげる。



B - qwerty

https://atcoder.jp/contests/abc218/tasks/abc218_b

chr関数

  • 数字→文字列はchr関数でこなすとお洒落





C - Shapes

https://atcoder.jp/contests/abc218/tasks/abc218_c

平行移動の話

  • 回転が不要な状態で、図形Sを平行移動を繰り返した時に図形Tと一致するか否かを考える
  • 縦横に並行移動する必要がある?
    • グリッド上にあるS、Tの場所がズレているなら、平行移動する必要がある
      • 場所がズレている=図形S、Tの上下左右に存在する、'#'の含まれていない行の数が異なっている
    • つまり、図形S、Tの上下左右に存在する、'#'の含まれていない行を全て削れば図形は一致する筈

回転の話

  • numpyのrot90でかんたんに90度回転できる



D - Rectangles

https://atcoder.jp/contests/abc218/tasks/abc218_d

長方形を一意に定めるには

  • 左下の頂点と、右下の頂点を決めると長方形が一意に定まる。
  • 条件より、2000個のうちから2つの組み合わせで全探索



E - Destruction

https://atcoder.jp/contests/abc218/tasks/abc218_e

考え方

  1. 先に道を全部外してプラスの報酬を全て受け取る
  2. 報酬がマイナスの道に関してはとりあえず繋ぐ
  3. 報酬がプラスの道を、報酬が小さい順(昇順)に並び替える
  4. まだ繋いでない(報酬がプラス)道の、一番報酬が小さい道を取り上げる。
    • Q:道の両端の地点は既に繋がっている?
      • 繋がっている場合→繋ぐ必要が無いので、報酬はそのまま(貰ったまま)
      • 繋がっていない場合→繋ぐ必要があるので、報酬を返却して道を繋ぐ

UnionFind木

https://www.slideshare.net/chokudai/union-find-49066733/1

  • 行程4の、「グラフの2点が繋がっているか?」の判定と、「グラフの2点を繋ぐ」を速く行うためのデータ構造
  • O(log n)らしい。



Discussion

コメントにはログインが必要です。