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 151-E

コードはこちら

組み合わせ総数と累積和を上手く貯える。

$A_1 ... A_n$ から $k$ 個選ぶ方法として

両端を選んで残り $k-2$ 個選ぶ
先頭(1番目)と最後の前(n-1番目)を選んで最後(n番目)は選ばない。他を $k-2$ 個選ぶ。
先頭(1番目)と最後の前の前(n-2番目)を選んでそれ以後は選ばない。他を $k-2$ 個選ぶ。

... という方法を考える。要するに最初と最後の要素の添え字の差(幅-1)が $n-1, n-2, ... , k-1$ になるように選ぶ。それぞれの選び方は ${n-2} \choose {k-2}$ 通りで、最初と最後の要素の添え字の差と定数 $k$ で決まる。ここで ${{n-1} \choose {k}} = {n \choose {k}} * (n-k) / n \quad for \quad n>0$ を使うことで、選び方の数を逐次的に求めることができる。

最初と最後の要素の添え字の差が $w-1$ と決まっているとき、 $f(X)$ は $(a_w-a_1) + (a_{w+1}-a_2) + ... + (a_{n}-a_{n-w+1})$ であり、符号をまとめると $(a_w + a_{w+1} + ... + a_{n}) - (a_1 + ... + a_{n-w+1})$ である。まとめて足す部分とまとめて引く部分については、累積和を使うことでそれぞれ $O(1)$ で求まる。

よって添え字の幅が $O(N)$ なので全体の計算量も $O(N)$ になる。

ABC 152-D

コードはこちら

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

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

ABC 152-E

コードはこちら

手抜きも時に重要。

$A_{1..N}$ の最小公倍数(LCM)を求めて、LCM/AをBにすればいい。 std::lcm() を使うとオーバーフローするので、 $A_{1..N}$ を素因数分解して得られるそれぞれの素数の出現回数を求める。一度でも出現する素数について最大出現回数を累乗し、それらを掛けたものをLCMにする。

ここで $B_i$ を真面目に求めようとして、LCMを構成する素数の個数から $A_i$ を構成する素数の個数を引いて残った素数を全部かけるとTLEする。単に $LCM / A_i = B_i$ で問題ない。

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 153-F

コードはこちら

遅延評価いもす法

解き方は複数あるが、遅延評価いもす法が分かりやすい。モンスターの座標 $1..N$ におけるダメージをいもす法で更新していく。左にいるモンスターから最小回数で順に倒すgreedyということは分かったが、回数がバイナリ1/0でないことをすっかり忘れていた。

ABC 154-D

コードはこちら

期待値の加法性を使う。

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

ABC 154-E

コードはこちら

桁を上から見るか、下から見るか。

下の桁から見るのが正解である。もしかしたら上の桁から見ても解けるのかもしれないが、私には解けなかった。公式解説を見ると再帰で解けると解るが、もう少し読み解くと以下のようになる。数字列 $abcd...$ があり、非0の数字が $abcd$ に $k$ 個要るとき、

$k=0$ なら $a=b=c=d=0$ の1通り
$k<4$ つまり $k$ が $abcd$ より短すぎるなら0通り

を特別扱いする。次に下の桁 $...$ への繰り下がり $inCarry$ が起きるかどうかを引数で受け取っておく。最下位桁については $inCarry=0$ である。

$d=0$ かつ $inCarry=1$ なら、下の桁 $...$ への繰り下がりがあり、かつ上の桁 $c$ からの繰り下がりが必ず起きる( $outCarry=1$ )。それ以外で、上の桁からの繰り下がりが起きるかどうかは状況次第である( $outCarry=0$ )。
$inCarry=1$ なら $d$ を1引く。つまり $d:=(d+9) mod 10$ にする。

ここで $d$ の値について考察し、上の桁への再帰を考える。

$d$ があるこの桁は0ということにして、 $k$ を消費しない。この組み合わせの数は、末尾を削除した数字の並び、繰り下がり、非0の数字の数がそれぞれ $(abc, outCarry, k)$ の場合について求めたものである(なので再帰的定義である)。
$d>0$ ならこの桁は非0の値 $1..d$ のいずれかにして、 $k$ を1消費する。この組み合わせの数は、同様に $(abc, outCarry, k-1)$ の場合について求めたものを $d$ 倍した値である。
$d<9$ ならこの桁は非0の値 $d+1..9$ のいずれかにして、 $k$ を1消費する。この組み合わせの数は、同様に $(abc, 1, k-1)$ の場合について求めたものを $9-d$ 倍した値である。上の桁から繰り下がりがないと、 $d$ より大きな数字をこの桁に設定できない。

