ABC-D 105-116
相変わらず考察だけで実装はしてないが、一応これで新基準以降のABC-Dが終わった。
ストリークとかAtCoder problemsの緑染めとか考えなければ、次はscoresで400-500を埋めていくのが良さそう。
105
累積和をmod Mで記録しておく。map。
l-1までの累積和のmodと等しい累積和のmodを持つrを数える。
iより左側で累積和がnになる位置の数、がそれぞれわかっていればいい。
いちいち記録するのは不可能だが、結局必要なのはnの時と、今見ているlについてのもののみ。先にNについて求めておいた上で、lを進めながら同じmapを更新していけばいい。
106
X までの区間に完全に含まれるものの数、を求めておいて引き算。
ここからさらにXを含む電車の数を除けばいい。これは区間の重複度なのでimos法でいける。
解説のように範囲を扱う問題を2次元で考えるやり方には慣れておいた方がいいかも。
107
むっず。
わからん。
それぞれの数がmedianの配列に登場する回数が分かれば良いが、N^2すらとおらない。
https://img.atcoder.jp/arc101/editorial.pdf
無理すぎる。ARC&ABC全体で正解者26人て。
medianの値を主軸に、二分探索で探していく。
この考え方は頻出っぽい。
https://betrue12.hateblo.jp/entry/2018/08/26/122740
“前項で書いたとおり、「中央値はX以下である」ことと、「X以上の要素が半数以上存在する」ことは同値です。そして、「整数Xが与えられたとき、集合の要素の中にX以上の要素は半数以上存在するか？」というYes/No問題は、直接中央値を求める問題よりもずっと考えやすくなります。というのも、各要素の具体的な値は全部無視して、X以上かどうか、だけで2値化して考えれば良いからです。”
108
Nが20以下でMが60以下なので、xからx+1に3本ずつ引ける。
全ての数字を重複なく、ということなので、hoge進数でやれそう。
辺の重みはゼロでも構わないので、
頂点xからx+1への辺の重みを、0, 3^(x-1), 2*3^(x-1)として3進数でやればいい。
面倒なのは、ちょうどL個という部分の処理。
30を考えると、3*3は必要だが2*3^3を入れるとオーバー
3^3も、それ以下をいれすぎるとオーバー
3^11>10^6なので、頂点数にはある程度余裕がある。
3^n-1までは安全に作れるので、3^nからL-1は別ルートで作るi。
頂点1から重み3^nの辺を伸ばし、すでに使った頂点以外を使って作る。
これを繰り返す。
解説は2進数ベースでやってる感じで、実装はあちらの方が楽そう。
2^n-1を超えた部分の処理が上手い。改めて制約を考えると二進数の方が自然だった。
109
うねうね動きながら処理していけば、全て偶数 or ひとつだけ奇数まで持っていけるはず。
どちらになるかはともかくとして、操作としては変わらない。
i, j を見て偶数ならそのまま、奇数ならi+1, jへ一つ移動させ、次はi+1, jを見るというのを繰り返す。
110
Mを素因数分解してから、1でない要素がいくつあるかで分けて数えていく。
k個の場合、nCk * (Mの1以外の約数のk個の箱への振り分け方)
素因数の重複がややこしい。
各素因数について、区別のできないボールとして分けていく。
kを処理する時にどれかの箱がカラにならないように注意する必要がある。
単純に分配した後でk*(k-1の場合)+kC2*(k-2の場合)... を除けばいい。
というかもっと単純に、各素数について独立に、N個に分配する場合の数を求めればいい。
カラになった箱には1が入っていると考えればいい。
Π binom(n+素数の登場回数-1, 素数の登場回数)
111
まず、十分にアーム全体が長ければ近づけるだけ近づけた後で帳尻を合わせればいい。
腕が重なることは許されているので、この場合0, 0からの距離の偶奇が全ての点で等しければ到達可能。部分点はこれで良さそう。
m<=40という制約をここに取り入れていく。
直感的に、マンハッタン距離の最大公約数とかが関係しそうではある。
最大公約数を作ることができるなら、それを何回か繰り返せば到達できる。
ただし、3, 12のような組み合わせでは3が作れなくなる。
最大公約数で割ったときの偶奇が等しければ、いって戻ってを適正回数やれば帳尻が合う。
マンハッタン距離で考えていたが、x, yそれぞれでやらないとダメか。
中途半端なところで曲げられないので。
結局、x, yそれぞれの方向の各店の距離の最大公約数を求め、それで割った偶奇をチェックする。全ての点で等しく、また、割った値のx, y方向での合計が40以下であれば作れる。
解説ぜんぜん違うやんけ。
https://img.atcoder.jp/arc103/editorial.pdf
マンハッタン距離は回転させるとx, y独立にあつかえるので2進数で作る。
負まで許せば、全ての腕を使いつつ任意の値を作れるということに頭が及んでなかった。
マンハッタン距離のこの性質は頻出っぽい。
冷静に見ると、上でやった考察だと最大公約数が小さい時に腕が足りない。
112
median of mediansのように、値について二分探索っぽい。
ある値xを最大公約数とするような分割が存在するか判定。
MがN*x以上でM%x=0ならok
用は、Mの約数でM/N 以下で最大のもの。
113
最低限必要な本数はK-1本。
『i th rowで j th colに居る為の、i-1 th rowまでのアミダパターンの数』でdp。
114
約数が75個ということは、その数は約数が75, 3*25, 5*15, 3*5*5個。
1,2,...,Nをそれぞれ素因数分解して約数の個数を数える。
115
レベルNバーガーの厚みは、x_{i+1} = 2x_i +3の解。
レベルiのパティの枚数も簡単に求まる。
与えられたxがレベルNのどこまでか。
半分超えてればレベルN-1のパティ+残り、という感じ。
レベルN-1の途中で止まっていることになるが、それがレベルN-2の言葉でどこか。
このように再帰的に潜っていって、レベル何の途中で止まっているかを突き止める。
確定で含まれるとわかったバーガーのパティから勘定に入れていく。
実装ミスりそう。
116
何種類食べるかを決めれば、それに応じて美味しさの高いものから取っていけばいい。
種類についてループを回すなら、log Nで作れないといけない。厳しい。
とりあえず、種類のことを気にせずK個取ったとするこれは解の下限。
構成から、どれを入れ替えたら大きくなりうるかといえば、種類数が増えるもののみ。
使用していない種類の品物を集めて価値でソート。
使用しているもののうちで使用回数が1のものは確定なので、2個以上の物を集めてまとめてソート。小さいものから順に入れ替えていく。ただし、すでに入れ替えたものと同じ種類はスキップ。各ステップでのスコアを記録しておいて、最終的に最大を出す。
種類毎の最大を出す、という一番最初にの方針を、逐次的な入れ替えで行なっていく。
これで新基準以降のABC-Dについて考察だけは終了。
500点以下は結構安定して解法にたどり着けるようになってきた。
実装してないけど。
