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

AtCoder Beginner Contest 218

https://atcoder.jp/contests/abc218

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

A - Weather Forecast

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

文字列のスライス

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

B - qwerty

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

chr関数

• 数字→文字列はchr関数でこなすとお洒落
  • chr(i)で、Unicodeコードポイントである文字が文字列strで返される
  • 反対向きの変換はord(s)
  • https://note.nkmk.me/python-chr-ord-unicode-code-point/
  • 'a'はchr(97)
  • chr(96 + i)で、iを1~26で当ててあげれば良いね

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)らしい。