ABC120参加したメモ
https://atcoder.jp/contests/abc120/tasks
ABCの3完
提出: https://atcoder.jp/contests/abc120/submissions?f.User=skjmp
A:
- 算数して最小を取る
- 整数を上から抑える条件が2つ与えられるので、
- 2つの条件を満たす数のうち最大を答える。
- or 2つの制約のうち、条件が厳しい方(低い方)を答える。
B:
- 整数の集合「整数Aも整数Bも割り切る」が与えられるので、それのK番目に大きいものを答える。
- 制約が小さいので愚直ループでよい。
- 本番では「解は最大でもgcd(A, B)であることがわかるので、そこまで愚直ループ」という書き方をしたが、最悪計算量は改善されない
- ”大きいもの”ではなく”小さいもの”を答えると誤読した。
C:
- 1列に赤と青のブロックがランダムに並んでいる。赤と青が隣り合うときにそのブロックを取り除ける。最大でブロックはいくつ取り除けるか?(ただし、取り除いたあとの隙間は詰める)
- 下記を考えると、赤と青の個数を数えて、小さい方の回数だけブロックを取り除けることがわかる。
- 操作により1つのpairしか減らない
- 赤と青のブロックがある限り、どこかに赤と青が接する箇所が必ずある
D:
- 無向グラフが与えられる。そして辺が、辺番号の若い順に取り除かれる。このとき不便さを「どう辺を通っても辿り着けない節点のペアの数(数えるペアnode_i, node_jの点番号は i<j)」を定義する。辺が取り除かれるたびに不便さの値がどうなるか出力。
- 本番中に考えられたこと
- 操作を正順に考えて「連結成分から1つ辺を除いたときに残る連結成分」を考えると難しい。操作の逆順を考えると、「辺の追加により生まれる連結成分を管理する」という話になり考えやすくなる(分割統治法っぽくなるから?)
- 本番中の失敗
- 辺の追加により「連結成分XとYが連結成分Zになった」という状態を、コードに落とし込む必要性を見落としていた。「点XとYが連結成分Zになった」までしかコードに落としていなかった。辺追加前から連結成分X(or Y)の一部だった点について更新する必要性を見落としていた。
- なんかサイズつきのUnionFindでうまくできるという話がある。