ABC412 C～F問題 思考過程

概要

ABC412で問題文を一目読んだ時、どういう思考を経て正解に至ったのかを文章化してみました。ABCで良い成績を取りたい人の参考になればと思います。

C - Giant Domino

atcoder.jp

考えたこと

  • 変数 x を x=A_1 から x=A_N に変化させるみたいなタイプの問題で、貪欲法(変化させられる値のうち最大の物を選ぶ)でよい。
  • 値をソートしてlower_boundで検索すれば良さそう。

実装

  • c=A_1, g=A_N としてソート、whileループで cを 2c 以下の最大の値で更新。更新できなかったら-1。終了条件は 2 c<g であること。
  • 大きいドミノを倒すためにドミノを差し込むイメージで基本的に A_i が増加していくように並べるが、 A_1 > A_N のケースもあるので壊れないか一応確認し、提出。

コメント

解説は操作回数が \mathrm{O}(\log A) 回であることを使っていたが、C問題でそれが出るのは少し珍しい気がする。というよりは、lower_boundによる検索を差し置いて操作回数が \mathrm{O}(\log A) 回で～という解説に違和感があるというべきか。

D - Make 2-Regular Graph

atcoder.jp

考えたこと

  • それっぽい(効率的な)解法がすぐ出てこない& N が小さいので、どうせD問題でありがちな全探索だけの問題だろう。

実装

  • すべての次数が2のグラフはいくつかのサイクルになる。DFSでサイクルを順に生成すれば列挙できるか。
  • なんか大変なので方針転換。 _{_N C_2} C_N 通りの辺の選び方を全部調べる。( _{30} C_{10} が間に合うというのを過去に何回か見た記憶があるので _{28} C_{8} も大丈夫と判断)
  • 長さ {_N C_2} の01列であって0が {_N C_2}-N 個、1が N 個のものをnext_permutationで回して1に対応する辺が存在するものとして判定・求値する。

コメント

長さ2のサイクルが出来てはいけないのを見落としていたので、方針転換によって偶然ペナルティを免れたことになる。

E - LCM Sequence

atcoder.jp

考えたこと

  • ( A_i は単調非減少なので) A_{i-1} \neq A_{i} となる i を考えればよくて、これは素数 p, 正整数 m を用いて i=p^m と表せるのが条件。
  • i=p の場合があるのと、 R-L \leq 10^7 という制約があるあたり区間篩をさせられると思って間違いなさそう。 M=R-L として区間篩って M \log M だっけ？ M \log\log M だっけ？になったが、TL見たら4秒だったのでどちらにせよ間に合うでしょうと判断。
  • i=p^m(m \geq 2) は、 p \leq 10^7 なので全部調べてしまって良い。

実装

  • L=R, すなわち L+1 > R の場合に変なことが起きたら嫌なのでとりあえず L=R ならば1を出力して終了させる。
  • 10^7 以下の素数を列挙。
  • 区間篩で素数をカウント。
  • p^m(m \geq 2) の列挙をする。 p^m \leq R の間 p^{m+1}を計算し続けたが、オーバーフローするので128bit整数を使用。

コメント

前に区間篩を見たのはABC-GだったのでEで出てきて少しびっくり。

F - Socks 4

atcoder.jp

考えたこと

  • この辺によく置かれる、自己ループを処理しないといけない期待値DPだろう。
  • A_i \leq 3000 なのでこれで2乗っぽい。実際、 \mathrm{dp}[i] を今持ってる靴下が全部で i 枚あるときの期待値とするとうまく考えられる。

実装

  • 経験則的に、 i の降順に処理することにする。
  • 全部で i 枚存在する靴下がないのに \mathrm{dp}[i] を扱うと壊れるかもしれないので丁寧に弾く。( \mathrm{dp}[i] を決めるときや遷移のときに存在するか調べて存在しない場合はcontinue)
  • 操作の結果を遷移のタイプに応じて3つに分類。
  1. より枚数の多い靴下を選んで、より大きな値のキーに遷移
  2. 今持ってる靴下を選んで、終了
  3. 今持ってる靴下以外で、今持ってる靴下と枚数が同じかより少ない靴下を選んでキーの変化なし(自己ループ)
  • 確率 p で成功する試行を成功するまで繰り返す場合、試行回数の期待値は？という問題の答えは \frac{1}{p} となることが有名。上記3を失敗、それ以外を成功と見なせば自己ループは解決する。
  • 1の遷移を考える。念のため \mathrm{O}(A^2 \log A) にならないようにしたくなり、少し考えると i ごとに遷移の係数の分母が全部同じだったのでその逆元だけ前計算してやった。

コメント

  A_i \leq 3000 というのを見た瞬間に A_i の値をキーとするDPだろうという思考になって、 \mathrm{O} (N) が想定という気がしなかった。

まとめ

頭を使う必要が無いと早く解けるということがよく分かりますね。

AtCoderで頂いた賞金・賞品

ABCでの上位賞金廃止が話題になったのですが, そういえば自分は今までどれだけ貰ったのだろうという気持ちになったので.

メールとか頑張って遡りましたが漏れがありそうです(対応の取れないアマギフ追加履歴がある).

日付 コンテスト名 順位 賞金・賞品
2020/10/10 HHKB プログラミングコンテスト 2020 総合20位 HHKB
2020/11/07 HACK TO THE FUTURE 2021 予選 抽選 3,000円
2021/09/18 サイシードプログラミングコンテスト2021（AtCoder Beginner Contest 219） 総合6位・学生3位 20,000円
2021/11/13 キーエンス プログラミング コンテスト2021-Nov. 総合5位 10,000円
2021/11/20 トヨタシステムズプログラミングコンテスト2021(AtCoder Beginner Contest 228) 総合4位・学生2位 120,000円
2023/11/19 ALGO ARTIS プログラミングコンテスト2023 秋 （AtCoder Regular Contest 168） 抽選 5,000円

ちなみに, 2022年の3月頃から2024年の1月頃まではABC-Wをやっていました. 会う人会う人に橙～赤になると賞金だけでかなり貰えるんじゃないかと聞かれがちなのですが, (上記期間を考慮しても)全く以てそんなことはありません.

二項定理の問題ツイートを組合せ論的解釈と多項式・FPSで解く

このツイートを目にしたので, 解いてみました.

9問目は式が違うようなのでこれから解こうという方はお気を付けください.

最近競プロerの間でFPSを勉強しようという流れがあるようなのでFPSを用いた解法も載せようと思ったのですが, 多項式の範疇に収まるのがほとんどです. また, 最後にそれっぽい競プロの問題を何問か紹介します.

続きを読む