ABC lessons learned2

AtCoder Beginner Contest lessons learned (ABC 151-200)

ABC 6,8問体制(126..最新)のD問題をだいたい解いたので、そこから得た教訓をまとめていきます。

ABC 151-160

ABC 151-D

コードはこちら

マスを頂点をみなして、あるマスから他のマスへの最短距離を求める。126-Dと同様にBFSで求まる。木ではないので、既知の最短距離ではないマスは移動しない(移動すると無限ループになる)。

ABC 152-D

コードはこちら

Nが200000と読んで、いろいろ探索するより数え上げた方が早く実装できる、と勘づく。

先頭と末尾の組は9x9=81通りしかないので、 $1..N$ を81通りに分類すればよい。K進数の最上位の桁は、Kで繰り返し割ってK未満になったときの数である。

ABC 153-D

コードはこちら

上手く状態遷移をまとめれば、状態数が指数になるのを防げる。

モンスターをどういう順番で攻撃しても、体力が0になるまでの体力の減り方は同じ、ということが重要である。よって体力の減り方の経路は一通りだけ(2で繰り返し割る)で、ある体力のモンスターが何体あるかだけ数えれば攻撃回数になる。

ABC 153-E

コードはこちら

Greedyだと思ったらDPだった。

ということでDPで解く。このとき、 $i$ 番目までの魔法を使い(というか $i$ 番目の魔法を初めて繰り返し使うことにして)、 $h$ のダメージを与えた時( $h$ 以上は一律 $h$ )とする、 $dp[i+1][j+A]$ に配るのは $dp[i+1][j] + B$ である。 $j$ を内ループに置くと魔法を無制限に使えることを表現できる。品物を一個だけ加えるナップザックDPの $dp[i][j] + B$ から引くと上手くいかない。

ABC 154-D

コードはこちら

期待値の加法性を使う。

隣接するK個のサイコロとあるので、サイコロK個の期待値は、サイコロを1個加えてK+1個になったら、最後に加えたサイコロの期待値を減らす。期待値の加法性からこれが成り立つ。移動平均の求め方と一緒である。

ABC 155-D

コードはこちら

困ったら二分探索。

二数を書けた結果が、正、ゼロ、負の三通りに分けて、 $k$ を超える積が何個あるか尺取り法で数え上げる。緻密な実装が問われる。

ABC 156-D

コードはこちら

二項定理に対する基本的な知識が問われる。それとダブリングの使いどころである。

Nから0..N通り選ぶ組み合わせの総和は $2^N-1$ 通りである。なぜなら $1..N$ 番目の要素を選ぶか選ばないかを、全要素について独立に数え上げることと同じだからである。1引くのは何も選ばないケースを除くためだ。

nが $10^9$ と大きいので $2^n$ を繰り返し求めると終わらない。 $2^{i+j} = 2^i * 2^j$ なので $i$ と $j$ を2のべき乗について求めると巨大なnでも $2^n : mod : 1000000007$ が求まる。 $2^{0..32} : mod : 1000000007$ はダブリングで求める。コードスニペットを書いてテストしておくとよいだろう。

ここまできたら $2^n - {}_n C_a - {}_n C_b$ が答えである。

ABC 157-D

コードはこちら

Union-find木を知っていると解ける、知らないと解けないか実装が大変な問題である。

友達の友達は友達という推移関係は、友達関係をグラフで表現した時の連結成分である。なのでそれぞれの連結成分の頂点数から、既に友達である関係の数と、 同じ連結成分で ブロックしている関係の数を引く。異なる連結成分でブロックしている関係は、友達の友達は友達という推移関係は成り立たないので引かない。

ABC 158-D

コードはこちら

コレクションを反転するのはコストが高いが、反転したとみなすのフラグ1個書き換えるだけである。手元の列に対して、

• 手元の列が反転していないときに先頭に追加するのは、列の先頭に追加する
• 手元の列が反転していないときに末尾に追加するのは、列の末尾に追加する
• 手元の列が反転しているときに先頭に追加するのは、列の末尾に追加する
• 手元の列が反転しているときに末尾に追加するのは、列の先頭に追加する

反転しているか否か、先頭と末尾のどちらに追加するか if文で4通りに分けてもいいし、xorを取って2通りにまとめてもよい。

ABC 159-D

コードはこちら

全部の組み合わせの個数を挙げてから、ある種の組み合わせの個数を引く。