再帰呼び出しで引数で何度も呼び出すことに備えてメモ化するとよい。再帰とメモ化するためのキーは、 $N$ の桁を表現する数字の部分列そのものではなく、文字列の先頭からの長さでよい。再帰呼び出しは $N$ の最下位桁から順に取り除くからである。つまり再帰呼び出しの引数とメモ化のキーを(入力 $N$ から上位何桁取るか、繰り下がり、非0の数字の数)にする。

ABC 155-D

コードはこちら

困ったら二分探索。

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

ABC 155-E

コードはこちら

154-Eと似ている。

基本的には154-Eと同様なのだが、入力が大きいのでDFSは使えず、BFSするとTLEした。なので単純にメモ化しながらループする。メモ化するのは、(下から何桁目までに、下の桁から繰上りがあったかどうか) のとき使う紙幣の最小枚数 $DP[0..N][0..1]$ である。

154-Eの繰り下がりと同様に、ある桁 $d$ 、下の桁から繰上りがあったかどうか $inCarry=0 or 1$ があったとき、上の桁から繰り下げるかどうか $outCarry=0 or 1$ を固定して、

$d:=d+inCarry$ について
$d<10$ ならその場で $d$ 枚紙幣を払い
$d>0$ なら上の桁から借りてお釣りをもらうことにして $10-d$ 枚紙幣を払う

最上位桁が繰り上がったときを考慮する必要がある(そうしないと91の答えが3でなく2になってしまう)。このためには、 $min(DP[N][inCarry]) += inCarry$ とすればよい。答えは $min(DP[N][0..1])$ である。

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 156-E

コードはこちら

k個のお菓子をn人に分ける。

自力では解けず、こちらの解説を用いた。この解説通り実装すればよい。

解説中、 $n-i$ 個の部屋に1人以上、合計で $n$ 人を入れる組み合わせの総数は、 $n$ 人を $n-i$ 部屋に一人ずつ入れて、残り $i$ 人を $n-i$ 部屋に入れる組み合わせの数である。これは $i$ 人と $n-i-1$ 個の仕切りについて、人と仕切りを区別しない順列組み合わせの数 ${{i+n-i-1} \choose {i}}$ = ${{n-1} \choose {i}}$ = ${{n-1} \choose {n-i-1}}$ である。

${n \choose {n-i}}$ = $n!/(i!*(n-i)!)$ = ${n \choose {n-(i-1)}} * (n-i+1) / i$ を用いて組み合わせの総数を逐次的に求めないとTLEする。

ABC 157-D

コードはこちら

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

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

ABC 157-E

コードはこちら

力業すぎる。

type 2クエリからセグメント木を連想する。文字は英小文字しかないのだから、26本のセグメント木を作り、ある区間にa,b, ..., z があるかどうか更新して調べればよい。type 1 クエリで変更前の文字が何であったかは、 $S$ を直接更新すれば分かる。

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 159-E

コードはこちら

制約をよく見る。

$H \leq 10$ から、鉄則本をA72を思い出す。横方向(行方向)に沿って切る方法は $2^{H-1}$ しかないので総当たりできそうである。後は縦方向(列方向)の切り方をgreedyに求める。

例外処理として、 $K$ が小さいときはすべての列を幅1で切っても制約を満たさない可能性がある(例えば $K=1$ ですべてのマスが1のとき)。そのような横方向の切り方は見つけ次第除外する。後は一列ずつ $i=1..W$ 列の右側で切れるかどうか試して、

切れ端に含まれる 1が $K$ 個を超えたら、 $i$ 列の右側ではなく左側で切る。 $i$ 列を起点に調べなおす。
そうでなければ切らずに、 $i+1$ 列の右側で切れるかどうか調べる。

横方向+縦方向に切った回数の最小値が答えである。

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 161-F

コードはこちら

ゴールから見た方が簡単である。

