3完。普通の結果。得たものは無能感。
A - Make 10
まず10を作れる組み合わせを手で列挙する。意外と少ない。列挙して観察しいくつかの性質を知る。3は(唯一の)奇数なので偶数個使う必要がある(つまり2個使う)。4は2の上位互換なので2より先に使ってしまっていい。そこから先はよくわからなかった。時間が経つとだんだん考えがまとまってくるので、証明はできないけど適当に答えを書く。まず、3は2個くっつけて6にして使えるなら使う(残りは4を優先して使う)。4と2だけ残ったら、442を作れるだけ作り、4222を作れるだけ作り、22222を作れるだけ作る。まあAC。
(解説を見て)最適解を持ってきて、6も4もどこかで使われているけど6と4をくっつけたものがなければ使われている2本を解体して64にできる。そう考えるのかあ。そこそこ難しいうえに複雑で時間かかるな。きつい。
B - Cross-free Matching
aでソートして順に置いていって、最後に置いたやつよりbも大きくなるようにする。何も思いつかない。先にCやDを考えて、合間にBを見て何か思いつかないかにらむ感じでやってた。
DPができないと思っていたのは、左にある線分全部から遷移しないといけないため。でも(和ではなく最大値の)BITでbの位置に最大値を入れれば、aの順に追加していくことでabの2系統の変数を捌けるといういつものやつだ。この問題ではaが同じものもダメなので、位置iに対してa_jがiである辺jを使ったときの位置iまででの最大値を先に計算しておいて、その後その最大値でBITを更新する。位置i毎に区切って処理する。
C - Maximize GCD
この問題の設定でGCDが0になることはない。gcd(A)はmax(A)以下になる。全要素をmax(A)以上にできるなら簡単。そうでないとき、答えはgcd(A)以上max(A)未満の整数のどれか。logは2つ(調和級数と二分探索)付くかもしれないが全探索できる(特に定数倍が重くなる要素もないので大丈夫そう)。Aをソートしておく(二分探索する)。GCDの目標値を決めると、それに必要な最小操作回数がわかる。目標値の倍数になるまでインクリメントする必要があり、そうすれば達成できる。二分探索で区間を求め累積和を使い必要操作数を求めK以下なら出力(大きいほうから見る)。
わりと素直に解けた。総和sを累積和に変更するときintにしてしまい1WA。