今月もやってきました 先月より省略気味です
- AGC039-C Division by Two with Something (800)
- AGC026-D Histogram Coloring (1100)
- AGC030-D Inversion Sum (1000)
- AGC037-D Sorting a Grid (1100)
- AGC028-C Min Cost Cycle (700)
- AGC025-D Choosing Points(800)
- AGC032-E Modulo Pairing(1200)
- AGC006-F Blackout(1700)
- AGC031-C Differ by 1Bit (800)
- AGC038-C LCMs (700)
- AGC012-C Tautonym Puzzle (1000)
- AGC012-D Coloful Balls (1000)
- AGC043-A Range Flip Find Route (400)
- AGC043-B 123 Triangle (700)
- AGC039-D Incenters (1000)
- まとめ
(ネタバレ防止用の空白)
AGC039-C Division by Two with Something (800)
要するに最も下のbitを反転させて一番上に移動させる操作なので、$X$と$X$の反転と$X$を順に繋げたものを考える。周期性と約数包除の気持ちになる
AGC026-D Histogram Coloring (1100)
盤面が長方形の時だけ考える。最上段がoxox...oxみたいな時はその下は2通りで、それ以外は1通りに決まる。(cf. IMO Shortlist 1996 24番)
上から下におろしていくことを考えると、今いるところがoxox...oxみたいな状況かそうでないかを持って木DPっぽく適切なマージをすればいいことがわかる。
AGC030-D Inversion Sum (1000)
反転数はバラして、$A_i < A_j$となる確率を求める。これはDPでできる 実は全ての$i,j$に対して同時に操作しても問題ないので、同じ配列上で同時に操作する
AGC037-D Sorting a Grid (1100)
ある行から行きたい行へ辺を貼ることを考える あとは二部マッチングに落とす
AGC028-C Min Cost Cycle (700)
小さい方から$N$個取りたい 全部Aや全部Bだったら可能 あと$A_i$と$B_i$を同時にとる$i$が存在すれば可能 これらを満たす取り方で和が最小なものは？ これは差分更新でいける
AGC025-D Choosing Points(800)
まず点集合を2個に分ける 二部グラフに帰着できるらしいので...(正三角形で全ての頂点が格子点にあるものが存在しないことを使って思いついた)
AGC032-E Modulo Pairing(1200)
二分探索3回 単調性には気を付けよう！
AGC006-F Blackout(1700)
行列→グラフの言い換え (ステップ1)
手で実験すると頂点をmod3で分類して0→1,1→2,2→0の辺が全てできることを確認する (ステップ2)
コーナーケースに気を付ける 辺を一本も貼れないときは辺は増えません (ステップ3)
信じる心！
AGC031-C Differ by 1Bit (800)
とりあえずこのツイートを見てください https://twitter.com/Rho4913/status/1239201260609212417
グレイコードを使う雰囲気になって、これをちょちょっと改変する 前半でずっと0だったbitは後半ずっと1のままになることとグレイコードを2回回せば00...00となることをうまく利用 この方針は実装が過激
Submission #10924320 - AtCoder Grand Contest 031
AGC038-C LCMs (700)
求めるものが$A_iA_j/GCD(A_i,A_j)$で。ここで$A_i$を固定して考えると$GCD(A_I,A_j)$の個数は$A_i$の約数の個数と同じなので約数包除の気持ちになる
$\sum_{d|A}f(1/d)=1/d$なる数列を作りたくなる これは調和級数で作れる(要証明) あとは約数ごとに分類して足して補正する
AGC012-C Tautonym Puzzle (1000)
基本思想は2冪 このままだと文字数がキツイので、各種類について2種類までしか使わないで構築してみる 1回目の登場と2回目の登場で分けて2つの同じ要素を線で結んでごにょごにょやるとなんか2冪が出てくる トポロジカルソートの要領で復元
AGC012-D Coloful Balls (1000)
自由にswapできるときは可能な組の間に辺を貼って連結性判定をする ここまで400点
辺を減らすのが本質 最終的な連結性が愚直に辺を貼ったときと同じであればよいので、無駄な辺を減らす
まず同色については、その色の中で最も軽いものへ向かって辺を貼るとしてよい
異色については、ある色の中で最も軽いボールに向かって貼ってよい またそれと別の色で、その中で最も軽いボールをもう一つ取り出してそれに向かっても貼る
残りの数え上げは簡単
AGC043-A Range Flip Find Route (400)
白から黒に入るときだけコストが発生する あとはダイクストラを貼る
AGC043-B 123 Triangle (700)
簡単な考察: 最初の1回で3は消える
こういうのは最初に簡単な部分問題を考えることから始まる もし2段目が全部0と1だったら？このときはパスカルの三角形みたいに寄与分を計算すればよい
そして偶奇が保たれるので最後の偶奇は判定できる(3は消えるので)
残りは0と2の区別 ここで2段目に1があると最下段は必ず0になる(2が残るのは0と2が隣接する場合だが、1があると0と2を破壊してしまう) それでも残った場合、最上段は1と3しか残ってない ここでさっきと同様に寄与分を計算すればOK
50分かかった、まあ適正くらいかな
AGC039-D Incenters (1000)
こういうびっくりするものも丁寧に考える癖をつけたい
最初に内心の座標をベクトルやらなんやらで求めに行くとN3かかって死ぬ(この方法で解いた方教えてください)
そこで、数えやすいものへと変形する。三角形の五心でまともに座標計算で戦えるのは重心くらいなので、重心へ帰着する意識を持つ。
ステップ1) △ABCのそれぞれの角の二等分線を外接円に当たるまで延長する。その交点をD,E,Fとすると、△ABCの内心は△DEFの内心と一致する。
証明: 円周角の定理とその逆を駆使して角度を写すと、角の二等分線とそれを横切る辺が直交することが分かる
ステップ2) 垂心と重心を対応付ける
適当に[垂心 重心]とかで検索すると、図形を扱ったサイトが出てくるので潜る。オイラー線というものがあるのでそれを利用する。OG:GH=1:2となることがわかった。
今回Oは(0,0)で固定なので、HがわかればGも同時にわかることになる。よって求めるべきはありえる三角形全てについてのGの座標である。
2点固定したとき、その2点の優弧/劣弧上の中点がそれぞれ何回足されるか求め、適当に足し合わせればOK
まとめ
15問 14000点
800点を全て潰した。月の後半はCodeforcesをやっており、ほとんど新しい問題を解けなかった。