まず $N = i \times K+1$ を満たす数は $K$ ずつ減算して1になる。次に $N = K^{i}(K \times j+1)$ を満たす数は $K$ ずつ除算して1になる。よって $i = 2.. \sqrt{N}$ を決め打ちして、 $i$ で割れるだけ割って残った数を $i$ で割った余りが1なら、 $i$ は $K$ の候補になる。私の実装はこのように $N$ から減らしたが、解説にあるように1から $i$ を構成する方が考えやすい。

念のため $K$ の候補に $N-1$ の約数と $N$ を加えてから1を除いた。 std::set で重複を除いている。

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 < 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 > 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 167-E

コードはこちら

動的計画法できなさそう、という見切りが必要。

同じ色が並んでいるブロックが残り $0 \leq i \leq K$ 組というのはメモ化できなさそうである。そこで発想を変える。 $N$ 個のブロックがあり、同じ色が並んでいるブロックが $i$ 組あるなら ${N-1} \choose {i}$ 箇所ある。

これをすべての $i$ について求める。同じ色が並んでいるブロックがなければ、色は $M*(M-1)^{N-1}$ 通りある。同じ色が並んでいるブロックが $i$ 組あるならブロックを圧縮する、つまり $N-i$ 個のブロックがあると考えて、同じ色が並んでいるブロックが ${N-1-i} \choose {i}$ 箇所ある。156-Eと同様、組み合わせの数は逐次的に求める。

ABC 168-D

コードはこちら

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

ABC 168-E

コードはこちら

2時間近くかかったが、久しぶりに青diffを解けた。

$A_i \cdot A_j + B_i \cdot B_j = 0$ が内積だということはすぐわかる。 $(A_i, B_i) = (0,0)$ ならどんな $(A_j, B_j)$ との内積も0になるので原点を特別扱いすることも分かる。しかしそこからが長考だった。

自明な答えとして、イワシは一匹なら答えは1である。

原点なイワシ $(A_i, B_i) = (0,0)$ をいったん無視して、 $(A_i, B_i) \ne (0,0)$ なるベクトルを既約のベクトルにして、ある向きのベクトルが何種類あるか数えられるようにする。これは $(A_i, B_i)$ を $gcd(|A_i|, |B_i|)$ で割る。割ったものに対して、以下の通り数えて連想配列 std::map<std::pair<Num, Num>, Num> に収める。ここで0種類増やす、つまり連想配列のエントリだけ作っておくと後の処理が楽である。

既約なベクトル $(A_i, B_i)$ を1種類増やす
対称なベクトル $(-A_i, -B_i)$ を0種類増やす
直交するベクトル $(-B_i, A_i)$ $(B_i, -A_i)$ を0種類増やす

次に登場したベクトル $(A_i, B_i)$ を種類ごとに std::vector<std::pair<Num, Num>> に追加する。ここで $(A_i, B_i)$ が出現したら $(-A_i, -B_i), (-B_i, A_i), (B_i, -A_i)$ も既に出現したことにすると、対称または直交するベクトルをまとめて一回だけ追加できる。追加したかどうかは std::set<std::pair<Num, Num>> で管理する。

ベクトル $(A_i, B_i)$ の種類ごとに、イワシをどう組み合わせられるか考える。 $(A_i, B_i)$ および $(-A_i, -B_i)$ から $P_i (\geq 0)$ 匹、直交する $(-B_i, A_i)$ および $(B_i, -A_i)$ から $Q_i (\geq 0)$ 匹選べるとする。直交するイワシは選べないが直交しないイワシは選べるので、選べる組み合わせは $C_i = 2^{P_i} + 2^{Q_i} - 1$ 通りである。

ベクトル $(A_i, B_i)$ の種類が異なるイワシは直交しないので、独立に組み合わせられる。よって選べる組み合わせは $\prod_i C_i : (A_i, B_i) \ne (0,0)$ である。

ここで重要なこととして、原点なイワシ $(A_i, B_i) = (0,0)$ が $K$ 匹いたら、それぞれ一匹ずつクーラーボックスに入れることができる。これを忘れるとWAする。よって答えは $\prod_i C_i : (A_i, B_i) \ne (0,0) + K$ である。

1260 ms掛かっているのを見ると、ベクトルの種類を数え上げるにはもう少し洗練された方法がありそうだ。

