2022-05-13 ABC109 の A, B, C, D を解いた / チョコスティックパンの絵
ABC109 : AtCoder Beginner Contest 109 の A, B, C, D を解いた。
- A - ABC333
https://atcoder.jp/contests/abc109/tasks/abc109_a
- 提出: https://atcoder.jp/contests/abc109/submissions/31636034
- C = 1, 2, 3 の 3 通りなのですべて試せば良い
- B - Shiritori
https://atcoder.jp/contests/abc109/tasks/abc109_b
- 提出: https://atcoder.jp/contests/abc109/submissions/31636078
- 指示通りにシミュレートする
- 重複は BTreeSet などで管理する
- 2 番目の要素から走査して一つ前の要素の末尾と現在の要素の先頭が不一致のものがあれば No で抜ける
- C - Skip
https://atcoder.jp/contests/abc109/tasks/abc109_c
- 提出: https://atcoder.jp/contests/abc109/submissions/31636161
- x に X を加えて昇順に並べたものを A とする
- A_1 から D 刻みで移動して A_i すべてに止まることができれば良い
- A_{i+1} - A_i が D の倍数なら良い
- 最大の D なので A_{i+1} - A_i の最大公約数を取れば良い
- D - Make Them Even
https://atcoder.jp/contests/abc109/tasks/abc109_d
- 提出: https://atcoder.jp/contests/abc109/submissions/31636456
- 偶数枚にすれば良いこと・各マスは最大 1 回しか操作しないことから a_ij は 0 or 1 で十分に見える
1同士を組にすれば良いが 1 回しか動かせないのでどう動かすべきか迷う- 直感的に遠い者同士を組に割り当てる意味はない
101とあったとき左右から中央に集めずとも右に寄せれば良さそうだ- 上下も同様で下に寄せれば良さそう
111のような場合も001のあと左に寄せても仕方ないので下に寄せる- 怪しいけどこれで良さそう、で AC
- 解説によると一筆書きが正解っぽい、なるほど確かに
- ただ
1が奇数個の行から 1 行下に寄せたあと右に寄せようが左に寄せようが偶奇は変わらなさそうなので問題なさそう
4 完できた。
上の子が保育所で「好きな絵を描け」と言われて、チョコスティックパンの絵を描いたと聞いて笑ってしまった。
今日のコミット。