整数 $x$ が書かれたボールが $m$ 個あるなら、ボールの選び方は $((m+1) * m) / 2$ 通りである。整数 $x$ から個数 $m$ への連想配列にしておけば $x$ の値域について悩まなくて済む。

後はボールが一個 ($A_1 .. A_N$) 減ったら、その分ボールの選び方が減るのでその値を計算する。

ABC 160-D

コードはこちら

入力サイズから計算量を見切ることが大事である。

頂点の位置を、Xより右、X-Y間、Yより左に場合分けして解くととてもめんどくさい。BFSで距離を求めると簡単である。こういうときは $N$ が二千しかないことから、各頂点を出発点として総当たりでTLEしないと予想できる。

辺の長さが固定のときにBFSで距離を求める方法は既出なので省略する。

ABC 160-E

コードはこちら

std::vector::resize() を使う

問題文から X<A, Y<B なので場合分けを減らせる。無色のリンゴを補充しなければならない状況はなく、置き換えるだけでよいことが分かる。リンゴを色別に、美味しさの降順にソートして、赤いリンゴは元々 $X$ 個だったと考えると楽である。 std::vector::resize() は余分な要素を切り捨てるので便利である。

置き換えるなら最もおいしくない赤と緑のリンゴを、最も美味しいリンゴに置き換えればよいだろう。これは尺取り法でできる。赤と緑のリンゴをすべて置き換え終わったらもうできることはない(もっと美味しい無色のリンゴに置き換えたはずだから)ので、尺取り法のインデックスに気を付ける。

ABC 161-170

ABC 161-D

コードはこちら

これも 160-Dと同様に、入力サイズから計算量を見切ることが大事である。