ABC 169-D

コードはこちら

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

ABC 169-E

コードはこちら

二分探索ではなかった。

$lower..upper$ の範囲の中央値はいかようにも作れる。では $lower$ と $upper$ を二分探索で求めるコードを書くと異常にややこしい。実は $lower$ は $A$ の中央値、 $upper$ は $B$ の中央値である。プログラミングというより数学の問題である。

小数が出ると厄介なので、入力値を二倍して答える前に半分にする。 $lower$ が奇数なら取りうる中央値は1個多い( $upper$ も同様)。

ABC 170-D

コードはこちら

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

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

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

ABC 170-E

コードはこちら

力業すぎる。

C++の速度でゴリ押すなら、幼稚園をキー、園児のレートを値とする std::map<Num, std::multiset<Num>> を作ればよい。min(全幼稚園のmaxレート)は、全幼稚園を載せたセグメント木で管理する。関数を std::max , 元(モノイド)を inf にしておけば、2秒を切ってACできる。1-based indexで通すなら入力を読み込むときもそうする。

ABC 171-180

ABC 171-D

コードはこちら

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

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

ABC 171-E

コードはこちら

E問題が10分以下で解けることもある。

めったにないE問題茶diffである。XORパリティと言えばわかる。自分以外の数字のXORを取るということは、数字の各桁について、自分以外の数字で1が出た回数が奇数回なら1、偶数回なら0を意味する。

$a_{1..N}$ を XORしてパリティを求める。1 XOR 1 = 0から、数字の各桁についてある $a_{1..N}$ は1回だけ数えるのと同じである(Nは偶数なので)。つまり数字の各桁について、 $a_{1..N}$ での出現回数が奇数回なら1、偶数回なら0を意味する。

ということで数字の各桁について、 $a_{1..N}$ での出現回数が奇数回(1)で、 $a_1=a_{2..N}$ での出現回数が奇数回(1)なら、 $a_1=0$ である。同様によく考えると、求める答えはパリティと $a_i$ のXORである。

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 174-E

コードはこちら

二分探索である。

丸太の最大長を決め打ち、 $K$ 回以内で切れるか測ればよい。長さ $L$ の丸太を $i$ 回切るなら明らかに $i$ 等分が最適なので(何を思ったか $2^i$ 回切って数十分使ってしまった)、何回切る必要があるかは $\lceil L/i \rceil$ 回である。

なのだが、探索幅の下限を $1e-6$ にしないと、WAかTLEになる。整数演算だけで解こうしたが上手くいかなかった。だがやはり整数で解かないと解が安定しないらしい。整数解法はこちらで、区間のleftではなくrightつまり total > k ではない最小の値を返す。二分探索はこれが常にややこしい。

ABC 174-F

コードはこちらだが、実質的にはある記事そのものである。

Mo's Algorithm で解く。Mo's Algorithmを知らないとどうにもならない。

ABC 175-D

コードはこちら

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

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

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

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

ABC 175-E

コードはこちら

三次元DP

三次元の動的計画法を作る。行、列、ある行でのアイテム取得回数 0..3 を上から下、左から右にスキャンする。0行0列は価値0のアイテムがあるとみなす、つまり入力アイテムの位置を1-base indexingすると、スタート地点のアイテムを拾うかどうかを例外処理しなくて済む。

左から右にスキャンしてアイテムを拾うとアイテムの数が1増えるが、行を下に移ったときに拾ったアイテムの数が0に戻ることに注意する。

ABC 176-D

コードはこちら

普通にBFSで解ける。

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

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

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

ABC 176-E

コードはこちら

縦横を独立に考える。

破壊対象が最も多い行と、破壊対象が最も多い列はそれぞれ独立に考えることができる。よって破壊対象が最多の $rmax$ である行(複数あり得る)と、破壊対象が最多の $cmax$ である列(複数あり得る)が候補になる。これらの行列の交点ぴったりに破壊対象があると、破壊対象が一つ減るので、これら行列の組を全探索する。

実は全探索しても大丈夫である。もし交点に破壊対象がないのであれば答えは $rmax+cmax$ と解るのでその場で終了できる。この探索は最大 $M+1$ 回なので十分早く探索を打ち切ることができる(公式解説より)。

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 < 1$ ならおわり
そうでなければ区間 $\lbrack max(1, i-L), i-R \rbrack$ のマスに行く方法を全部足す

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

