これから毎月解いた問題をダイジェスト形式でまとめます。たまに解説を書くかもしれません。
- AGC040-C Neither AB nor BA (800)
- AGC014-D Black and White Tree (900)
- AGC001-D Arrays and Palindrome (1000)
- AGC003-E Sequential operations on Sequence (1400)
- AGC021-D Reversed LCS (900)
- AGC013-D Piling Up (900)
- AGC017-D Game on Tree (1100)
- AGC017-C Snuke and Spells (1000)
- AGC007-D Shik and Game (1200)
- AGC018-C Coins (800)
- AGC024-D Isomorphism Freak (1100)
- AGC003-F Fraction of Fractal (1700)
- AGC006-E Rotate 3x3(1500)
- AGC005-D ~K Perm Counting(900)
- AGC013-D Ants on a Circle(700)
- まとめ
(ネタバレ防止用の空白)
AGC040-C Neither AB nor BA (800)
解説 : AGC040-C Neither AB nor BA (800) 解説 - ZenReKkyo Industry II
提出 : atcoder.jp
AGC014-D Black and White Tree (900)
問題 :
解説 : 長さ4とか5のパスで実験するとパス長が偶数の時だけ後手が勝てる。いろいろいじると実は完全マッチングが作れるときに後手が勝つ(直感的にもそう)
あとはDinicを貼るだけ
提出 :
AGC001-D Arrays and Palindrome (1000)
問題 :
解説 : 奇数がいっぱいあると結ぶのに失敗してしまう。[0,K]と[0,K+1]が両方回文だったら[0,K+1]は全て同じ文字であることも利用すると、奇数を両端に寄せれば構築可能であることが分かる。つまり奇数が3個以上なら破滅。
提出 :
AGC003-E Sequential operations on Sequence (1400)
問題 :
E - Sequential operations on Sequence
解説 : $q_i$が減少するような部分はとっても意味がないので無駄な部分を削るまでは自明
あとは割り算の要領で数列のリピート部分を分解していけばいい setとmapを使うとできる
提出 :
AGC021-D Reversed LCS (900)
問題 :
解説 : 左からと右からで同じ文字を取っていくといえば...?
回文に気づけばあとは一瞬
提出 :
AGC013-D Piling Up (900)
問題 :
解説 : 記事を参照
AGC013-D Piling Up (900) 解説 - ZenReKkyo Industry II
提出 :
Submission #10079893 - AtCoder Grand Contest 013
AGC017-D Game on Tree (1100)
問題 :
解説 : Grundyに注目する。その状態で根の上に頂点を新設してそれを根としたときのGrundyはどうなるかさえ発見できれば 実はこの新しいGrundyは元のGrundy+1
提出 :
AGC017-C Snuke and Spells (1000)
問題 :
解説 : 記事を参照
AGC017-C Snuke and Spells (1000) 解説 - ZenReKkyo Industry II
提出 :
AGC007-D Shik and Game (1200)
問題 : D - Shik and Game
解説 : 0からEまでは絶対一回ずつ通る。最適な移動を考えるとあるところまで行ってきてまだ戻ってくる... を繰り返し、これは共通項を適切に削除すると区間を区間に分ける問題となる。
部分点のDPさえかければあとはこれをセグ木に載せるだけである。$dp[i]-x[i]$みたいな式が出てくるときは元のセグ木に加えて$dp[i]-x[i]$を載せたセグ木も持っておく。教育的なインラインDPの問題。
提出 :
AGC018-C Coins (800)
問題 : C - Coins
解説 : コインが2種類だったら？そのときは簡単で$B_i-A_i$でソートして貪欲でよい
3種類の時、$B_i-A_i$でソートしておけばある点を境に銀貨をくれる人と金貨をくれる人が入れ替わる。(入れ替えたら損することがわかる)
その点で区間を分割すると、$X$人から金貨をもらい余った人から銅貨をもらうことになる。これはpriority_queueを用いることで解くことができる。(類題 : 3N Numbers)
提出 :
AGC024-D Isomorphism Freak (1100)
解説AC
問題 :
解説 :
ふわっと言い換えればこれは木を点対称にする操作である。
直径が奇数なら簡単で、中心となる辺が一意に定まるので中心からの距離が同じ頂点ごとに分類して次数の最大値を取り続ければよい。
偶数のときはいくつか場合分けがある。中心となる頂点をそのまま使う場合と、周囲の辺を中心として使う場合がある。前者は奇数のときと同じ方針でよく、後者は中心として使う辺を中心から出ている辺の中を全探索することで解ける。下線部に気づかずバグらせ続け、解説を見た。
提出 :
AGC003-F Fraction of Fractal (1700)
解説 : 全部連結になる場合と全部離れてしまう場合は自明
次の連結成分の個数は、基本は(元の画像の黒マスの個数)倍になるが一部くっついてしまう。そのような場所も1回の操作で指数関数的に増えるので...
適切な漸化式さえ立てば高校数学でも解けるし行列累乗でもたぶん解ける(提出は前者)
提出 :
AGC006-E Rotate 3x3(1500)
問題 :
列とその位置のパリティは保たれるので明らかにダメなケースは除外できる。
以降は以下のような問題設定を考える。
- $N$枚の裏表のあるカードが一列に並んでいて、最初は全ての面が表で左から$1~N$が書かれている。
- 1回の操作で連続する3枚を裏返し、左と右のカードの位置を交換する。
回転の中央に奇数番目を用いたときは偶数番目の表裏が1だけずれて、奇数番目の表裏の偶奇は不変 逆も然り
ここで連続する3枚が"2枚"だったら？実はこれは移動距離の偶奇と表裏の偶奇が等しく対応する。
この問題の場合でも移動距離とパリティに注目すれば条件が絞り込めて、実はそれは同値
提出 :
AGC005-D ~K Perm Counting(900)
問題 : D - ~K Perm Counting
解説 : 見るからに包除原理が使える 各要素に関して禁止されている数の個数は0,1,2のいずれか
1個の場合は有名問題 0個の場合もまあ自明 では2個のときどうすればいいか？
ある数Kが嫌いな要素は高々2か所で、そのような点はある点から連鎖的に決まっている。その数を包除の際に数えるか数えないかでその次の要素を置ける場所の数が変わってしまうので、それを入れてDPをする。
提出 : atcoder.jp
AGC013-D Ants on a Circle(700)
問題 :
解説 : 本家蟻みたいにアリはすれ違うものとして考えてよい。各アリの番号を求める必要があるので、すれちがったときに各アリのindexを交換するものとして考える。
考察を進めると、いかなる時でも蟻0から反時計回りに1,2,...N-1と並んでいることが分かる。また、先ほどのように仮定することで全ての蟻の最終的な位置が(indexはわからないにせよ)求められる。
ここで蟻0が向かってくる蟻と衝突したとき、そのindexは向きによって±1される。これで最終的な蟻0のindexが算出でき、そこから全ての蟻のindexもまた求まる。
提出 :
まとめ
累計15,900pts 15問 赤dif以上を7問埋めた。
3月の目標はひとまず10,000点分AGCを解くことです