再帰とメモ化で取りうる組み合わせを累計するとめんどくさそうである。しかし10進数5桁しかないのだから、上の桁に下の桁(0には0と1、9には8と9、それ以外の $i$ は $i-1, i, i+1$ をくっつけても全探索できる。

ABC 162-D

コードはこちら

これも 160-D, 161-Dと同様に、入力サイズから計算量を見切ることが大事である。配列の添え字がはみ出さないように全探索すればよい。

ABC 163-D

コードはこちら

巨大な数 $10^{100}$ が意味するのは、数を何個足したかが和から区別できることである。この習慣を覚えておく。

それさえわかれば、 $0..N$ から $K$ 個選んだときに、和として表現できる数とできない数を求めればよい。

• 和の最小値は何も選ばない0、最大値は全部選ぶ $sum(i=0..{N})$ である。
• $s = sum(i=0..{K-1})$ が最小値なので、それより小さい数 $S$ 個は和になりえない。
• 足す数をそれぞれ $N-i$ とすれば左右反転して、 $sum(i=0..{N})$ までの $S$ 個は和になりえない。
• それ以外の和は表現可能である(和にする数の集合に対して、ある数とそれより1多い数を交換すればよい。このような数は必ずみつかる)

ABC 164-D

コードはこちら

• 鉄則本の「8.6 文字列のハッシュ」問題 A56を知っていると解ける
• 累積和から部分列の総和を取る方法が使える

文字列から部分文字列を取っていくときに、部分文字列から得られるハッシュのような情報を得る。ある数が2019で割れるかどうかは、2019のすべての素因数(3と673)で割れるかどうかと同じである。つまり3で割った余りと673で割った余りを、文字列の末尾から先頭に向かって取っていく。説明の都合上、文字列を std::reverse で逆順にして最も下の桁を文字列の先頭とする。

...abcdef と桁がたくさんある整数のうち、下位1,2,3...桁を673で割った余り(mod 673)について考える。3で割った余りも同様である。

• f mod 673は、実際に割れば分かる
• ef mod 673は、(e*10 + (f mod 673)) mod 673
• def mod 673で割った余りは、(d*100 + (ef mod 673)) mod 673
• cdef mod 673で割った余りは、(c*1000 + (def mod 673)) mod 673

こうして最上位の桁まで、最も下の桁から連続する桁を673で割った余りを計算できる。10, 100, ... と $10^n$ を673で割った余りも併せて計算しておく。

次に下の桁から順に0に置き換えていく。

• 最初は何も置き換えない。このときf, ef, def, ... を673で割り切れるかどうかは既に調べてある
• 最下位の桁を0に置き換える。例えばcdefをcde0に置き換える。cde0が673で割り切れるかどうかは、 $(cdef - f) : mod : 637 \equiv 0$ つまり $f$ を673で割った余りと $cdef$ を673で割った余りが等しいということである。ここで f mod 7 を固定して、f mod 7 と等しい f, ef, def, ... を数えれば、題意の総数の一部が求まる。
• 一般的には、下の桁から連続する $i (\geq 0)$ 個の0を置き換える。下i桁 mod 7 と等しい f, ef, def, ... を数えれば、題意の総数が求まる。下i桁の値は初期値を0とし、 $i$ を更新するごとに $10^{i}$ * i桁目の数字 mod 673 を足す。
• f, ef, def, ... mod 673 と f, ef, def, ... mod 3 から、 f, ef, def, ... mod 2019 が求まる。これは $i$ と関係ないので、mod 2019をキーとして該当する余りの出現回数を一度数えて連想配列に保存しておく。

この考え方は、部分列の総和を求めるのに累積和を使う方法とよく似ている。和を余りに置き換えただけなので。

Mod 3とmod 673はACLを使うと書きやすい。

#include <atcoder/all>
using ModInt3 = atcoder::static_modint<3>;
using ModInt673 = atcoder::static_modint<673>;

ABC 165-C

コードはこちら

$N$ が小さいのでDFSの全探索で行ける。

ABC 165-D

コードはこちら

直観的には、Aを増やすほどBで割った余りが溜まっていって、Bになると余りが0に戻る、ということである。 $A &lt; B$ だと戻らないので入力条件に気を付ける。

ABC 166-D

コードはこちら

三次以上の多項式の問題は、n条根を取ると変数の取る領域がそれほど大きくないので総当たりできる。

$A^5-B^5 = (A-B)(A^4+A^3B+A^2B^2+AB^3+B^4)$ なので、 $X$ の約数を求めて総当たりすればいい。 $A-B$ は約数を総当たりし $A$ を決め打ちして総当たりすればいい。 $X^5-(X-1)^5 &gt; 5X^4$ なので、 $A$ は下限が0、上限は ${5*x}^{1/4}$ もあれば十分だろう。

約数を求めるは頻出なのでコードスニペットを書いておく。平方数の約数を二度数えてしまいがちである。

ABC 166-E

コードはこちら

絶対値は順序を固定すれば外せる。

組み合わせを列挙するので、一般性を失わず $A_i, A_j$ (i<j) なペアだけ考えればよい。定式化すると以下のように大変だが、手を動かすと何となくわかってくる。

題意から $A_1 + A_2 = 1, A_1 + A_3 = 2, ...$ と解る。これを $A_1, A_2, ...$ について数えあげると $O(N^2)$ なのでTLEするが、 $A_1$ を $A_2$ に取り換える方法がありそうである。

実際できるのである。 $A_i + A_j = j-i \Leftrightarrow A_j - j = -(A_i + i)$ である。よって $A_j - j : for : j=1..N$ が何個あるか求めて連想配列にいれておき、 $-(A_i + i) : for : i..N$ がいくつあるか連想配列で引いて総和を求めると答えが出る。

ABC 168-D

コードはこちら

部屋1から他の部屋の距離をBFSで求める。方法は既出の通り。

ABC 169-D

コードはこちら

素因数分解して、素数pで1回、2回、3回... 割ってみる。素因数とその数をコードスニペットを書いておく。

ABC 170-D

コードはこちら

任意の組み合わせを数え上げるのに、ソートしても一般性を失わないだろうか。

小さな数でそれより大きな数を割ることはできない。よって昇順にソートして、自分より大きな数で割り切れるかどうか確かめる。そのまま実装すると $O(N^2)$ になってしまうので、約数が既に出現したかどうか調べる。

なお同じ値の数が複数ある場合は互いに割り切れるので、答えの回数には含めない。

ABC 171-180

ABC 171-D

コードはこちら

要素が何個あるかは気にしない。

なので $B_i$ が何個あるかを連想配列で管理する。クエリごとに、 $B_i$ がn個あるなら、 $C_i$ をn個追加して $B_i$ をn個削除する。

ABC 172-C

コードはこちら

Aをから何冊読むか決めたら、Bから最大何冊読むかは一意に決まるので、尺取り法で求まる。

ABC 172-D

コードはこちら

縦の物を横にする。

ある数に約数が何個あるかを調べるのは大変である。しかし $1..N$ に約数 $i$ が何個あるかは、 $\lfloor N/i \rfloor$ 個とすぐわかる。縦横を入れ替えるだけですんなり解ける(私自身はこの解法を思いつかなかったが)。

ABC 173-D

コードはこちら

あれこれ悩むより、手を動かして試した方が早い。

最後の一人は誰かにとって心地よさは与えないので、フレンドリーさが最大の人から降順到着するのがよいと分かる。どこに入れるかであるが、Nが十分大きいとき、フレンドリーさが上位二名の間に入れればそこの心地よさが最小になる。つまり N, N-1, N-1, N-2, N-2, ... となる。

ABC 174-C

コードはこちら

$K$ が小さいので、実際に求めれば分かる。

ABC 174-D

コードはこちら

選択肢が二つあるが、片方があればもう片方は要らないということがある。

RWの並びはよいがWRの並びはよくないので、WRを減らせばいい。ならばRだけ左にずらっと並べて、Wだけ右にずらっと並ぶよう、Wを右に寄せればいいと分かる。つまり最左のWと最右のR入れ替えればよく、この回数を求める。これは尺取り法でできるので O(N)で解ける。

石を入れ替えれば災いは1または2減るするかもしれないが、石の色を変えても1しか減らないので、石の色を変える意味はない。

ABC 175-D

コードはこちら

解の方針は立つが、実装が非常に辛い。

まず状態遷移をループ成分に分解する。DFSでもよさそうだが、union-find木の代表元を使うと簡単である。それぞれのループ成分ごとにスコアを求めて、その最大値が答えである。

問題はスコアの求め方である。一周するとスコアが正の値になるなら、できるだけたくさん周回する。そうでそうでなければ一周しなければよい。一周に満たない場合のスコアは起点を終点の組を総当たりして $O(N^2)$ で求まる。

と書くと簡単に見えるが、WAしないように実装するのがものすごく大変である。二周分のスコアの累積和を求めて、すべての起点と長さを総当たりすればいいはずなのだが、それだけではどうしてもWAを取り切れない。

ABC 176-D

コードはこちら

普通にBFSで解ける。

と、公式解説に書いてある。おそらくその方が実装が簡単なのだろう。私の解き方は少し回りくどいが以下の通りである。

• すべてのマスを、ワープなしで行ける範囲で連結成分分解する。Union-find木を使うとできる。
• 連結成分を頂点、ワープで行ける連結成分を辺とするグラフを構成する。頂点番号は連結成分の代表元( $x + y * 1000 $ でいい)、ワープで行けるかどうかは各頂点から25通り試せばよい。同一連結成分同士を辺でつながないように注意する。
• このグラフについて、出発点の連結成分から目的地の連結成分までに経由する、最短距離つまり最小の辺の数をBFSで求める。到達不可能なら距離は無限大である。

多重辺を作らないようグラフは std::map<Num, std::set<Num>> にするが、頂点から延びる辺は edges[current] で取り出す。 edges.at(current) だと、辺がないときに例外が飛んでプロセスが終了してしまう。

ABC 177-D

コードはこちら。

グループ分けといえばunion-find木である。

友達の友達は友達という推移関係は連結成分に分解できる。これをバラバラにするには、連結成分の数だけグループを作って、疎な連結成分の人をそれぞれのグループに集めればいい。よって最小のグループ数は最大の連結成分の要素数である。これは気が付かなかった。

当時は自前で実装したUnion-find木を使っていた。今はACLを使っている。

ABC 177-E

コードはこちら

用語の定義を落ち着いて理解すれば分かる。

$GCD(A,B,C) = GCD(GCD(A,B),C) = GCD(A,GCD(B,C))$ なので、すべての要素のGCDが1より大きければ not coprime である。

Pairwise coprime なら必ず setwise coprime だが逆は成り立たないので、 pairwise coprime ではない例を一つでもみつけたら setwise coprime と出力し、そうでなければ pairwise coprime である。これは $A_{i+1}$ の素因数が $A_1..A_i$ の素因数を含むかどうかで分かる。

ABC 178-D

コードはこちら

DFS(幅優先探索)はスタックの深さに注意すればきれいに再帰で書ける。

数列は順序が異なれば違うものと数えるので、3以上の数を $S$ から引いて残りを再帰的に求めればよい。 $S$ は2000しかないので、メモ化しておけば計算時間が指数オーダーになるのを防げるし、スタックもあふれない。

ABC 178-E

コードはこちら

45度回転。

$x+y$ で等高線が引けるのは分かったが、 $x-y$ の等高線は使い道が分からなかった。式変形は公式解説にあり、より詳しい解説が記事にある。

しかし式変形をしなくても直観的に理解する方法がある。xが左、yが上に増える座標系で、x+y等高線は左下-右上関係をとらえ、x-y等高線は右下-左上関係を捉えると思えば、二点のマンハッタン距離は、二点における等高線の差の大きい方と一致する。

ABC 179-D

コードはこちら

貰うDPで解く。

配るDPでも解けるようだが、貰うDPで解いた。まず区間を $L$ の昇順にソートする。 $i=2..N$ のマスについて、区間を順番に調べて

• 区間の終わり $i - R &lt; 1$ ならおわり
• そうでなければ区間 $\lbrack max(1, i-L), i-R \rbrack$ のマスに行く方法を全部足す

区間にある貰うマスに行く方法を累積和で管理すれば、区間は10以下なので計算量は $O(N)$ になる。答えも累積和の差分で出力する。

ABC 179-E

コードはこちら

厳密解を求めるより、鳩の巣原理で解く。

余りは $0..M-1$ しかないのだから、同じ余りが二度出たら以後は周期的になる。よって、周期を求めて、

• 周期に入る前
• 周期を繰り返し
• 周期の途中で $n$ に達する

について和を求める。ただし周期に入る前に $n$ に達することがある。

ABC 180-D

コードはこちら

ジムに通うと強さがどう変わるかは今の強さと今通うジムだけで決まり、これまでどう鍛えたかには関係ない。これをマルコフ性という。

なので両方のジムに通ったとして強さが低くなる方を選べばよい。弱いうちは強さをA倍にし、その後はB増やすとよさそうだが、そこまで考察しなくても解ける。

ABC 181-190

ABC 181-D

コードはこちら

算数的な方法で解ける。Nが大きいので、順列を数え上げるとTLEする。

算数的な方法は、数字をいい感じに組み合わせると、下から3桁目が偶数か奇数かと、下から1,2桁目の組を使って8の倍数になるかどうか調べる。要は000, 008, ..., 192 かどうか調べる。間違い無いがコード量が大きい。

実は下三桁を求める方が簡単である。こちらの記事を参照。

ABC 181-E

コードはこちら

数学的考察が必要。

解を満たす組は、小さい値から順に二つずつ取る、である。最も大きい値と最も小さい値を組む、ではない。この前提が間違っているとどうにもならない。これが分かれば累積和をつかって計算量を減らせる。

ABC 182-D

コードはこちら

問題をよく読む必要がある。問われているのは最大瞬間座標であって、 $A_{1..i}$ 一組の動作完了後ではない。

累積和を累積するのは頭がこんがらがるが、コードに落とし込めばそのままである。 $i$ 組目の動作をすると、最大瞬間座標は以下の最大値である。

• 出発点(右側にしか行かない場合)
• $A_i$ だけ進まずに行ける場所(これまでの最大瞬間座標)
• $A_i$ 進むことで初めて行ける最大瞬間座標

この後、位置に累積和と $A_i$ を足し、累積和に $A_i$ を足し、累積した動きの最大瞬間座標が過去最大なら差し替える。

ABC 182-E

コードはこちら

帰納法。縦横を独立な問題として考える。

縦方向に光が届くかと、横方向に光が届くは独立なので別々に考える。公式解説にある通り、すでに光が当たっているマスはその隣もあっていることを利用して計算量を減らせる。

ABC 183-D

コードはこちら

いもす法(Imos method)を使う。

NとSとTが大きいので、すべての整数時刻についてお湯の量を求めるとTLEする。だが変化点だけその累積和を求めることで、計算量を $O(N)$ に抑えらえる。

• S, T, P を得て、入りの変化点Sでお湯の量を +P, 出の変化点Tでお湯の量を -P するイベントを作る
• イベントを時刻の昇順に並べ替える
• 同一時刻のイベントについてお湯の量をまとめる
• ある時刻のお湯の量が容量Wを超えてたら供給不能、そうでなければ供給可能である

ABC 184-D

コードはこちら

確率DPと呼ばれる。

期待値の加法性から、分岐点のその先に行く確率を逐次的に求める。DPの更新式は条件付き確率そのもの(A,B,C枚あるときにA,B,Cを一枚引く確率はA:B:C)である。私の解法は出発点(A,B,C枚)から配るDP、公式解説は終着点(いずれかの硬貨が100枚)からメモ化再帰で実装している。

ABC 185-D

コードはこちら

問題文を制約に落とし込む。

赤いハンコが青いハンコに重なってはいけないが、赤いハンコを押す場所同士が重なってもいい。ということは以下の制約になる。

• 連続する白のマスの最小値が、赤いハンコの長さの最大値 $l$ になる
• 連続する白の $n$ マスに押す回数は、 $\lfloor l/n \rfloor$ である

ABC 185-F

コードはこちら

セグメント木を使う。

加法 + と同様に XOR もセグメント木に載せられる。自分で実装したセグメント木を使ったが、ACLを使ってもよい。

ABC 186-D

コードはこちら

絶対値があると上手く値をまとめられないので、絶対値を外す。

$A_i$ を昇順にソートしても、得られる結果は等しい。なぜなら以下が成り立つからだ。

• $i &lt; j$ かつ $A_i &lt; A_j$ ならソートしても $i &lt; j$ なので、 $i,j$ の相対的な位置は同じ。
• $i &lt; j$ かつ $A_i \geq A_j$ なら位置が入れ替わるのでソート前の $|A_j - A_i|$ を足すことに等しいが、絶対値なので値は変わらない

計算量を減らすために累積和を取りたい。要素の差だけに意味があるので、最小値を0にしても同じである。よって $min(A)$ を全部の $A_i$ から引いておく。これですべて非負の値になるので、 $(A_i - A_{i-1}) + (A_{i-1} - A_{i-2}) + ... (A_2 - A_1)$ は $i$ 番目までの累積和になる。

二重 $\sum$ における $j$ の寄与分は、 $(A_j - A_1) * j$ の長方形を描くと分かる。この長方形の上辺から $A_j - A_1$ に下ろした長さの和が寄与分であり、つまり長方形の面積から $A_1..A_j$ の累積和を引いたものである。

ABC 187-D

コードはこちら

多数決は、得票数ではなく、得票数の差で考える。

得票差は全く演説しないときが最小(最も不利)である。得票数の差を増やす方法を考える。演説すると $A_i * 2 + B_i$ だけ得票数の差が埋まるので、この値が大きい順に演説し、得票差が正の値になったところで終わる。

ABC 188-D

コードはこちら

いもす法を使う。

既述の通り時刻ごとのイベントを作り、同一時刻のイベントをまとめる。後はイベントを時刻順にみて、前のイベントからの期間について、1日あたりプライム料金を最大として支払えばよい。

ABC 188-E

コードはこちら

DAGである。

ということで、in-degreeが0の頂点から順番に最安値を伝搬すればいい。トポロジカルソートを使ったが、元々入力がトポロジカルソート済なのだからもっとすっきりした線形時間の実装があった。

ABC 189-D

コードはこちら

ランレングス圧縮を実装する。その上で、ビット操作の意味を考える。

• ビット操作のANDは、出力をTrueにしたいなら、入力をTrueにせよ、と捉える
• ビット操作のORは、入力がなんであれ、出力をTrueにしたいならそうできる、と捉える

$S_i$ がANDなら $x_i$ はTrueしか選択肢が無いので組み合わせの数には影響しない。ORの並びだけみる。連続するORつまりrunにおいて、 $pos$ 個目から $len$ 個ORが連続する場合、

• この run で $y_N$ をTrueにするので、それ以前の $y$ は何でもよい。組み合わせは $(2^{len-1}) * 2^{pos}$ 通り
• このrunではTrueにせず、それ以前の run でTrueにする。このrunについては全Falseの一通りで、組み合わせの数は以前のrunで決まる。

ので、後ろのrunから順に調べて組み合わせを加算していく。

ABC 190-D

コードはこちら

等差数列の公式を因数分解する。

等差数列の公式 $N=(n+1)*n/2$ を逆に利用して $2*N=(n+1)*n$ とし、 $N$ の約数から $n$ を列挙する。 $n$ を重複して数えないように注意する。約数の数はそれほど多くないので ($log2(N)$ を超えることは無い)、重複が心配なら std::set で集計する。

ABC 191-200

ABC 191-C

コードはこちら

辺ではなく頂点に注目する。

辺に注目すると、凹の部分で上手く値が求まらなくなる。よって頂点が90度曲がる箇所を数える。ある点の周辺4マスについて、白黒のマスの数が1または3ならそこで辺が曲がるとわかる。

ABC 191-D

コードはこちら

浮動小数で簡単に解けると思ったら、精度に注意する。

X座標が求まればY座標は三角関数から求まるので、Y座標の上下限を引いて(両端が整数の場合に注意する)数える。のだが、浮動小数で実装すると丸め誤差が原因でWAする。問題文をよく読み返すと、

• $|X|,|Y|,|R| \leq 10^5$
• X,Y,R は高々小数第4位まで与えられる

なので、1+52ビット精度の浮動小数では精度が足りない。しかし64-bitではギリギリ精度が足りる。そのため浮動小数を固定小数(整数部x10000+浮動小数部)として扱う。これで10進数18桁(9桁の二乗)を誤差なく扱うことができる。

ABC 192-D

コードはこちら

答えが整数 $n$ ちょうどであることを確認するのは大変だが、答えが $n$ 以上または以下であることを確認するのは容易、という問題がある。そのときは二分探索すると求まる。

$n$ 進数と決め打ちして $M$ を表記可能かどうかは、実際に $n$ 進数で表記すればよい。 $n$ には単調性がある( $n$ を増やすと小さな数を表現できなくなる)ので、ある $n$ ではMを表記可能、 $n+1$ では表記不可能と解る。下限は $d+1$ なので、答えは $n-(d+1)$ である。

整数の二分探索は、素朴に実装すると区間が2以下のときに無限ループに陥りやすいので、パターンを確立する。

ABC 192-E

コードはこちら

ダイクストラ法である。

距離の定義を時刻にすれば、そのままダイクストラ法で解ける。BFSで最短距離を求めるときに優先度キューに追加情報を足すように、目的地と移動時間(いわゆる距離)の他に発車間隔をキューに載せればよい。

ABC 193-D

コードはこちら

条件付き確率の定義そのものである。ある数字が表に書かれたカードで出尽くした場合を考慮する。

ABC 194-D

コードはこちら

確率の加法性から明らか。

ABC 194-E

コードはこちら

Binary Indexed Tree (Fenwick Tree) を使ってみた。あるいは縦の物を横にする。

公式解説によれば $O(N)$ 解法がある。だが $O(N*log(N))$ は容認されるので、 $1..k$ が連続して出現する要素をBITで管理して、この $k$ を二分探索すると求まる。セグメント木を使うとTLEする。注意点として、BITに $A_i$ があるかないか(1か0か)を載せるので同じ数を何個載せたかは別途管理することと、BITに0を載せられないので(1-based indexing)、0は特別扱いする必要がある。

$O(N)$ 解法は縦の物を横にする、つまりmexになりうる数は連続するM個の中に出ないことを、 $A_i$ の位置から求める。

ABC 195-D

コードはこちら

$N, M, Q$ が小さいのでgreedyでいけそう。

実際価値が大きい荷物を、その荷物が入る最小の箱に収めればよい。そうでなくて、同じ価値のものをもっと大きな箱に入れるのも、同じ大きさに価値が低い荷物に入れるのも意味がない(交換すればいい)。クエリ間に依存関係はなく、 std::multiset で箱を管理して荷物の入った箱を取り除けばいい。

ABC 196-D

コードはこちら

C++の力でごり押してしまった。

半畳の間に境界線を引く/引かない、つまり半畳をまとめる/まとめないをビット全探索すると、C++実装なら2秒を切るのでACできる。境界線の内側の領域(半畳がつながったものを)をunion-find木で管理する。以下の通り全探索する。

• 最初は各半畳が孤立した領域とする
• 境界線を引くなら領域をmergeする
• 領域の大きさが2(一畳)を超えたらその場で打ち切る
• 打ち切らずに一通り境界線を引く/引かないを終えたら、一畳がA枚、半畳がB枚あるかどうか数える

ABC 197-C

コードはこちら

$N$ が小さいので全探索する。

ABC 197-D

コードはこちら

ベクトルを回転させれば求まる。

ABC 198-E

コードはこちら

$N=10^5$ ならDFSできる。

なので木を頂点1からDFSして、途中にある色を数えればいい。木なので葉に向かうときに経由した頂点の色を加え、根に向かうときに頂点の色を除く。

ABC 200-D

コードはこちら

鳩の巣原理。

鳩の巣原理であっさり解ける。こういう発想も重要である。定石通りDFSと再帰で求めてもいいが、パスを保存しながらエッジケースを実装するのが難しい。コードはこちら。