なおこの問題は遅延評価セグメント木でも解ける。実装はこちら。ただしこの問題では $K$ が小さいので、DPで12 ms、遅延評価セグメント木635 ms となり高速化には寄与しない。

ABC 179-E

コードはこちら

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

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

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

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

ABC 180-D

コードはこちら

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

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

ABC 180-E

コードはこちら

三角不等式

三角不等式を考えない一般的な巡回路については、ある都市を訪れたかどうかが $2^N$ 通り、ある都市を訪れたかどうかつまり訪れた都市の集合が決まっているときに、今いる都市から他の都市への遷移が $N^2$ である。これを収束するまで繰り返すと $(N^3*2^N)$ になってTLEする。

しかし三角不等式が成り立つときは同じ都市を二度訪れる必要はない。入力例2が引っかけである。このときは訪れた都市の数が1,2,...,Nになるように集合を拡張すればいい。つまり(訪れた都市の集合, 今いる都市)をキー、値を最小コストとするDPを行い、すべての都市を訪れて今都市1にいるときの値を答えにする。

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 183-E

コードはこちら

引くDPは累積和にもできる。

配るDPを素朴に実装すると $O(N^3)$ になってTLEするので工夫がいる。解説通り、移動方向別に累積和を作ると解ける。漸化式から導けるが、より直観的には左、上、左上方向のどこから一手で飛んでこれるかについての、それぞれの累積和である。

ABC 183-F

コードはこちら

std::move を使う。

生徒の集団をunion-find木で管理し、集団に属する生徒についてクラスをキー、生徒数を値とする連想配列 std::map<Num, Num> で管理する。生徒aを含む集団と、生徒bを含む集団が新たに合流するときに、union-find木で管理する生徒の集合と、クラス-生徒数の連想配列もマージする。

このときこの連想配列を、union-find木の代表元(root, leader)に持たせ、代表元以外には持たせないようにする。そうすれば誰が連想配列を持っているか迷わなくて済む。union-find木をマージしたときに代表元が変わったら、以前の代表元が持っていた連想配列を新しい代表元に std::move する。

ABC 184-C

コードはこちら

まず原点に移動する。

原点に移動すれば式はすっきりする。公式解説通りの場合分け通りに実装したはずなのに、ついにACできなかった。

ABC 184-D

コードはこちら

確率DPと呼ばれる。

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

ABC 184-E

コードはこちら

TLE対策が必要

01-BFSで最短距離を求める、というのはすぐわかるのだが、ワープゾーンがあるマス同士を枝で結ぶとTLEする。ワープゾーンa..zという頂点を一つずつ、計26個作ればいいことは思いつく。しかし実際に実装するのが大変である。解説通り、普通のマスからワープゾーンに距離1、ワープゾーンから普通のマスは距離0にすると上手くいく。ワープゾーンへの距離を持たせて、枝を刈らないとTLEする。

BFSのループ内に上下左右の頂点、障害物と枠外には進めない、ワープゾーンの出入りと直接構成する必要がある。とにかく、ワープゾーンの出入りを枝で表現すると、TLE, RE, MLEとあらゆることが起きうる。

ABC 184-F

コードはこちら

半分全探索

半分全探索を完全に忘れていた。これは JOI 本選 2008Cとしてあまりにも有名である。 $N \leq 40$ を見たら、鉄則本の目次を眺めるとよいかもしれない。それと $N=1$ を特別扱いするには、空集合を解く時間の候補を0だけにする。

ABC 185-D

コードはこちら

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

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

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

ABC 185-E

コードはこちら

編集距離

題意は編集距離、またの名をレーベンシュタイン距離の定義そのものである。

削除はそのまま
要素を挿入するのは、他方の列から要素を削除するのと同じこと
編集後の要素の違いは、要素を置換するコストと同じ

レーベンシュタイン距離の求め方はこちらが参考になる。初期化と更新式を併せて10行程度で書ける。

ABC 185-F

コードはこちら

セグメント木を使う。

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

ABC 186-D

コードはこちら

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

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

