トップ > ABC120参加したメモ

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でうまくできるという話がある。