2022-09-06 ABC241 A, B, C, D を解いた

ABC241 : AtCoder Beginner Contest 241（Sponsored by Panasonic）の A, B, C, D を解いた。

A - Digit Machine https://atcoder.jp/contests/abc241/tasks/abc241_a
- 提出: https://atcoder.jp/contests/abc241/submissions/34653608
- 0 から p = a[p] を 3 回繰り返せば良い
B - Pasta https://atcoder.jp/contests/abc241/tasks/abc241_b
- 提出: https://atcoder.jp/contests/abc241/submissions/34653692
- A B の要素の個数をそれぞれ HashMap に入れる
- B の各要素の個数を A の各要素の個数が上回っていれば Yes
C - Connect 6 https://atcoder.jp/contests/abc241/tasks/abc241_c
- 提出: https://atcoder.jp/contests/abc241/submissions/34653887
- 各マスから開始して縦・横・斜めに '.' が 2 個以内かを調べる
- N <= 1000 なので 1000 * 1000 * 6 * 3
- 斜めが逆方向にあるのを忘れていて 1WA
- ↑をさらに 3 回 90 度回転させて試して AC
D - Sequence Query https://atcoder.jp/contests/abc241/tasks/abc241_d
- 提出: https://atcoder.jp/contests/abc241/submissions/34654853
- x の範囲が大きすぎるので座標圧縮する
- 各クエリは x 間の大小関係だけなので座標圧縮しても問題ない
- Q <= 2 * 10^5 なので x もその範囲に収まる
- FenwickTree で x ごとの出現個数を管理する
- クエリ 1 は FenwickTree の x の位置に 1 加算する
- クエリ 2 は FenwickTree の 0 から x までの範囲で個数が K 個の位置を二分探索する
- クエリ 3 は FenwickTree の x から Q までの範囲で個数が K 個の位置を二分探索する
- 二分探索の境界値を間違えて 2 WA
- 座標圧縮することで FenwickTree で扱える個数にした上で位置を二分探索する

調子が悪い。台風 (低気圧) のせいだろうか。

それとは別だろうけど昨日からお腹も壊している。

今日のコミット。