$i < j$ かつ $A_i < A_j$ ならソートしても $i < j$ なので、 $i,j$ の相対的な位置は同じ。
$i < 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) \times j$ の長方形を描くと分かる。この長方形の上辺から $A_j - A_1$ に下ろした長さの和が寄与分であり、つまり長方形の面積から $A_1..A_j$ の累積和を引いたものである。

ABC 186-E

コードはこちら

拡張ユークリッドの互除法

$S+K \times i=0 \quad mod \quad N$ つまり $K \times i=-S \quad mod \quad N$ すなわち $i=-S/K \quad mod \quad N$ を求めればよい。Nが素数ならフェルマーの小定理を使えるが、Nが素数でないときは拡張ユークリッド法を使う。拡張ユークリッド法を直接実装する必要はなく、実はACLを直接使ってよい。

より具体的には以下の通りである。

拡張ユークリッドの互除法を用いて、 $g=gcd(|A|,|B|)$ , $Ny - Kx = g$ なる $x,y$ を求める。これを基に $Ny - Kx = S$ を満たす最小の正の $x$ と求める。

$S$ が $g$ で割り切れなければ玉座に座ることが永遠にできないので -1 を出力する。そうでなければ、 $Kx - Ny = g$ を満たすある $x$ が存在し、 $N((S/g)y) - K((S/g)x) = S$ である。 $(x,y)$ を一単位動かすということは $(K/g, N/g)$ 動かすことなので、 $(S/g)x$ を $N/g$ で割った余り ($x$ が負なら負の無限大方向にある $N/g$ の倍数に対する余り)が答えである。実装はこちら。

こちらの記事の通り、中国余剰定理で解くこともできる。

ABC 187-D

コードはこちら

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

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

ABC 187-E

コードはこちら

実装が大変

おおよその解法はすぐ思いついたが、110分掛かった。諦めない根性も必要である。まずデータ構造を示そう。

辺 $1..N-1$ の始終点 std::vector<std::pair<Num, Num>> abset
木をDFSして根から葉、左から右に頂点番号を振りなおしたID std::vector<Num> ids
頂点より根方向の部分木のうち、頂点番号を振りなおしたIDの最大値(葉なら0) std::vector<Num> max_id
ID $[L,R]$ に $x$ を加算するという区間の集合 std::vector<std::tuple<Num, Num, Num>> spans
上記区間の集合から求めた、IDに対応する整数 std::vector<Num> score

解き方の概要を示す。

木をDFSして根から葉、左から右に頂点番号を振りなおす。
クエリは abset を参照する。クエリ2は頂点a,bを逆に読み替えるだけなので std::swap すればよい
頂点from に対応するID $id_{from}$ 、頂点to に対応するID $id_{to}$ があったとする。toがfromより根に近いつまり浅いなら、 $id_{from}$ > $id_{to}$ である。そのようにIDを振ったのである。このとき頂点fromの部分木にしか到達できない。IDでいうと、 $id_{from}$ 以上、部分木の最大頂点( max_id(from) から分かる)以下である。
fromがtoより根に近いつまり浅いなら。このとき頂点toの部分木には到達できない。よって到達可能な頂点は、 $id_{from}$ 以下、頂点toの部分木の最大頂点( max_id(to) )より番号の大きな頂点である。
クエリに対応して、頂点 $[L,R]$ に $x$ を加算するよう spans に積んでおく
すべてのクエリを読んだら、いもす法で区間の値 spans を統合して score にする。こうすると頂点IDに対応する値が求まる。
最後に頂点 $1..N$ に対応するIDをキーとする値を出力する

fromがtoより根に近いつまり浅いときは、部分木に $-x$ を足して全体に $x$ 下駄を履かせれば実装が少し楽になる。常套手段らしい。

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 189-E

コードはこちら

アフィン変換である。

座標に行列を掛けるとクエリに対する座標変換ができる。これをアフィン変換という。クエリに対応する行列を見ていく。

90度時計回り

$$\begin{pmatrix} 0 & 1 & 0 \\ -1 & 0 & 0 \\ 0 & 0 & 1 \\ \end{pmatrix} $$

90度反時計回り

$$\begin{pmatrix} 0 & -1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \\ \end{pmatrix} $$

$x=p$ で上下反転

$$\begin{pmatrix} -1 & 0 & 2p \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{pmatrix} $$

$y=p$ で上下反転

