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

AGC030b Tree Burning部分点を解説などを見て解いたログ

問題 https://atcoder.jp/contests/agc030/tasks/agc030_b

コード https://atcoder.jp/contests/agc030/submissions/3913984

考察ノート

f:id:hoyamag:20190103133238p:plain

アルメリアさんの記事 https://betrue12.hateblo.jp/entry/2018/12/30/215006 を見て、写経しました。

dpの更新順序がよくわからなかったので確認しています。

 

あまり関係ないですが、コンテスト本番での考察ノートは下図です。一瞬DPを考えていたので、「今度はちゃんとDP解けるようにしたいなぁ」という感想です。

f:id:hoyamag:20190103133808j:plain

f:id:hoyamag:20190103133825j:plain

f:id:hoyamag:20190103133841j:plain

f:id:hoyamag:20190103133855j:plain

 

AGC007A - Shik and Stoneを解いたログ

問題

https://atcoder.jp/contests/agc007/tasks/agc007_a

コード

https://atcoder.jp/contests/agc007/submissions/3891298

コード(解説見たあと)

https://atcoder.jp/contests/agc007/submissions/3891365

 

考察ノート

f:id:hoyamag:20181229195830p:plain

自分は判定のために探索を書きましたが、解説を見るとO(1)で判定出来たようです。

AGC008A Simple Calculatorを解いたログ

問題

https://atcoder.jp/contests/agc008/tasks/agc008_a

 

コード

https://atcoder.jp/contests/agc008/submissions/3891172

 

考察ノート

f:id:hoyamag:20181229192016p:plain


明確に無駄な操作(BB, ABA)を省くだけで最適な操作になったので、それを実装したら通りました。

「x >= 0 なら符号を反転させる」と書くところを「x>0なら〜」と書いたことで1 WAを生やしました。

 

AGC009A Multiple Arrayを解いたログ

問題

https://atcoder.jp/contests/agc009/tasks/agc009_a

 

コード

https://atcoder.jp/contests/agc009/submissions/3889556

 

解説見てから書いたコード(負の数の剰余を取る部分が消えた)

https://atcoder.jp/contests/agc009/submissions/3889667

 

考察ノート

f:id:hoyamag:20181229141618p:plain

  • 計算量の見積もりをせず、N<=1e5に対してO(N^2)を提出してしまった
  • 考察がそんなに良くなくて、負の数の剰余を取る必要が生じてしまった。