Atcoder: みんなのプロコン2019
A. Anti-Adjacency
選ぶ数の最大値をなるべく小さくしたいことから,1から1つ飛ばしで数を選んでいくのが最適.このとき個目の数は番目の正奇数,すなわちであるから,これととの大小を比較する. 解答例
B. Path
問題文の処理をそのまま実装するDFSを書いた.道に番号を振ってそれぞれの道を通ったかを配列で記録しておけば,3回の移動で「すべての道を」「1回ずつ」通ったかは迷いなく判断可能. 解答例
editorialの解法は漏れを作りそうなため,個人的にはこちらの解法のほうが好ましく思う.
C. When I hit my pocket...
こういう操作の特性を考える系の問題はあまり得意ではない.実験をした. 解答例
本文中にある操作を上からP,Q,Rとする.最終的に円を持っていても利益がないので操作Q,Rの数は同数.すると例えば操作列はPPPQRPPQQRRP...
のようになるが,P...PQR...QR
と整列して構わない.このときP
の数を,QR
の数をとすると,.
このときのスコアは .
の係数が負または0,すなわちの場合はが少ないほうがよく,としてスコアは.そうでない場合はは多いほうが良い.ただし操作Qを行う条件として,変形してが必要であり,としてスコアを算出すればよい.ここでにも注意:が負のときはとする.
最初はについて整理しようとして散々な目に遭った.を用いると .のときはの係数が負なので操作Q,Rを増やすべきだが,操作Qを行う条件として.素直にとしたいが,は整数なのでの偶奇で場合分け:偶数のときはそのまま.奇数のときは としてしまうと1操作余るため,それを操作Pに回してとする.というように,について整理するほうが面倒.
ところでeditorialでは最初からかを見ている.これは操作QR(スコア)と操作PP(スコア)の比較と見れば納得できる:であれば後者を選んだほうがよく,であれば前者を選んだほうが得をする.
D. Ears
散歩が1回だけという条件を読み落としていたが,そうでなくても解けなかったと思う.
解説(editorialなど)
まず散歩により耳がどうなるかを考えると,これは[]*-[偶数]*-[奇数]*[1]-[偶数]*-[]*というつの区間が並んだ形になる.逆にこの条件下であれば任意数の石を入れることができる[2].
この結果の導出についてはこちらの記事が大変参考になった:始端終端という一番単純な形から考えてみる.この2点を固定すると,散歩のバリエーションとしてあり得るのは途中箇所に往復を加えたものだけであるから増分は必ず偶数となり,ここから導かれる[3]. 以下では当該記事も含めた2記事を参考文献としている(後掲する).
本問で行う操作は次の2つ:
- 散歩によって位置の石の個数をとする
- 各に好きな回数だけをし,とする
各位置が散歩のときどの区間だったのかを考える.先に述べた区間を順にとする. 前の数字が区間であるとすると区間の順序から位置は以降の種類のどれかになるはずであり,逆にどれになっても構わない[4].
位置が当て嵌まる区間の種類を仮定すると,の値から必要な操作の回数もわかる(先に述べたようにが好きなように作れるため):
- が: から回操作を行ってにしたとするのが最小
- が: は2以上の偶数であることから,
- のとき操作は回(としてする)
- 以上の偶数のとき回(そのまま)
- 奇数のとき回(とすると,操作ですることでが作れる)
- が: は奇数であるから,
- が奇数であれば操作は回
- 偶数であれば回(とする)
- が: と同様
- が: と同様
肝心の区間を決めたい.以前に「区間の境界を1つ決めると残りの境界も決まる」というタイプの問題を見たことがあるが今回はたぶんそうはならない.DPができる:「が区間であるときの操作回数の最小値」とすると,先に説明したように区間の遷移を書ける.すなわち区間に対して先の操作回数を,またはそれ以前の区間の種類をとおくと:
となる.配るDPとして解釈したほうが先の記述に合っているが,配るDPを式で書くときの慣例がよくわからず. 計算量はが5通りなので.考察さえ済めばかなり綺麗に書ける. 解答例
参考
- https://betrue12.hateblo.jp/entry/2019/02/10/014031
- http://koba-e964.hatenablog.com/entry/2019/02/10/003030