$$\begin{pmatrix} 1 & 0 & 0 \\ 0 & -1 & 2p \\ 0 & 0 & 1 \\ \end{pmatrix} $$

変換行列 $M_i$ があるとき、 $A_i$ 個目の操作を行った後の駒 $(x,y)$ の座標は $M_i * ... * M_1 * (x, y, 1)^{t}$ で求まる。行列を掛ける向きに注意する(最初に書ける行列が右端)。

ABC 190-D

コードはこちら

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

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

ABC 190-F

コードはこちら

転倒数と言えばセグメント木

この問題は座標圧縮が要らないので Fenwick Tree でもよい。いずれにせよ $a_0..a_i$ を順にセグメント木に挿入する、つまりセグメント木の $a$ の値を1にすると、 $a_i$ が関係する転倒数は $a_i$ を挿入する直前のセグメント木における $a_i$ より大きな数の和である。

これで $k=0$ のときの転倒数 $sum_0$ が求まる。 $sum_0$ から $sum_1$ を作る方法を考える。これは $sum_0$ において $a_0$ が関係する転倒数を除いて(引いて)から、 $sum_1$ において $a_i$ が関係する転倒数を再測定して加算すると求まる。

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 191-E

コードはこちら

久しぶりにダイクストラ法

それぞれの出発点について、ダイクストラ法を使って最短距離を求めればいい。多少工夫がいる。

同じ出発点から終着点への道路については、最短経路の道路だけ残して他は捨てる
ダイクストラ法のキューは、初期状態で出発点の隣を積む。出発点を積むのではない。
距離の初期値は、出発点-出発点のループがあればその距離、そうでなければ無限大にする

公式解説では、道路の向きを反転して出発点に向かう距離を求めているが、上記の方法であれば道路を反転したグラフは作らなくてよい。

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枚あるかどうか数える

解説通りに畳の配置でDFSすると9ミリ秒で解ける。私のコードはこちら

ABC 197-C

コードはこちら

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

ABC 197-D

コードはこちら

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

ABC 197-E

コードはこちら

えいやっとDP

同じ色のボールを回収するなら、右端のボールまで行って左端のボールまで回収するか、左端のボールまで行って右端のボールまで回収するか、どちらかにすればいい。左端か右端以外の場所で止まる意味は無い(次の色になってから動けば済むことなので)。

ここで今の色の左端と右端、次の色の左端と右端を組み合わせてDFSするとTLEする。そこでDPできないかと考える。つまり $DP[i][2]$ を、 $i$ 番目の色を回収して、左端または右端のボールを回収した時点の移動距離、とする。これでACできるが、証明が分からない。

ABC 198-D

コードはこちら

問題文をよく読む。

文字が同じなら入る数字も同じ、というのは分かる。しかし数字が同じなら文字も同じ、ということは問題文をよく読むと解る。後者の制約のおかげで随分簡単な問題になる。

まず文字が11種類以上あるときは解けない。文字が10種類以下なら総当たりでよい。文字が $n$ 種類あるとき、 $0..9$ から数字を $n$ 個取り出し、取り出した数字の順列組み合わせを文字に当てはめて総当たりする。文字の順序は、総当たり中に変わらなければ何でもいい。

$0..9$ から $n$ 個取り出す方法は、 $0..01..1$ という風に $0$ を $10-n$ 個、 $1$ を $n$ 個並べた配列を初期値として、 std::next_permutation すれば $0..9$ を取り出すか否かが分かる。

ABC 198-E

コードはこちら

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

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

ABC 199-D

コードはこちら

解説を読んでも解けないのが青diff

連結成分に分解してそれぞれ解く、DFSでたどるのは分かったが、入力例1を解くことができずに諦めた。単に頂点の色を決め打ちして進むと、入力例1の右回りと左回りで同じ塗分けを重複して数えてしまう。DFSで頂点をたどる方法を固定すれば、重複せずに数えられる。

DFSで頂点をたどる順序を求めて頂点を追加すると、根が最初、深い場所が後になる。このとき追加順つまり根を最初に、深い場所を最後たどる必要がある。そうしないとTLEする。うっかり逆にしたためにTLEがなかなか取れなくて苦労したが、この難易度が青diffである。

ABC 200-D

コードはこちら

鳩の巣原理。

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