A - First Player
ABCのAにしては難しい
- if文とfor文だけでも解けないことはない
まず$ 人_i $について(年齢,i)の順番でtupleに格納し
min関数で年齢が最小となる$ i $を求める
円卓の順番を崩さないために、双方向キューを利用した
- 一番左のデータを取り出して一番右に移せるデータ構造
- 双方向でなくてもよいが…
本音を言うと、ACできるか恐々としながら提出した
B - Subscribers
問題文が長い
桁数が1ずつ増えていることを確認してから実装に入った
こういう問題では$ N \in [0,1] $の時がコーナーケースになりがち
- 今回は違ったけど
C - Virus
感染した順番は覚えておく必要がない
- そのため、UnionFindをコピペした
- DFSやBFSでも解ける
距離判定をする場合、両辺を二乗すると実行時間が短くなる
あと<=と<、>=と>を間違えるのはやりがち
- 余談だが、sqrtを利用するとfloatの誤差でWAが出る問題が稀にある
-
- sqrtを利用しない形に式変形する必要がある
D - A Piece of Cake
異様に悩んでしまった
- 延長された20分の間に天啓が降ってきた
- なんとかコンテスト中にACできた
ケーキの縦分割と横分割を独立に考える
ケーキの切れ目ではなく、切れ目によって分配されるイチゴに注目する
- ケーキの左端（下端）を0個目の切れ目と考える
- それぞれのイチゴについてすぐ左（下）にある切れ目がどこにあるか覚えておく
- あとはPythonのCounterに突っ込む
-
- keyがtupleでもちゃんと数えてくれるので便利
- $ \big[ m=0 \leftrightarrow $ イチゴが1個以上あるピースが $ (A+1)(B+1)$ 個未満$\big]$に注意
E - Good Graph
慣れないタイプの問題だったが解けて気持ちよかった
- この問題で扱うのは無向グラフであるため
- $\big[$点$ x $と$ y $のパスが存在する$\leftrightarrow$連結である部分グラフ$S$が存在して、$x,y \in S\big]$
- が成り立つ
オレよく分かんねーけどよ、任意頂点間のパス存在性を変えずに分割した時、その分割は一意に定まるんじゃねーか？
- よわよわなので証明できません
とにかく
- UnionFindを使って頑張る
- 分割して、部分集合に付番することで
- 「存在したら良さが損なわれるパス」
- 「クエリによって生やされる辺」
-
- 入力で与えられるやつです
- これらが格段に扱いやすくなる
「クエリ〜」が「存在〜」を生むか判定することで解ける
- 具体的には、tupleをkeyにしたdictを使うとか
総括
推定パフォーマンス的には悪くなかったが、unratedとなってしまった
- 無料でコンテストに参加させてもらえる運営さんには感謝しています
余談
考察を紙に残せば「天啓」が来るのを早めることができる
- ……のだろうか？
-
- というのも、Twitterに上がっていた考察用紙がそれなりに埋まっていたので