AGC とか埋めまとめ
今年のはじめ頃に AtCoder 埋めをしたので、感想を書き連ねます。問題を選ぶ基準は、すでに埋めた全員 rated のコンテストの 1300 以上とあと若干の気になったものたちです。
(ネタばれ防止用空白)
(空白ここまで)
AGC 001 E:
当時は非典型だったけど一回出ちゃえば解法忘れないからもう典型なんじゃないかな、本番はなんか解けた
AGC 001 F:
N*N グリッド作って〇書いていろいろ線引いてたら解けた覚えがあるけど、けっこう時間かかったし難しい
最初やった時は平衡二分探索木が必要になって詰んでた
AGC 002 E:
普通に勝ち負け書いてたらできるけど細かい実装に若干ハマった覚え まあ簡単だと思う
AGC 002 F:
典型数え上げ 生成されるものを数えるときは生成されるものを認識する簡単なアルゴリズムを作ってその動作を数えるアレ
AGC 003 E:
writer 手持無沙汰になって excel のセルのコピー機能を無為にガシャガシャやってたらできた問題
AGC 003 F:
writer 最初全体が連結になるか判定だったけどお布団にいたら数えられることに気づいた
AGC 004 E:
言われればまあそうっていう感じだけど微妙に見えにくい あとグリッドをガシャガシャ動かす羽目になるので実装頭壊れる
AGC 004 F:
2200 だけど人間的に解ける
まず、こういうのは葉から操作回数を決めていくんだけど木の場合は greedy に順に操作回数が決まっていく
なもりの場合は、サイクルの各頂点にくっついてる木を見ると「何回この色で塗ってください」みたいなのが定まってることになって、サイクルに対する問題に帰着されて、これは解ける
AGC 005 E:
これ相当難しいと思うんだけどみんな簡単って言う……
人を片方消すのはまあよくて、到達した瞬間逃げ放題の頂点の条件もわかるんだけどその先がきついと思う
悩み続けたらなんかぬるっとできたけど再現不可能
AGC 005 F:
これは素直 FFT できるように項を分けるのに慣れてますかというだけ
AGC 006 E:
つくれるもの全体は部分群なので位数を実験で数えるのは典型 実験すると全体の 1/4 が作れるのでパリティ条件を 2 個探せばよく、ありがちなものを試すと出る
AGC 006 F:
AA->B, BB->A は mod 3 で見るのの初出かな、なんでこの特定の遷移が何度も出されてるのかわからないけど
当時はかなりすきだったけど今となっては典型
AGC 007 C:
1000 点とは 適切にやると非本質っぽい条件が消えていってシンプルな問題にはなるけどそれもまた難しかった覚えがある
AGC 007 E:
DP っぽいことする以外にやりようがなくてそうするとまあこれしかないよねという感じ log がたくさんついて若干不安になる
AGC 007 F:
思った通りにお絵描きするとできる
AGC 008 E:
やることはわかるんだけどやるのが大変すぎる……
AGC たまにこういう見た目が面白そうなだけなものが出てくる、たぶんりんごさんの問題評価の癖
AGC 008 F:
やることはわかるがたるのが大変その 2
求めたいものの式を無心で変形すると求められるものの足し引きで書けるがちゃんと求めるのが大変
Petr がこの回 tedious って言ってた
AGC 009 D:
writer なんか考えてたらできて面白いと思ったけど既出らしくかなしい
りんごさんはこれしかないでしょみたいなノリで解いてたので難易度評価バグった
AGC 009 E:
writer これお気に入り
あまり解けると思わずに適当に考えてたらなんか解けてテンション上げてた
AGC 010 E:
考えることが複雑で頭壊れてくる 実装も特殊な重さだし王道難問という感じ
まあ落ち着けばできるんだけど落ち着くのが大変
AGC 010 F:
雰囲気でだいたい戦略わかるのでやると通る 配点ミスだと思うけどこういうふわっとしたの過剰に難しく評価されがちな傾向はあると思う
AGC 011 E:
これは見たことないタイプで難しい
9 倍するの見えてしまえばまあできるとは思うのでここだけ覚えておこうという感じ
AGC 011 F:
いろいろと複雑で頭壊れるけど特に特殊なところはないので落ち着けばできる
時間内に間に合うかというとそれは別問題
AGC 012 F:
条件エスパー系 妥当にやってもできない数え上げは難しい
それっぽい条件を思いついたら証明しにいくのが良い気がする
AGC 013 E:
解説は頭っぽいことしてるけど式書いて無心でいじればできる
式を組合せ的に解釈して思考する系で combination 系でないやつは大抵式のままいじってもできる
AGC 013 F:
正答派難問 最初 O(NQ) すら全然わからなくてビビるやつ
ステップが 3 つあって、区間系の条件言い換えの典型っぽさのある最初の 2 つをやると O(NQ) にはなる
最後は全クエリ並列に処理しようとすると、各クエリが欲しがる条件がまとまってくるのでオーダーが落ちる、これはそんなに見ないタイプ
AGC 014 E:
パスとか言ってるけどグラフ理論の教科書の定義の部分っぽい感じで要するに連結性の話をしている
やることはわかり、なぜかマージテクできないと思い込んでハマってたけど両方の木を一気に考えればよい
AGC 014 F:
増加列がどこに行くかみたいなのをお絵描きして三日悩んだらできたけどこの不変量はなに……
他の AGC の問題と比べても段違いに難しいと思う 何かにこのテク使えないかな
AGC 015 F:
writer 解説に書いた定理っぽいのを見つけたので出した
適切に実験すればできるんじゃないですかね
AGC 016 E:
いろいろ手で実験したりしてるとまあ条件は見えるのでできる 王道
AGC 016 F:
指数系苦手…… grundy 数そのものを持たなくていいのかなり新鮮だった
AGC 017 C:
1000 点とは 90 度回さないと大変な目にあいそうというのはそうなんだけどそこから先もきつい……
AGC 017 F:
こういうの見ると上からやりたくなってしまうのは宿命なんだろうか 横に見ないと無理ということを結論するのにけっこうハマった
あとは i->j のパスに中間状態を付け加えて遷移まとめてやるやつをどう適用するかというだけ ゼータ変換みたいな感じ
AGC 018 E:
累積和っぽい変形は combination 慣れでできて、16 個問題を解けばいいことはわかる
経路数の話だと思えば自然な境界足し引きでできる
AGC 018 F:
適当なものを作って補正することにするとけっこうきれいにフローになるけど非想定だったっぽい(10 万の重みなし dinic なのでオーダー的にも大丈夫)
AGC 019 E:
落ち着いていろいろ分類して DP の式を書くと状態がまとまることがわかる
解説変なことしてるけどまあ 2 乗しか書かないと思う
AGC 019 F:
適当に言い換えると combination 系の境界足し引きをするだけになるけどなんか添え字にハマった 簡単だとは思う
AGC 020 E:
どうせこれしかできないし状態数少ないやろみたいな DP を書いて送り付けるとなんか通る
tourist だとりんごさんの良問判定ガバガバになるので
AGC 020 F:
積分したくないという一心でできそうな方針を探すと第一感がこれ まあやけに許容誤差が小さいとかいろいろ怪しいポイントはあるよね
期待値とると消えるので特定条件下での平均を実現しそうなケースだけやれば OK というの思考過程での実験とかではよく使うのでそれが問題になっただけと思えばまあ
AGC 021 F:
writer DP 自体そんなに難しいとは思わないけどりんごさんがハマったのでここに置かれた
AGC 022 D:
落ち着いてやることをやればできるが、場合分け多いしコンテスト中にできるかといわれると微妙
場合分けだけど場合のそれぞれが結構きれいなのでやる気になる
AGC 022 E:
普通の数え上げ 判定問題のアルゴリズムの動作を数えるやつ 典型
AGC 022 F:
落ち着いて適切な方向から見ると判定問題のアルゴリズムが生える系 適当にやりすぎてオーダー増えたので埋め込んだ
APC 001 G:
場合分けが大変 コンテスト中はひたすらこれと格闘していた
やればできるとは思うけど合わせるのはかなり大変
APC 001 H:
列の場合を適切な方法で解けるとそれを拡張できる
HL 分解ってデータ構造乗せる以外にもたまにこういうきれいな使い方ができるし解析に使えることも多いので心の片隅に置いておくとよい
各ステップの最初の処理の部分の操作回数最初見積もってなくて一瞬ひやっとしたけど大丈夫だった
APC 001 I:
下手な方針を選ぶと実装が手に負えなくなる
座標圧縮は良くて、障害物に影響されてできる最短路は圧縮した座標の隣くらいしか通らないことがわかるので、座標圧縮後に重み 1 で最短路してから補正すれば十分なことがわかる
これでもとても軽いということはないが、見通しは良い
APC 001 J:
非自明なケースを作りに行くと作れて絶望的になるが、実は素直に積んだ後に三方向から長方形領域をずらしたような形を作ると残り全部決まることがわかるので、これを数える
いろいろな値が出てくるが、結局全部適切に計算すると 4 乗で済むことがわかるので、落ち着いてそれぞれ数えてやる
CODE FESTIVAL FINAL 2017 H:
本番バグらせて賞金がだいぶ減った
問題文の条件を言い換えるとそれっぽくなるのでそれを使って DP する
CODE FESTIVAL FINAL 2017 I:
条件エスパー系 実験すると必要条件が十分条件なことがわかる
あとはゼータ変換っぽくやるとできる
CODE FESTIVAL FINAL 2017 J:
実家重心分解で通るので……
CODE FESTIVAL 2017 Qual A E:
writer 場合分けして combination 頑張るとできると思う
手数と気を付けることは多めなのでそんなに解かれなかった
CODE FESTIVAL 2017 Qual A F:
お気持ちをそのまま DP の式に落とすと通る
CODE FESTIVAL 2017 Qual B E:
素直に判定条件を書いて素直に式をいじるとできる
CODE FESTIVAL 2017 Qual B F:
結局証明できてないね…… 綺麗だとは思うのだけど
文字列系のこういう証明闇になりがち
CODE FESTIVAL 2017 Qual C E:
発想も結構難しいし気を遣う、実装はもっと気を遣う
見た目に反して面白いけど、コンテスト中に通せるものではないね
CODE FESTIVAL 2017 Qual C F:
これも判定条件を書くと多項式にはなるが、3 乗まで落とすパートの累積和を変なものを取らないといけなくなって大変な目にあった
結局更新順序を異常にして通したけど最初の方針が悪かったのかな
MUJIN 2017 B:
素直にできる操作をするとそれ以外にやりようがないことも同時にわかるので適当に場合分けしてちょっとやる こういうお気持ち系はりんごさんの難易度評価が上にぶれがち
MUJIN 2017 C:
かなり悩んだ 正しい方針以外はすべてがダメダメなので手が動かないタイプ
正しい方針も見たことないタイプで、難しいと思う
MUJIN 2017 D:
条件エスパー系 比較的簡単に証明できる
メモ化で書くと楽 奇数の場合も実はきれいに処理できて良い
CODE FESTIVAL GRAND FINAL E:
この考察パートはどこをとっても見たことがない 1000 点とは……
確かに見るべきものを絞る段階でサイクル消せるけど有向でそんなことしようと思うのかなぁ
CODE FESTIVAL GRAND FINAL H:
rank しか関係ないことは対称性からわかる 残りもひたすら対称性って言い続けながら線形空間の様子をイメージし続けるとできる
やることは多いので時間はかかる
CODE FESTIVAL GRAND FINAL I:
こういう緩い構成は適当に作って座標圧縮が筋なのかな こういうのも典型化したいね
CODE FESTIVAL GRAND FINAL J:
構造を適切に見ると普通に数えられる やればできる系
CODE FESTIVAL FINAL 2016 H:
DP は簡単で、その様子を適切に眺めるとまあできるんだけど難しい……
怪しい制約を生かそうという思考をしてもそんなに簡単になるかというと……
CODE FESTIVAL FINAL 2016 I:
部分群系は実験して状態数をカウント いろいろ実験すると見えるのでそれを書く
CODE FESTIVAL FINAL 2016 J:
割り当てた後にサイクルに沿って回す操作をすれば割当先までの距離の和みたいなものが減少することがわかるので、必ずできることはわかる
上から突っ込むものの割当先までの距離の集合だけ考えても、各距離はサイクルに沿って回す操作で増加しないので上からの距離の列が辞書順最小になるように埋めていけばよい
辞書順最小なので順次決めていけて、毎回フローを流すとできるが遅い
グラフは単純な形をしているので maxflow-mincut で言い換えてやると高速に判定ができる形になり、できる
埋めてないのがたまってきてるのでまた埋めないと……
