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

トップページへ

コードはこちら

n進数表記とは、ばらばらの桁を集めて数を表示する方法である。

Nim数は2進数のそれぞれの桁を独立に扱えるのが原理である。同じ原理を2進数以外でもできる。100進数を導入すると、10進数2桁をひとくくりにできて、297通り(0はおもり無しに相当する)の数を表現できる。2進数の複数ビットをまとめれば上手くいくのではと思って、300個以下に減らなかったのはちょっと惜しい。

コードはこちら

二通り考える

ここでは $i=0..N-1$ つまり 0-based indexingに読み替える。

• $[i, (i+1)mod N]$ に餌をあげたら、 $[(i+1)mod N, (i+2)mod N]$ に餌をあげてもあげなくてもよい
• $[i, (i+1)mod N]$ に餌をあげなければ、 $[(i+1)mod N, (i+2)mod N]$ に餌をあげなければならない

ことが分かる。そうしないと動物 $(i+2)mod N$ は餌をもらえない。逆にこれ以上餌をあげるとお金が無駄になる。よって $A_0$ 払って動物0と動物1に餌をあげるかどうかを決め打ちした2通りを出発点に、餌をあげる/あげないでDPする。初期値をいい感じに設定すると場合分けが減る。

• $[0, 1]$ に餌をあげるとき、餌をあげる/あげないの初期値は $(INF, A_0)$
• $[0, 1]$ に餌をあげないとき、餌をあげる/あげないの初期値は $(0, INF)$ で、最後に $A_{N-1}$ を足す

コードはこちら

包除原理が使える。

3つの数が異なる組を数えるのは大変だが、3つのうち2つの数が同じ組、3つとも同じ組を数えるのは容易である。公式解説通りに数え上げてもよい。コードは こちら

コードはこちら

基本ダイクストラ法

ダイクストラ法で解けばいいのだが、以下の制約を加える。

• いつも通り、頂点から出ている辺=既にある道路だけ移動可能である
• いつもと違って、次の頂点に行けるかどうかは、辺があることかつ、辺の先に到達する方法がまだないことである。これはunion-find木で管理できるのだが、実はダイクストラ法なら何もしなくてもそうなる。

こうすれば都市1から他の都市へのパスは必ず木になる。後は辺を辺番号に逆算して出力する。

コードはこちら

ハフマン符号化

切り出したパンのうち、短いもの2つをくっつけて、切り出す前と考える。くっつけたパンが一塊とみなし、やはり短いもの2つをくっつける。これを逆順に行うとハフマン符号化で、切り出す前のパンの長さの和がコストで、このときコストが最小になる。

$r = l - \sum A_i$ とする。 $r = 0$ ならパンは余らないので上記の分割が答えである。 $r > 0$ なら長さ $r$ のパンを配ると考えて(値が $r$ の要素を $A$ に一つ追加して)、同様に解くと答えが得られる。

コードはこちら

やはり包除原理が使える。

整数をAで割った余りとBで割った余りは、AとBの最小公倍数の周期で求まる。ので求めようと思えば求まるが大変煩雑である。包除原理を使って、AまたはBの倍数、AおよびBの倍数を数えるとあっさり終わる。そのように実装したコードが こちら

コードはこちら

累積和でDPの計算量を減らす。

素直にDPするとTLEするので、累積和を使って $sum(A_{1..m})$ を求めて置く。 $K=0$ の扱いに注意する( これを忘れるとWAする )。if分岐を減らしたコードが こちら

コードはこちら

公式解説の最初の方にある方法とはかなり異なる。

$i$ を素因数分解して、ある素因数が奇数個あったとする。 $i \times j$ を平方数にするためには、 $i \times j$ の素因数が偶数個になるよう、 $j$ がこの素因数を必ず含む必要がある。例えば $i = p \times q^3$ なら、 $n \geq j = p \times q \times r \times r$ である。 $1 \leq r \leq \sqrt{n / (p \times q)}$ から、 $i$ を固定した時の $j$ は $r$ 個であることが分かる。

公式解説は色々あるが、2番目の方法を実装すると こちら のようになる。 $2 \times 10^5$ の次の平方数まで探すように、少し多めに探索しておく。

コードはこちら

問題文をよく読む。

頂点の次数が3以下で $k_i \leq 3$ なので全列挙で解ける。以上。

コードはこちら

Qが大きいので、累積和が必要と解る。

Aを昇順に並び替えても答えは変わらないので並び替える。そうすると $X_i$ より大きい数と小さい数に二分でき、それぞれの個数は std::lower_bound から分かる。後は累積和を使って答えを求める(幅が要素数、高さが $X_i$ の長方形を切り取る)。

コードはこちら

std::map::[] にご用心。

std::map::[] はキーに対応する要素がなければデフォルトコンストラクタで要素を作って登録する。なのでキーに対応する要素がなければ0を足すのを、 += aMap[key] にすると、どんどん連想配列の要素が増えてTLEする。 std::find(key) でキーに対応する要素の有無を調べて、要素がなければ足さないようにして連想配列の要素が増えないようにする。

さて本題であるが、 $A_1$ を決めうちすれば $A_{1..N}$ は一意に決まる。なぜなら、

• $A_2 = S_1 - A_1$
• $A_3 = S_2 - A_2 = S_2 - S_1 + A_1$
• $A_4 = S_3 - S_2 + S_1 - A_1$

よって $SS_i = S_i - S_{i_1} + S_{i_2} ... S_1$ の部分を、 $i$ が奇数か偶数で分けて累積和で求める。

こうしたら $A_{1..N}$ を $X_{1..M}$ のいずれかに決め打ちして、 $x = X_{1..M}$ に一致する $A_{1..N}$ の個数を数える。 $SS[x]$ の個数をあらかじめ数えて連想配列に載せておけば、 $A_i = SS_i + (-1)^{i-1} A_1 = x$ となる $A_i$ の個数を数えるのは、 $x - (-1)^{i-1} A_1$ の個数を数えることと等しい。すでにある連想配列を使うにはキーをオフセットするのも頻出の方法である。

$M$ が少ないので、計算量 $N \times log(N) M^2$ で間に合う。ただし上記の通り連想配列を上手く使わないとTLEする。

公式解説通り実装すると簡潔な コード になる。式展開が重要である。

コードはこちら

区間といえばいもす法。

ということで区間の累積和を取る。正の累積和が続く区間を合併し、累積和が0になったところで別の区間に切り分ければよい。ランレングス符号化と似ている。

コードはこちら

ループ検出

人間嫌いな関係にループがある場合、一つの関係は嫌いなまま解決できず、残りの関係は適切な順番にキャンディを配ることで解決できる。よってループ中で最も低い不満度が、そのループの最も低い不満度になる。ループ以外は適切な順番でキャンディを配ることで不満度を0にできる。

よってループ検出を行い、それぞれのループの最低不満度を足すと答えが求まる。ループ外にあっていつかループにたどり着く頂点は、既に訪問したループに出合ったら探索を打ち切ることで、同じループを二度数えない。

有向グラフの強連結成分分解を使うと簡潔に書ける。コードは こちら 。

コードはこちら

頂点が少ないグラフはワーシャルフロイド法。

ということでワーシャルフロイド法で解ける。最低で何回訓練を行う必要があるかを距離と定義し、距離の和をsumではなくmaxにすると、どの経由地を通ったかで最短距離を求めることができる。公式解説にあるが分からなかった(解答履歴には自力で解けなかったとある)。

二分探索でも解けるようだが、上限を $4 \times 10^9 + 9$ くらいにしないと演算オーバーフローしてWAするのと、そうでなくてもTLEが発生してしまう。

コードはこちら

DFSではなくDP

DFSで解けそうな気がするが、DFSだとWAかTLEになる。なので空文字列から素直にDPする。コストと、 $9..1$ の出現回数で二次元DPする。なお同じコストの数字については、同じコストで最も大きな数字 $9..1$ を残して他は捨てる。

• 初期状態は空文字列に相当し、どのコストについても $9..1$ の出現回数はすべて0回とする。
• 配るDPで数字を一つ加えた時のコストを求める。コストが $N$ より大きければ遷移しない。コストが $N$ 以下なら $9..1$ の出現回数について辞書順で大きなものに差し替える。
• 辞書順とは、 $9..1$ の出現回数の和つまり桁数が大きいか、桁数が同じで $9,8,...,1$ の出現回数が辞書順に大きいことである。これは出現回数を繰り返して桁に展開すれば分かる。なので出現回数は $9..1$ として、 $1..9$ とはしなかった。

$C_i \leq N$ なので "0" は答えではない。ちなみに公式解説を読むと、桁数が求まるので貪欲法で上の桁から解けた。実装は こちら

コードはこちら

残機つぶしを思い出す。

あるステージから先に進まずそのステージを解き続ける方が、ステージの繰り返し回数に対して必要な時間が減るということである。今のステージから先に進む必要はなく、そうでなければ先のステージに進み、前のステージに戻ってもいいことは何もない(前のステージも今のステージもストーリー映像はみなくていいのだから)。これを全ステージ試せば解る。

コードはこちら

サイクル検出

箱に重さ $X$ 以上詰めていき次は $i$ 番目から詰める、というのを繰り返すと、いつかは $i$ が二度出てくる。つまり $i=0$ から初めてサイクルが発生する。よって $K$ がサイクルの手前かサイクルの中の位置かを判断し、その位置で詰めるじゃがいもの数をあらかじめ求めておいて答える。

$\sum W = n \times X + rem$ として、

• $rem = 0$ なら、 $W$ を一種類ずつ $n$ 個詰めるという作業を毎回行う
• $rem > 0$ なら、 $W$ を一種類ずつ $n$ 個詰めて、 残り $rem$ 以上の重さを箱に詰める。 $W_i$ の $i$ に応じて、 $rem$ 以上なるように $p$ 個詰めて、 その後 $(i+p) \quad mod \quad N$ 番目から詰めるということを、サイクルが見つかるまで更新する。

コードをきれいにしたのが こちら 。必ず $N \lfloor X / \sum(W) \rfloor$ 個詰めるのを忘れない。

コードはこちら

推移可能といえばunion-find木

二つの円が重なっているかどうかの判定は、以前書いた通りである。

コードはこちら

ある数が無くなって困るか。

$LCM(S), S = {a_1,...,a_N}$ から1つ数を抜いて $LCM(S \setminus a_i)$ を考える。 $a_i$ を抜いたら最小公倍数が減るというのは、 $a_i$ が持つある素因数 $p$ の個数が最大であるということである。丁寧に書くと、

• $a_i$ が素数 $p$ について約数 $p^e (e>0)$ を持つとして
• すべての $a_j \in S \setminus a_i$ について $a_j = n * p_i^q$ なら $0 \leq q < e$

が成り立つ。これは $a_i$ がある素数を何個素因数に持つか(入力そのもの)と、素数 $p$ を $a_{1..N}$ はそれぞれ何個素因数に持つか列挙する。素数 $p$ に対する、何個素因数に持つかをソートすれば、先の $0 \leq q < e$ について std::lower_bound(e) が最後の要素か否かで分かる。

$a_{1..N}$ を抜いたら最小公倍数が減るのは何通りあるか $c$ を数える。 $c < N$ なら $c$ 個の最小公倍数と、元の最大公倍数の併せて $c+1$ が答えであり、 $c=N$ なら $c$ が答えなので、 $min(c+1, N)$ が答えである。

コードはこちら

たまには使うスマートポインタ。

カードの山を std::set<Num> で持ち、山の一番の番号をキーとして連想配列に入れる。このとき素のコンテナではなくスマートポインタ経由にすると、山に重ねたカードが変わったとき std::move で移せる。ムーブではなく山をコピーして削除だと時間が掛かるかもしれない(ムーブのコストはplaceholderのポインタだけかもしれないが)。

コードはこちら

遅延セグメント木の出番である。

値が $i$ となる $A_j$ および $B_j$ となる $j$ はどれか、という表を作る。

表を作ったら、 $S=(i)$ から初めて、 $S=(i,i+1,...)$ と尺取り法で伸ばしていくことを考える。0-based indexingで、初期値を $l=0,r=0$ とする。

• 値が $l$ となる $A_j,B_j$ の $j$ を集合 $U$ に入れる。集合 $U$ の要素数で重複は数えない。
• 集合の大きさ $|U| = M$ なら以下の通りにする。
  • 数列 $S=(l, ..., r)$ は長さ $k=r-l+1$ の良い数列である。 $S$ が良い数列なら要素 $A_p,B_p : l < p \leq M$ を追加した集合からもやはり良い数列を作れる。
  • よって $f(r-l+1, ..., M-l)$ に1を追加する。これは遅延セグメント木の区間可算でできる。あるいはセグメント木といもす法でもよい。
  • $l$ を1加えて同様に尺取り法を繰り返す。
• 集合の大きさ $|U| < M$ なら、 $r < M$ の範囲で $r$ に1を加える。

遅延セグメント木の添え字 $i=1..M$ の要素( $[i,i+1)$ の区間和)が、 $f(1..M)$ である。

コードはこちら

二次元DP。

公式解説通り、i回目までコイントスを行い、現在のカウンタがjである、というDPを作ればよい。

コードはこちら

ビット操作は独立。

各桁のビット操作は独立なのでそれぞれ別に考える。操作 $1..N$ は累積できるので、操作を全部読んで累積してから一気に $X$ を求めることができる。 $A_i$ のあるビット $a$ について、操作前のビットが $x$ なら、

• $x XOR a$ は、 $a=0$ なら $x$ のまま (keep)、そうでなければ $x$ のビット反転 (flip)
• $x AND a$ は、 $a=1$ なら $x$ のまま (keep)、そうでなければ0 (reset)
• $x OR a$ は、 $a=0$ なら $x$ のまま (keep)、そうでなければ1 (set)

操作の累積を keep, reset, set, flip に置き換えることができる。

$C$ の各ビットをkeepの初期値として順に操作した結果を出力する。

コードはこちら

セグメント木が二本要る。

$X$ の転倒数を数えるためにセグメント木が一本要る。これは定石通り。問題は色 $C_i$ についてもセグメント木が一本要る。なぜなら転倒を解決するためのバブルソートの最後の一手は、同じ色の球が並ぶのでコストが要らないからだ。

具体的には転倒している要素 $SX_i = {X_{1..{i-1}} > X_i}$ と、転倒して色も同じ要素 $SC_i = {X_{1..{i-1}} > X_i} \land {C_{1..{i-1}} = C_i}$ を数えると、 $|SX_i| - |SC_i|$ が $X_i$ の転倒を解決するコストである。

問題は $SC_i$ を上手く数えないとTLEすることである。 $i=1..N$ について愚直に求めるとセグメント木が多すぎるので、重複を排除した一意な色 $c_1, c_2, ...$ を求め、それぞれの色 $c_i$ に対して位置と値 $(j,X_j)$ の集合を関連付ける。こうしてそれぞれの色に対してセグメント木を使って $|SC_i|$ を求めると、セグメント木の総操作回数は $N$ 回なのでTLEしない。セグメント木の初期化と破棄はかなり時間が掛かるので、一本のセグメント木を使いまわして、加算した要素を減算して空にする必要がある。

要素が上位何番目かを $O(log(N))$ で求め、要素一個を追加するコストが $O(log(N))$ なデータ構造があれば、セグメント木は1本で済みそうである。

コードはこちら

三次元DP。

公式解説通り、先頭j項からk項選んだ総和をiで割った余りremになる、というDPを作ればよい。

コードはこちら

一次元DP。

公式解説通りだが、訓練しないと簡潔なコードを速く短く正確に描けるようにならない。

コードはこちら

一次元DP + 累積和

動的計画法なのだが、マス1からマスNを求めると答えが出ない。マスNからマス1を求めると答えが求まる。

コードはこちら

転倒数。

atcoderが異なる一文字ずつからなるので、a..rの出現順序で転倒数を数えればいい。

コードはこちら

超頂点

クエリを先読みして、最後のクエリから順に電線をつなぐとunion-find木を使える。初期状態でそれぞれの連結成分について、都市がいくつあるか数える。これは atcoder::dsu::groups() で連結成分を一つずつ得て、発電所以外を数える。発電所は同一視できるのですべて一つの頂点にまとめて構わない(これは気が付かなかった)。超頂点を使うコードは こちら

都市に電気が通っているかどうかは、連結成分の都市の数つまり発電所以外の数と、電気が通っているかどうかを、連結成分のleaderに持たせればよい。あとはクエリの逆順に地点を結び、異なる連結成分を結んだら新たな連結成分の都市を数えて、新しいleaderに持たせる。併せて電気が通っている都市を増やす。

• 同一連結成分の地点同士を結んだ場合は、電気が通る都市は増えない
• 電気が通っている都市同士を結んだ場合は、電気が通る都市は増えない
• 電気が通っていない都市同士を結んだ場合は、電気が通る都市は増えない
• 電気が通っている都市と、電気が通っていない都市を結んだ場合、電気が通っていなかった都市の数だけ電気が新たに通る

コードはこちら

累積和があれば部分和は求まる。

あとは、std::lower_bound で探せばよい。

尺取り法を使うと $O(N)$ で求まる。実装は こちら で、 $P,Q,R$ よりも $P,P+Q,P+Q+R$ を管理する方が楽である。

コードはこちら

三次元DP

現在の座標から相対座標 $(A,B)$, $(C,D)$, $(E,F)$ に移動するので、相対座標に移動する方法が何通りあるかを三次元で管理する。障害物がある先には行けないが、障害物を連想配列 std::unordered_set<Num> で管理すると障害物のある座標かどうか分かる。連想配列のキーは $2X \times 10^9+Y$ とする。

$x,y,z$ 座標軸を $i$ 回移動するときの位置は $x=0..i$, $y=0..i-x$, $z=i-x-y$ である。これを $i=0..N$ まで求めればよい。TLEしそうでTLEしない。

コードはこちら

引く二次元DP。

ある時刻 t に 場所 i に居るかでDPする。今 i に居るためには j 時間に居られる(出発しなけばならない)範囲が限られるので、それを基に引くDPすればよい。

コードはこちら

いいところどり

ラウンド1つまり $N=1$ のときの答えは $p=3.5$ である。ラウンド $i$ のときの答えが $p_i$ のとき、サイコロの目 $x$ が $p_i$ 以上つまり $x \in X = {\lceil p_i \rceil .. 6}$ ならそこで終わり(次のラウンド行くと期待値が下がる)、 $p_i$ 未満つまり $x \in {1..6} \setminus X$ なら次のラウンドに行くと期待値が上がる。なのでラウンド $i+1$ の期待値は、 $p_{i+1}=(sum(X) + p_i * (6-|X|))/6.0$ である。これをラウンド $i=1..N$ まで求める。

コードはこちら

環状線と枝線

まず全体が一つの輪、つまり次数が1以下の頂点が存在しないときは答えは No である。輪ならある頂点から別の頂点に行くのに、右回りと左回りの両方があるからだ。

まずunion-find木で連結成分に分解する。連結成分について無向グラフのサイクル検出をする。 こちらの記事 を参考にした。

• 連結成分にサイクルがなければ、連結成分のどの頂点からも別の頂点に行く方法は一意である。この連結成分でunion-find木を再構成する。
• 連結成分にサイクルがあれば、サイクル外からサイクルまで、いわゆる枝線から環状線の各頂点について、ある頂点から別の頂点に行く方法は一意である。つまり枝線(端は環状線の頂点でもよい)を一つの連結成分とするようにunion-find木を再構成する。これは各頂点からBFSすれば求まる。

再構成したunion-find木について、クエリの $(u,v)$ が同じ連結成分なら Yes 、そうでなけば No である。なもりグラフを知らなかったので一般解を出した。

なもりグラフ、つまりサイクルは一つに限り、サイクルから木が生えていることが分かっていれば、サイクルから木をDFSしてそれぞれの木をunion-find木の連結成分にする。実装は こちら

コードはこちら

等比数列の公式っぽい。

等比数列の公式 $$\sum_{i}^{n} a^i = a^{n+1}/(a-1)$$ は、掛けてずらして引くことで得られる。この問題も足して引くことで、Bの始点 $ofs$ をずらしたときの値が求まる。

$$\sum_{i}^{M} i \times B_{i+ofs+1} = \sum_{i}^{M} i \times B_{i+ofs} + M \times B_{M+1} - \sum_{i}^{M} B_{i+ofs}$$

最後の一項は累積和から求まる。

コードはこちら

滑り込みセーフ

3768 msでぎりぎりACしたが、TLE回避の方法が要る。少し工夫しても 2437 ms掛かる。

現時点でコストの最も安い頂点を刈っていく、というgreedyで解ける。なので優先度キューを使って頂点をコストが低い順に並べればいい。頂点を刈るほどコストは低くなり、その結果同じ頂点が優先度キューに何度も載ることがあるが、そのときは一度刈った頂点は二度刈らなければいい。

TLEを回避するには、刈った頂点の隣の頂点のコストを再計算するのではなく、刈った頂点分だけコストを引く、つまり差分更新する。

コードはこちら

ややこしいことは再帰にやらせよう。

文字列の連携をDFSで再帰すれば解けるし、TLEしない。公式解説通り実装を簡潔にしたのが こちら

コードはこちら

あと一歩足りない

$S_i$ に含まれる数字の和 $full(S_i)$ , $S_i$ だけのスコア $part(S_i)$ , $S_i$ に含まれる X の数 $cnt(S_i)$ を測る。これを $(P_1,P_2,...,P_N)$ に上手く並べ替えると、 $T$ のスコアは以下の通りになる。ここで二番目(内側)の $\sum$ は累積和としてあらかじめ求めておく。

$\sum_{i=1..N} (part(S_{P_i}) + cnt(S_{P_i}) \times \sum_{j=(i+1)..N} full(S_{P_j}))$

問題は $(P_1,P_2,...,P_N)$ の作り方である。公式解説にある通り、 $i < j \Leftrightarrow full(P_i)cnt(P_j) < full(P_j)cnt(P_i)$ とする。だいたい思いついたが、整数の式で比較条件にするところまで落とし込めなかった。

コードはこちら

連結成分といえば、union-find。

ということで、マスの連結関係をunion-findに登録すればいい。

コードはこちら

質問回数を固定したらなぜかWAする。

行(y座標)について、 $1..N$ のどれかの行にはルークがないことを二分探索で見つける。ジャッジシステムへの質問としては、列を全幅 $1..N$ として、行の幅を半分ずつ狭めていけばよい。最初は $h=N/2, 1..h$ 行目について質問して、

• $h-1$ 個ルークがあれば、質問した半分のどれかの行にはルークがないのでそこを探し
• そうでなければ残り半分の行の、どれかの行にはルークがないので探す

これを繰り返すと、ルークの無い行を1つに絞り込める。列も同様。

さて質問回数の上限は20回だが、どういうわけか for(Num i{0}; i<10; ++i) {} するとWAし for(;;) {} するとACする。原因が分からないのだが、質問回数の上限を超えたことはジャッジサーバに判断させて(-1が返る)実装しなければいい。

コードはこちら

$X$ から深さ優先探索で $Y$ を求めればよいのだが、単純パスを返り値にすると、返り値のコピーが再帰の深さだけ発生してTLEする。対策として、単純パスをグローバル変数に置くなり、引数の参照に書き込むなりする。

コードはこちら

Min-max戦略である。

残り $i$ 個の石について、最善手を打った時に得られる石の総数を $score(i)$ とする。残り $i$ 個の石について、選択肢 $A_i$ を考える。 $i < A_i$ の手は打てない。 $i \geq A_i$ なら

• 今 $A_i$ 個の石が手に入り、残りは $p = i - A_i$ になる
• 相手が最善を尽くすなら、相手は次の手番で $score(p)$ 個の石を取る
• 合わせて自分が取る石の総数は $A_i + p - score(p)$ 個である

こうして残り $i$ 個の石について、すべての手 $A_{1..K}$ にから最善手 $score(i)$ を選ぶ。あとは $i=1..N$ について順に求める。

コードはこちら

整地

$A_i$ について、同じ数字が何個出るかを昇順にまとめる。つまり $A_i$ を、 $B_1$ が $C_1$ 個、 $B_2$ が $C_2$ 個 ... $B_m$ が $C_m$ 個 とまとめ直す $(\forall i B_i < B_{i+1} , C > 0)$ 。次に $B_i$ 以上の要素が $W_i$ 個ということを、 $i=m..1$ について $C_i$ の累積和を取ることで求める。

こうすると $B_i$ 以上の要素が $W_i$ 個とわかる。これを $i=1..m$ について順にりんごを食べる。要は $B_i$ を下から上に整地する感じである。

• $B_i * W_i$ 個のりんごを食べてもまだ $k$ 個を超えないなら、 $B_i * W_i$ 個食べて $i$ を1増やす
• そうでないなら $B_i * W_i$ 個のりんごを食べている途中に、累計 $k$ 個以上のりんごを食べることになる。 $B_{i-1} * W_{i-1}$ 個まで $c$ 個食べたのなら残り $d = k-c > 0$ 個なので、 $d / W_i$ 個または $1 + d / W_i$ 個食べる。食べている途中に累計 $k$ 個のりんごになるところで止める。

どのかごで食べるのを止めるか考える。 $j=1..N$ について、食べた後に残ったりんご $R_j$ は

• $A_j \leq B_{i-1}$ ならかごにりんごは残らないので0個。
• $A_j > B_{i-1}$ なら
  • $d \quad mod \quad W_i = 0$ なら全部のかごをきっちり食べて、 $A_j - d / W_i$ 個
  • $r = d \quad mod \quad W_i > 0$ なら、 $A_j > B_{i-1}$ となる先頭 $r$ 個は $A_j - d / W_i - 1$ 個、それ以降は $A_j - d / W_i$ 個

$R_j, j=1..N$ を出力する。

公式解説2は優先度キューを用い、りんごが入った個数が同じかごが複数あるなら、2つ目以降のかごは単に無視する。端数処理も上手くやる。解説通りの実装というか変数名以外はほぼコード例そのままなのが こちらである。

コードはこちら

2日掛かって解けた。

如何にもMSTをクラスカル法で解く問題である。空港と港をどうするかが課題だが、空港を建設する/しない、港を建設する/しないの都合4通りを総当たりすればよい。

クラスカル法なので、道路、空港、港を $cost, from, to$ の昇順にソートして、 $from, to$ が連結成分でなければ建設する。ただし空港は $to = -1$ , 港は $to = -2$ という辺を載せる。後で分かるが、実はこれが超頂点だった。

• 道路については、いつものクラスカル法通り、 $from, to$ を未連結なら連結してコストを払う
• 空港については、最初に出現した島を $Xfst$ とし、二番目以降に出現した島について $from, Xfst$ を未連結なら連結してコストを払う。最初の島のコストは、空港を建設した島が2つ以上あれば払う。ただし空港を建設しないと決めたら一切建設しない。
• 港も同様である。空港と港は独立である。

すべての辺を載せて、すべての島が一つの連結成分になったら、そのコストを候補にいれる。そのようなコスト候補の最小値が答えである。すべての島に空港か港を建設するという解があるので、答えは有限である。

公式解説は、最初に空港/港を建設した島ではなく、超頂点を用いている。空港を建設する/しない、港を建設する/しないの都合4通りは、超頂点を島と結ぶかどうかに対応する。超頂点で書きなおすと コード が短くなる。

コードはこちら

C問題としてはかなりややこしい。

1. 重複している巻は、一つを残してすべて売ってよい
2. N巻より先は読めないのですべて売ってよい
3. 持っていない巻のうち最小のものを買う
4. 持っている巻は買わない

重複している巻が1冊または0冊のときの実装が回りくどくなってしまった。公式解説を読んでコードを改善すると こうなる

コードはこちら

部分和である。

$N, a, b$ が小さいので、部分和は1万通りしかなく、したがってある部分和を作る表裏のシーケンスを全部列挙すればよい。

コードはこちら

ある種のDP

$E$ を先頭から見ていって、都市1から到達可能なら最短距離を更新し、そうでなければ到達不能(距離無限大)のままにする。

それだけの話だが、道の長さを std::vector<Num> として道の番号をキーにすべきところを、いつもの癖で std::map<std::pair<Num, Num>, Num> として道の始終端をキーにしたために、始終端が同じ道が複数あるときに上手く答えを求められなかった。

コードはこちら

半分全列挙までは分かったが切り口を間違えた。

左上 $(1,1)$ から到達可能なマス $(i,j)$ に到達可能な全経路で $K$ を取る組み合わせを連想配列 $upper[i,j](K \rightarrow V)$ とする。同様に右下 $(N,N)$ から到達可能なマスについても $lower[i,j](K \rightarrow V)$ とする。両者を突き合わせればよい。突き合わせる場所を行を二分する場所つまり水平線にするとTLEしてしまう。正しくは公式解説通り対角線である。

対角線について $upper[i,i](K \rightarrow V)$ , $lower[i,i](K \rightarrow V)$ が求める。対角線上のマス $(i,i)$ について、ある $K$ について $upperi,i$ は左上 $(1,1)$ から到達可能な組み合わせ、 $lower[i,i](a_{i,i} \oplus K)$ は $(N,N)$ から到達可能な組み合わせの数であり、両者の積を取ると $(1,1)$ から $(i,i)[K]$ を経由して $(N,N)$ に行く組み合わせの数である。これをすべての $i$ のすべての $K$ について合計する。

$(N,N)$ から数えるときは、盤面全体を上下左右に反転させるとコードを共通にできる。

コードはこちら

マスが少ないので網羅する。

400x400マスしかないので、行ける場所を頂点、行く方法を辺で結んだグラフを構築して、最小距離を求めればよい。グラフと同時に最小距離を求める方がおそらく速い。BFSによる実装は こちら

コードはこちら

計算量解析。

素で実装すると計算量が $O(MN)$ になるように見えるが、おそらく計算量 $O(Nlog(N))$ である。

なぜなら毎回の操作で $A_i$ は単調増加すること、鳩の巣定理よりMEXは $0..N$ のどれかにしかなりえないからである。要するに数 $A_i$ については、 $j$ 回目の操作で $0 \leq A_i + i \times j \leq n$ となる $j \in [L,R]$ だけ調べればよく、 $[L,R]$ の幅は $i$ に反比例するのですべての $i$ についての区間長の和は $O(Nlog(N))$ である。

$L = -A_i/j$, $R = (n-A_i)/j$ だが負の除算を整数に丸めるのがめんどくさいので、区間を左右1ずつ広げて $0 \leq A_i + i \times j \leq n$ に収まっていれば $j$ 回目の操作で出現する数と扱うのが簡単である。これをすべての $i$ について求める。

あとはそれぞれの $j$ についてMEXを求めればよい。ソートしたあと、先頭からみて番号が飛んだら(差が1以上開いたら)、飛んだ番号を出力する。初期値を-1としておくと、先頭が0ならMEXは1以上、先頭が1以上ならMEXを0にできる。

コードはこちら

壁の位置を二分探索するのも、番兵を導入して条件分岐を減らすのも、以前見たような気がする。

コードはこちら

バージョン管理システムのブランチと差分更新に言い換える。

• 最初のバージョンは $v=0$ で、中身は空列である
• ADD は、最後のバージョン $v$ にある $A$ の末尾に $x$ を追加し、バージョン $v+1$ を作る
• DELETE は、最後のバージョンに $v$ のある $A$ の末尾を(もしあれば)削除し、バージョン $v+1$ を作る
• SAVE は、最後のバージョンに $v$ と同じ内容をからバージョン $v+1$ を作り、併せてノートにバージョンを書き留め $note[y] = v+1$ とする。バージョンがSubversionてきな連番なら、ノートは(最後のバージョン一つだけ保持する)タグである。
• LOAD は、バージョン $note[y]$ (なければ0) と同じ内容から、バージョン $v+1$ を作る

このようにすると、バージョン $0..Q$ は木構造の有向グラフになり、バージョン間の辺は $A$ の追加、削除、無変更の操作に対応する。これらは対応する逆操作(削除、追加、無変更)がある。よって $Q$ 個のクエリをすべて先読みして木を構成し、バージョン0からDFSすると、各バージョンにある $A$ の末尾(なければ -1 )を得られる。末尾だけ分かればいいので、スタック操作と同様で計算量は $O(Q)$ である。

公式解説2の余談に、今回の操作はGitと書いてあったが、まさに私が思ったことである。

コードはこちら

独立に考えられる変数を分ける。

x座標とy座標は独立なので別々に考える。そうすれば $A_i$ の $i$ が奇数と偶数を独立な問題として考える。 $x$, $y$ が小さいので、 std::set で取りうる部分和を全列挙すればいい(取りうる値の種類が少ないなら std::vector の方が挿入コスト $log(N)$ がないので速い)。

コードはこちら

BitDPでTSP

これは実装例をよく見て解析しないと解けなかった。Greedyっぽい解き方でも入力例だけは解けてしまうがそれでは完答できない。

• 二次元ユークリッド距離は std::hypot で求まる
• ビットを数えるのは __builtin_popcount で求まる。上位ビットだけ取り出すならシフトすればいい。
• 1<<i はオーバーフローが怖いが、この問題ならintに収まるので問題ない。
• 初期値は一手移動した後にする。
• $1..N$ 頂点までを移動したことを、 $1..2^N$ ビットパターンで この順に 処理する。これが分からなかった。こうすれば、初手が頂点 $i$ のとき、頂点 $i$ からの移動先を網羅できる。

解けなかった 180-E から何も学んでいないのは反省。

コードはこちら

再帰の深さを考えてDFSする。

再帰の深さは対数オーダーなので、DFSしてもスタックはあふれない。よってメモ化しながら再帰すると答えが求まる。

コードはこちら

確率シミュレーション

$K$ 手後にそれぞれのマスにいる確率をシミュレーションすると求まる。 $1..K$ 手でゴールした確率を足し、ゴールしたらそれ以上遷移しない。

コードはこちら

左から考える。

$a_0 = 0$ と置く。 $i = 1..N$ について、 $[a_0, ..., a_i]$ から0個以上の数を組として選んで足して、 $0 \leq S \leq M$ 以下になるかどうか確かめる。ならないなら無視し、なるならそのような組のうち、操作が最小になる組を選ぶ。これを $i=1..N$ について動的計画法で求める。

• 操作数 $counts[0..M]$ , 最後の操作 $lefts[0..M]$ をDPする。 $counts[] = undef, counts[0] = 0, lefts[] = - \infty, lefts[0] = 0$ とする。
• 前の状態 $from = 0..M$ から、和 $to = from + a_i \leq M$ に移る。ただし $counts[from] = undef$ または $to > M$ の場合は移れない。さらに、 $lefts$ の隣が $i$ なら( $lefts[from] + 1 = i$ なら)操作回数は増えず、そうでなければ操作回数が1回増える。
• よって $counts[to] = min(counts[to], counts[from] + (lefts[from] + 1 < i))$ である。 $lefts[to]$ は $to,from$ のうち $min$ で選んだ方の添え字である。

これを繰り返すと、 $counts[1..M]$ が求まる。さらに $counts[1..M]$ について、操作で右端 $[..N]$ を消去した場合、つまり $left[i] + 1 < N$ なら操作回数を1足す。

コードはこちら

最大公約数。

• 2と3で割り切ったあと残った数(1でもよい)。残った数が不一致なら -1 。
• すべての $a_i$ を2と3で割れる最小回数(0回でもいい)

である。

コードはこちら

周回ではなく、周回寸前を考える。

始点から上下左右に一手進み、始点の隣まで戻ってくる経路があるかどうか考えればいい。始点の一手先以外で、始点に隣接するマスに戻ってこれれば題意を満たす。始点から一手進む方法は上下左右の4通りなので総当たりすればいい。実装は こちら。

BFSで実装したが、始点からの経路長を測ったらとても長いコードになった。題意を満たすなら経路長は必ず4以上になるので、経路長を測る必要はなかった。公式解説によれば、union-find木を使って到達可能かどうかだけ判断すれば、もっと短い コード になる。センチネルつまり盤面を障害物で囲っておくと端の座標の扱いが楽になる。

コードはこちら

セグメント木が二本要る。

登場する物が多いので整理する。

• $A_{1..N}$ を昇順に並べた時の順位を $order_{1..N}$ とする。同じ値については $A$ の添え字順にする。
• $A_{1..N}$ を昇順に並べ替えたものを $B_{1..N}$ とする。上記より、 $B_{1..N}$ に対応する $order_{1..N}$ は $1..N$ である。
• $i={1..N}$ について、 $B_i \times (2i-1)$ を順にセグメント木 $values$ に載せる。係数の意味は後述する。
• $i={1..N}$ について、 $1$ を順にセグメント木 $exists$ に載せる。これは $values$ に値が載っているという意味である。

$B_{1..i} \times (2i-1)$ は、 $K=N$ のときに小さい方から $i$ 番目の値が $max(x,y)$ になるのは $(2i-1)$ 通りであることを示す。期待値を求めるための分子 $s$ として、 $B_i$ に取りうる組み合わせを掛けたものを全部足す。分母は後で考える。

こうすると $K=N$ のときに $values.prod(1,N) / N^2$ が、つまりセグメント木の $[1,N]$ (1とNの両方を含む) の和を $(x,y)$ の組み合わせで割ったものが期待値だと分かる。ここから $K$ を減らしていく。

ある $K$ のときに、 $p = order_K$ なら $p$ 番目の要素を抜けばよい。ある時点で、下から $p$ 番目の値が $max(x,y)$ になるのは $(2p-1)$ 通りである。よって以下の通り分子 $s$ を減らす。

• $p$ 番目より大きい要素 $values.prod(p+1,N)$ を抜く。 $p$ を抜くとこの値の2倍分子が減る。これは累積和の差分を取る感じである。
• $p$ 番目ちょうどの要素 $values.get(p)$ を抜く。 $p$ を抜くとこの値の $exists.prod(1,p-1)$ 倍、つまり $A_K$ より小さい値の数を掛けた分だけ、分子が減る。
• $values.set(p,0)$ , $exists.set(p,0)$ して、 $A_{K}$ をなかったことにする。

これを $K=N..1$ について繰り返すと、それぞれの分子 $S_K$ が求まる。これらをそれぞれ分母 $N^2, (N-1)^2 .. 1$ で割って逆順に出力すると答えである。公式解法は $K=1..N$ だが実質的は同じだと思う。

遅延セグメント木でも 解ける 。

コードはこちら

余りが滑っていくのは何度目かである。

mod M が連続する(Nは0にループする)ならテーブルに置けるので、そのような run を求める。Run以外のカードの総数が手札に残るので、その総和を求める。コードをきれいにしたものが こちら

コードはこちら

BFSはキューの先頭に追加することがある。

頂点までの距離をBFSで求めればいいが、スイッチを奇数回押したか偶数回押したかで、頂点までの距離を二通り持てばいい。求めるのは移動した回数なので、頂点間の状態遷移に対して移動は距離1、スイッチを押すのは距離0を加える。最終的に頂点Nの二通りの距離の短い方を答えればよい。

自分の実装が2 WAs, 1 TLEなので公式解説を読んで実装し直したら1 TLEした。BFSは一般に後で訪ねる頂点をキューの末尾に加えるが、ここではスイッチを押してときの距離0で遷移した先の頂点をキューの先頭に加えなければならない。

コードはこちら

キャッシュの無効化またはバージョン管理を思い出す。

クエリ1は、既に数列にある要素を無効化して $x_q$ で上書きすると考える。以後 $x_i$ の読み書きで、要素が無効化されたら $x_q$ を使い、そうでなければ $x_i$ を使う。

コードはこちら

エレガントな解法がいくつがあるが、愚直に解ける。

左上だけ塗りつぶした状態を初期状態として、ある数字 $A$ が何個見えるか数える。塗りつぶし長方形を右にずらしていくと、さっきまで隠れていたマスと今隠したマスについて、ある数字 $A$ が何個見えるか更新する。右端まで行ったら下にずらしていく。

std::map::size() はキーの数を返すので、見える数字の数である。 $A$ が0個あるときは、std::map::erase(A) でキーごと削除すると数えずに済む。コードをきれいにしたものが こちら

コードはこちら

ゲーム木

相手を負かす最善手が一つでもあれば勝ち、一つもなければ負け、という決定木をDFSすればいい。公式解法ではDPと書いてあるが、実質的には同じである。

これだけだと 99_after_contest.txt だけTLEする。ある文字 c で始まり c で終わる文字列が2個あったらループするだけで先手後手の条件は変わらないのでまとめて削除する。

ゲーム木全体の先手必勝/後手必勝と、サブゲーム木の先手必勝/後手必勝がごっちゃになるので、整理したコードがこちら

コードはこちら

実数関数は素直に探索すればよい。

下に凸である、つまり微分が常に正であることは分かるので、三分探索で求まる。

コードはこちら

蟻本らしい

もしあみだくじを一本抜いたら、そこで入れ違うはずのものが行きつく先に行くはずだったと言える。なのでそのことを記録しつつあみだくじを $k=1..M$ 本シミュレートする。

• 初期状態は $B_1=1, B_2=2, ..., B_N=N$
• $k$ 本目を抜いたとき
  • $B_{A_k} = 1$ なら $B_{A_k+1}$ に行くはずと $X_k$ に記録する
  • $B_{A_k+1} = 1$ なら $B_{A_k}$ に行くはずと $X_k$ に記録する
  • どちらでもなければそのままなので $X_k=0$ と記録する
• ふつうのあみだくじと同じく、 $swap(B_{A_k}, B_{A_{k+1}})$ する。

あみだくじの最終状態において $1..N$ 番目は $B_{i..N}$ なのでここから最初の $i=1..N$ は $To_{1..N}$ に行くという逆引きの表を作る。そうすればあみだ $j=1..M$ を抜いたときの答えは $To_{X_j}$ である。

コードはこちら

ADT(2024/5/14 17:30 start)で初めて見たので、解いたことないなと思いつつ取り組んだら20分46秒で解けてしまった。青diffをこの時間で解けたのはおそらく初めてではないか。

マージテクとunion-find木の合わせ技である。

クエリ1はマージテクで集合を合併する。集合そのものの合併 $std::set$ と、Union-find木の合併の両方を行う。

• $Y$ が空なら何もしない
• $X$ が空なら $Y$ と交換する。 std::swap を使うと高速に交換できる。
• $X,Y$ とも空ではなく、 $|X| \geq |Y|$ なら $Y$ の中身を $X$ にマージして、 $Y$ を空にする
• $X,Y$ とも空ではなく、 $|X| < |Y|$ なら $X$ の中身を $Y$ にマージして、 $X,Y$ を交換して、 $Y$ を空にする

この後 $X$ に入ったボールの、union-find木の代表元 $U$ について、ボール $U$ から箱 $X$ への表を更新する。

クエリ2は $k$ を箱 $X$ に マージしてから $k$ をインクリメントする。 $X$ が空のときに注意する。Union-find木は高々 $N+Q$ 要素あればよい。

クエリ3はボール $X$ から箱 $B$ への表を引いて $B$ を答える。

Union-find木だけあれば集合そのものの合併は要らないことに後から気が付いた。改良版は こちら 。

コードはこちら

解析的に求められるようだが、迷ったら決め打ちする。

$K$ の素因数を求める。 $K$ が素因数 $p$ を $i$ 個含むとして、 $n$ を決め打ちして $n$ 以下の数を $p$ で割り切れる合計回数が $i$ になる $n$ を二分探索する。この合計回数は、ルジャンドルの定理 $\lfloor 1/p \rfloor + \lfloor 1/p^2 \rfloor ...$ で求まる。このような $n$ の最大値が、求める $k$ である。

コードはこちら

期待値の加法性による漸化式

なのだが式の意味を理解できないままACできてごめんなさいという気持ちである。

実質的には公式解法2を私が配るDPで実装したものである。要するにダメージを与えるための攻撃回数の期待値をDPで求める。公式解説通り引くDPなら以下の通りである。

$dp[i+2] = dp[i] \times (1-p) + dp[i-2] \times p + 1$

$P=0$ なら答えは $N$ 、 $P=100$ なら答えは $\lceil N/2 \rceil$ を特別扱いすると コード が見やすくなる。引くDPなら こちら の通り簡潔である。

コードはこちら

三次元DP。

余りで分類するのも定番である。i個目までからj個目まで選んで、総和の余りがremになるような組の総和を更新する。

コードはこちら

復活者セット

ある集合の下位 $K$ 番目まで取るには、 std::set の要素を $K$ 個以下に限定すればよい。順番を含めて、 $i$ 番目の要素が $A_i$ だったときに、集合に $(A_i, -i)$ を入れる。

std::set::rbegin は空でなければ最大の要素を指す。最大の $A$ となる要素が複数あれば添え字が最初の要素を指す。ここから集合の要素を下位から $K$ 番目まで、同じ値の要素はできるだけ添え字が小さい物に限定することができる。

さてスライディングウィンドウ $[L,R] = {A_L, ..., A_R }$ を取るときに、始点をスライドさせると要素が復活することがあるのを再現する。入力例1では、 ${3,1,4,1}$ から下位3個 ${3,1,1}$ 選ぶのだが、始点をスライドさせると、 ${1,4,1,5}$ から下位3個 ${1,4,1}$ を選ぶ。このとき $3$ を捨てて $4$ を復活させたい。

そこで直近の下位 $K$ 個の数の集合 $S$ と、後で復活させたい数の集合 $U$ を両方持つ。 $i \leq 1$ からスライドさせていくとき、

• $i - m \leq 1$ なら $S$ に $i - m \leq 1$ 番目の要素があれば捨てる
• このとき $S$ の合計も更新する
• さらに $U$ の最小値かつ添え字が $i - m$ より大きいものを選ぶ。ここで添え字が $i - m$ 以下の要素を見つけたら $U$ から捨てないとTLEする。

$A_i$ を加えるかどうか考える。

• $|S| < K$ なら必ず $S$ に $A_i$ を加える
• $|S| = K$ なら $S$ の最大要素を $U$ に移動する。このとき $S$ の合計も更新する。

後は $i \leq m$ について $S$ の合計を出力する。

コードはこちら

たまには使うスマートポインタ

$a$ を二進数表現したビット $i=31..0$ を、木構造の分岐で表現する。例えば十進数で12を32ビットのビット列で上限すると $0...01100$ であり、LSBを0として4ビット目から3ビット目の遷移は1、3ビット目から2ビット目の遷移は1、それ以外に $i$ ビット目から $i-1$ ビット目への遷移は0である。これを $a_1 ... a_N$ について木構造に載せる。

$i=31..0$ ビット目について、どのようにするのが $M$ を最適にするか考える。ビット $i$ に $d \in {0,1}$ で分岐したときの $M$ を $M_{i,d}$ とする。

• $i$ ビット目について、木構造の分岐が0のみであれば、 $x$ のビット $i$ を0に固定して $M$ のビット $i$ を0にできる。0に分岐して $M_{i-1,0}$ を求め、 $M_i = M_{i-1,0}$ である。
• $i$ ビット目について、木構造の分岐が1のみであれば、 $x$ のビット $i$ を1に固定して $M$ のビット $i$ を0にできる。1に分岐して $M_{i-1,1}$ の最小値を求め、 $M_i = M_{i-1,1}$ である。
• そうでなければ $M$ のビット $i$ は0または1の両方を取りうるので、 $M$ の最大値という観点からは $M$ のビットの $i$ が立っていると考えてよい。その前提で、 $i-1$ ビット目について0にした場合と1にした場合の $M$ の最小値を選ぶ。このとき $M_i = min(M_{i-1,0}, M_{i-1,1}) + 2^i$ である。
• $i < 0$ ビット目は $M = 0$ と考える

これを再帰すれば、 $M$ の最小値が求まる。木構造の分岐は最大 $N$ 回である。

コードはこちら

二部グラフでないグラフに、余計な辺を足しても二部グラフではない。

連結成分分解は例によってunion-find木である。二部グラフかどうかは、連結成分をBFSで実際に彩色すれば分かる。彩色できないなら辺を足してもやはり二部グラフではない。

よって題意を満たすもの個数は、すべての頂点の組み合わせの数から、すでに連結されている頂点間と、二部グラフの同じ色同士を結ぶ辺を除く。実装をまとめると このよう になる。

コードはこちら

AtCoder Daily Training HARD 2023/11/28 15:30 start のバーチャルコンテストで出題された。基本的な解法を思いついたが、いろいろ間違えて自力ではACできなかった。

• フェイズ1で $N$ より大きな数を出すと、WAではなくTLEする。これが分からなかった。
• 公式解説2の方法を取るときは、 $L$ の最小値を1にするか0にするか決めないといけない。0にすると区間をまたぐかどうかの判定で、右区間の始まりを $2^i$ にできて便利である。

公式解説1はsparse tableを用いて区間の並べ方が異なるが、実質的には同じである。実装は こちら 。

コードはこちら

括弧と言えば、プッシュダウンオートマトンとスタックである。

括弧と併せて、括弧間のボールをスタックに積めば、スタックから括弧を取り出した時に開き括弧と閉じ括弧に対応するボールも取り出せる。

コードはこちら

三乗根なので $10^6$ あればよさそうである。探索範囲を相補的にしないとTLEする。

$p < q$ なら $q$ が大きいので素数判定に持ち込むと言いたいが、そうすると $q \leq 10^9$ の探索が必要になりTLEする。なの $q$ を小さい順に調べる。

• $q \leq 10^6$ を決め打ちして求まる $p$ は、 $p$ が整数かどうか調べれば分かる
• $q > 10^6$ なら $p < 10^6$ なので、 $p \leq 10^6$ を決め打ちして求める $q$ は $q$ が整数かどうか調べれば分かる
• 両者で求まる $p, q$ が重なっていても(不等号を雑に組むとそうなる)、重複を後から除けばいい

公式解説はもっと体系的である。

コードはこちら

簡単な問題だと思ったら、問題文をよく読む。

単純パス数の合計は、DFSで同じ点を二度辿らないパスを数え上げれば求まる。長さ0のパスも数えるので、ある点に到達したらパスを1つ増やし、そこから先に到達可能なパスの数を加えればいい。各頂点の次数は10以下、というのはDFSの実装上特に使い道は無い(全探索しても計算量が少ないということらしい)。

解答は最大1000000なので、途中でパス数の合計が1000000以上になったら探索を打ち切る。打ち切らないとTLEする。

コードはこちら

ローリングハッシュは結合できる。

文字列の正順と逆順についてローリングハッシュを求める。

逆順の $[N-i..2N-i-1]$ からなる文字列と、正順の $[1..i], [N-i+1..2N]$ からなる文字列をローリングハッシュで比較する。前者はそのまま、後者はローリングハッシュを結合することで得られる。当然のこととして、ローリングハッシュの実装は正しいこと、区間は0始まりか1始まりか、left, rightを含むのか含まないのか確認する。

後は先頭から $i=1..N$ まで総当たりしてハッシュが一致したら答え、一致するものがなかったら -1 である。

コードはこちら

可能かどうか判断するだけなら、手順を求める必要はない。

名前の変更関係に循環参照がなければ、依存関係の連鎖の先にある物から順に処理すればよい。なのでサイクルがあるか調べるだけでいい。Union-findが簡単で、SCCを使うともっと 簡単 である。

コードはこちら

一般性を失わない

一週間が $0..N-1$ 日目から成るとして、先頭 $0$ 日目を休日として一般性を失わない。なので残りの日を休日にするかどうかをDPで求める。

$1 \leq i \leq n$ 日目を休日にするかどうかをDPする。これは $1 \leq j < i$ 日目が休日なら、 $(j,i)$ 日目の生産量で決まる。これは $i,j$ ではなく $j-i$ で決まる定数なのであらかじめ求めておく(そうしないとTLEする)。

答えは $dp[n]$ である。

コードはこちら

入力の範囲をよく確かめる。

ちょうど $X$ 払う方法を求めるのは難しいが、金額が 5000 までしかないのだから 1..5000円 払えるかどうか部分和を求めればよい。

コードはこちら

ワーシャルフロイド法ではある。

のだが、お土産の価値が難しい。ワーシャルフロイド法の更新式で、

• 距離が短くなるなら、経由してお土産を買う。距離も短くなる。
• 距離が同じなら、経由してお土産を買う。距離は変わらない。

のは思いつく。問題はこうなるように暫定的なお土産の合計価値を表現することで

• 初期状態は、到着地のお土産の価値にする
• 答えを出力する時点で、出発地のお土産の価値を足す

のが思いつかない。

コードはこちら

公式解説通り、中国剰余定理の練習である。

互いに疎な除数 $(m_1, m_2, ... , m_k)$ を用意して、 $N$ をこれらで割った余り $(r_1, r_2, ... , r_k)$ が返ってくれば、 $A,B$ から中国剰余定理で $N$ を推定できる。

$(A_1, A_2, ... , A_M)$ の作り方を決める。ある除数 $m$ について増分しつつ巡回したグラフ $p+1, p+2, ... , p+m-1, p$ を作る。そうすれば $A_i=p$ が $B_i=p+j$ になったとき、$N$ を $m$ で割った余りは $0 \leq i < m$ だったと言える。グラフの頂点数は $(m_1, m_2, ... , m_k)$ なので、それぞれのグラフの頂点番号を $((2,3,...m_1,1),(m_{1}+2,m_{1}+3,...,m_{1}+m_{2},m_{1}+1),(m_{1}+m_{2}+2,...),...)$ と連番にする。

最後に $(m_1, m_2, ... , m_k)$ の作り方を考える。素数のべき乗にすれば互いに素になるが、掛けると $10^{9}$ 以上、足して110以下という制約が少しややこしい。 $2^{2}, 3^{2}, 5, 7, 11, 13, 17, 19, 23$ にすればよい。

コードはこちら

一致関係は単調減少。

マッチする文字列にマッチしない文字の組を加えたら、マッチしない文字列になる。よって文字の組を加えていけば、文字列がマッチするかどうかは逐次的に分かる。

コードはこちら

辞書順で比較する。

先頭がほぼ一致する文字列は、文字列を辞書順で比較するとみつかる。例えば ab < abc < abd になる(公式解説の二番目に説明がある)。ターゲット $S_i$ についてソート順で前後の文字列に対するLCPを求めて、どちらか大きい方のLCPが答えである。

計算量が問題になる。N個の文字列について for(i in 1:N) でLCPを求めるとTLEする。なので

• {str, index} をソートして、文字列が何番目だったか保持した状態で文字列をソートし
• ソートした文字列の先頭から順番にLCPを求めて
• 各 index についてLCPを記録する

とTLEせず答えが求まる。というのが分からなかった。最初と最後の文字列に気を付けて実装すると こちら

もう一つの方法は、Trie木で決まり字を作ることである。決まり字の木構造において、葉に最も近い分岐点または、葉に最も近い $S$ が載るノードがLCPである。すべての $S$ から木構造を作り、根から葉に向かってDFSすればよい。葉は必ず $S$ のどれかで、葉以外のノードに $S$ が載っていたら併せてLCPを求める。なお同じ値の $S$ が二個以上あれば、 $S$ 自身がLCPである。実装は こちら 。

コードはこちら

不変量に注目する。

$A_i$ に $c$ を足すと、 $i : mod : K=0..{K-1}$ を一斉に $c$ 足し引きする。よって $i : mod : K$ の $i$ ごとの累積和が等しければ適切な $c$ を選んで $A$ をすべて0にでき、そうでなければ0にならない成分が残る。

コードはこちら

一次元DP。

到達可能かどうかだけ伝搬すればよい。

コードはこちら

辺が少ない

ので二人の位置 $N^2$ 通りの状態を状態遷移グラフで結んでBFSすればよい。 $N$ 頂点 $2^N$ 状態あるとき $N=10$ なら同様の問題で解けることが分かるのだが、この問題も計算量を見極めると同じように解ける。ということを解説を読むまで分からなかった。

コードはこちら

余りで分類する。

$N$ と $D$ の最小公倍数を周期として印をつける。 $K$ を $LCM(N,D)$ で割った余りだけ進んだところに $LCM(N,D)$ 回の印がつく。

コードはこちら

累積寄与度。

ある二か所の文字の組が、何個の回文に含まれるかという累積寄与度を考える。

まず回文にするために変更する必要のある要素の組について、組の数の最大値を求める。 $1 &lt; i \leq N$ 文字の連続部分列については、 $N+1-i$ 種類の部分文字列それぞれに $\lfloor i/2 \rfloor$ 組ある。これをすべての $i$ について足す。

同じ要素が二つあれば変更不要なのでそのような組と、組が何個の回文に寄与するか数える。ある要素 $A$ が $P={P_1, P_2, ..., P_k}$ 番目に出現するとおく( $P$ は昇順で0-based indexing)。要素 $A$ が両端になる部分列を左右にどれだけ広げられるかが寄与数なので、左余白 $1+P_1$ 、右余白 $1+n-P_k$ のどちらか少ない方 $1 + min(P_1, n-P_k)$ が寄与数と解る。

左余白の方が小さいとして、何個の回文に寄与するかは、位置 $P_1$ と要素が同じ他の位置すべてについて数えて $(1+P_1)(|P|-1)$ 個である。右余白の方が小さいときも同様である。余白の小さい方について求めたので $P$ から削除し、残りの要素 $P$ について同様に寄与度を数える。これを $|P|&gt;1$ の間繰り返す。尺取り法なので合計計算回数は $O(N)$ であり、 $P$ の総当たりにはならない。これが解説無しでは分からなかった。

最後に、回文にするために変更する必要のある要素の組の最大値から、変更しなくてよい組の数を引くと答えが求まる。

コードはこちら

一次元DP。

隣のカードと同じものを選ぶことがあるのかないのかだけで、表のみ、裏のみ、表裏両方のどれにするか決まる。これを基に取りうる組み合わせ数をDPで伝搬する。

コードはこちら

トポロジカルソート。

トポロジカルソート可能であり、かつ次に選ぶ頂点が一意(out degreeが1以下)なら題意を満たす。

コードはこちら

前後からたどる

スタート(都市1)から各都市と、ゴール(都市N)から各都市への最短距離はDPで求まる。よって都市 $k$ をテレポーター1回でまたぐような組を $M$ 回総当たりすればよい。

コードはこちら

Union-find木。

連結成分の代表ノードが分かれば、そこに属している頂点と辺が分かる。

コードはこちら

再帰的

解説無しでは解けなかった。ある頂点から到達可能な頂点にはすべて辺が張られる。

コードはこちら

三分探索

正三角形が長方形に接しているとして、角度を変えれば最大値が分かる。長方形を縦長(もしくは横長)に固定するとか、短い方の長さは単位1に固定するとか、角度は60度までとか工夫する。

コードはこちら

次数に注意する。

連結成分分解して、ループならすべての頂点の次数が2なので分かる。次数1が見つかればループではない。初見で解けなかったので実装したものが こちら

コードはこちら

漸化式を行列表現してダブリングすると解ける。もう一つの方法は、 __int128 を用いて $\sum_{i=0}^{X-1}{A_i}=(A^X-1)/(A-1)$ を求めることである。コードは こちら

• $A-1$ のときはこの式は使えないので特別扱いする
• $A^X \quad mod \quad M \equiv 0$ のときは分子が負にならないようにする

最後に $M$ と素とは限らない $A-1$ で除算するために、ダブリングを $mod \quad M(A-1)$ で行う。

static_cast<Num>(((sum_a + nm * (a - 1)  - 1) / (a - 1)) % nm)

コードはこちら

解説無しでは解けなかった。 ${(10^{18})}^{1/4} &lt; 32000$ より、基数(base)が大きいときと小さい時で方法を使い分けると総当たりできる。

• 2進数, $b$ 進数、 $b-1$ 進数は明らかに該当する。重複して数えないよう注意する。
• 2桁については、 $b$ 進法で0または1だけの桁から成る数つまり $10, 11$ を総当たりして、いずれで表現できるかどうか調べる。基数はだいたい $b$ の2乗根付近なので総当たりで調べる。よく考えたら $11$ は $b-1$ 進数だった。
• 3桁についても同様に、 $b$ 進法で0または1だけの桁から成る数つまり $100, 101, 110, 1111$ を総当たりして、いずれで表現できるかどうか調べる。基数はだいたい $b$ の3乗根付近なので総当たりで調べる。
• 4桁以上については $b=2..32000$ について、0または1だけの桁で表現できるかどうか調べる。 $b$ 進法表記を実際に作れば分かる。

コードはこちら

std::setは便利。

優先度がある集合(std::priority_queue, std::set)で管理する。線形時間でも解けるらしい。

コードはこちら

めったにないE問題茶diffである。

余りにむかし解いたので忘れていた。尺取り法で解ける。きれいに書き直すと このよう になる。

コードはこちら

少しきれいにしたコードが こちら 。随分前に解いたのだが、要するに二分探索問題に置き換えると解ける。

濃度には加法性が成り立たない、つまり $a/(a+b)+c/(c+d)=ac/(a+b+c+d)$ にはならないので、 $a/(a+b)$ を固定して $c/(c+d)$ の昇順に加えた $(a*c)/(a+b+c+d)$ は昇順とは限らない。高橋君の片方の砂糖水を固定して青木君の砂糖水を足した時の濃度がどうなるかは都度計算して並びかえる。

コードはこちら

オイラーツアーとセグメント木で解ける。

コードはこちら

偶奇に注目する。

嬉しい列=出現回数が偶数である。数字は10通り、数字の出現回数が奇数か偶数は $2^{10}$ 通りの状態なので、状態が一致する組み合わせを数えればいい。公式解説通り、もっと簡潔に 実装 できる。

コードはこちら

割り切れなければ、割り切れるまで足せばいい。

$M$ を $a$ で割った余りrについて、 $M$ に $r-a$ だけ余分に足せばaの倍数になる。 $a \leq b$ とおいて、 $a \leq \sqrt{M}$ について総当たりすれば求まる。

コードはこちら

難しく考えすぎない。

サイクルをいい感じに回り続けることが可能かどうか考える。サイクルに至る枝は一切関係ない。

• $i$ がサイクルにあるなら、高橋君はサイクル上の適切な始点からサイクルを回り続けて $i$ に達することができる。青木君が $K_i$ に何を選ぼうがこれを止めることはできない。
• $i$ がサイクル外にあるなら、青木君はサイクルに達する十分大きな $K_i$ を指定してというか $K_i=N$ にすれば、高橋君はサイクルに入り、サイクル外の $i$ で止まることはできない。

サイクルは一つとは限らないので、連結成分分解してそれぞれの有効グラフについてサイクルを求める。サイクルの頂点数の総和が、高橋君が勝つ回数である。

強連結成分分解(SCC: Strongly Connected Component)を使うと簡潔に 実装 できる。以下のように行う。

• 自己ループはサイクルにあるとみなす
• 強連結成分分解した頂点群で、要素数が1のものはサイクルではない(ただし自己ループは上記の通り)。要素数が2以上ならサイクルである。

コードはこちら

ユークリッドの互除法である。

ユークリッドの互除法で何回割ったかを数える。

コードはこちら

std::set と std::priority_queue の使いどころである。

まず何も買わない=合計0円を初期状態とする。この状態からたこ焼きを1個買ったときの合計金額を、N種類に対して求める。求めた合計金額に対して、やはり追加のたこ焼きを1個買ったときの合計金額を求める、というのを繰り返す。合計金額をソート済の状態で管理して、K+1個(合計0円があるので)以上求まったら繰り返すのを止める。

• 合計金額を最低額から並べたものを std::set で管理する。合計金額が同じたこ焼きの組み合わせは1種類、というのを都合よく扱える。
• たこ焼きを1種類買う前の金額は std::priority_queue に出し入れして管理する
• std::priority_queue から取り出した金額を std::set に挿入する
• たこ焼きを1種類買った後の金額を std::priority_queue に出し入れして管理する。ただし std::set にすでにある金額は無視する。
• たこ焼きを1種類買った後の金額が最低金額から K+1 種類求まっている条件は、 std::set の要素数がK+1以上かつ、たこ焼きを1種類買った後の金額がすべて std::set の最大金額を超えた時である。このときは std::set の小さい方から数えてK+1番目の要素が更新されることは最早ないからである。

上記の更新を打ち切ったら std::set を先頭からみて、K+1の要素を出力する。

コードはこちら

mod M 演算を行う。

Qの大きさから、 $10^{6000001} ; mod ; 998244353$ を求めておく。

• クエリ1は、 $S$ を10倍して $x$ 足してから mod
• クエリ2は、 先頭の数字 * 10の桁数乗 を引いてから mod
• クエリ3は、 mod で管理している $S$ を出力する

コードはこちら

確率シミュレーション再び

ABC 275-Eとほとんど同じである。違いは、先手がゴールにたどり着ける確率に、後手が (1-既にゴールしている確率) を掛けることである。今回は引くDPにした。

コードはこちら

実は鳩の巣原理

まずすべての非0のマスについて答えを求める。行の総和+列の総和-マスの値について最大値を求める。

次に、行の総和が最大の行(複数あるかもしれない)と、列の総和が最大の列(複数あるかもしれない)の組み合わせを全探索する。何を全探索するかと言えば、行と列の交点に0のマスがあるかどうかである。そのままだと $O(N^2)$ 組を探してTLEするが、非0のマスは $N$ 個しかないので、 $N+1$ 個探索すれば交点に0のマスがあるなら必ず見つけられる。見つけたら探索を打ち切ればTLEしない。

交点に0のマスがあるなら行の総和+列の総和が答え、なければ最初に求めた行の総和+列の総和-マスの値について最大値が答えである。余分な処理を省いて簡潔にしたのが こちら

コードはこちら

二分探索である。

答えに従って解の候補を半分に絞れば、20回で解が一意になるはずである。中点についてジャッジに質問して、

• ジャッジが0を返したら後半に変化点がある。前半は全部0かもしれないが、後半には0から1に変わる場所が少なくとも一か所ある。
• ジャッジが1を返したら後半に変化点がある。後半は全部1かもしれないが、前半には0から1に変わる場所が少なくとも一か所ある。

コードはこちら

std::optional

頂点の色が白/黒/分からないというのを、 std::vector<std::optional<bool>> で管理する。

各頂点から他の頂点への距離をBFSで求める。 $N$ が少ないので総当たりで間に合う。次に頂点 $p_i$ から距離 $d_i$ 未満の頂点を白く塗る。このとき $d_i&gt;0$ なら $p_i$ 自身を含む。

その後、次に頂点 $p_i$ から距離 $d_i$ の頂点を一つ以上黒く塗れるかどうか調べる。言い換えれば、白く塗っていない頂点が一つ以上あることを意味する。塗れなければ解なしなので No と出力して終わる。塗れるなら特に何もせず続ける。

こうすると白く塗らなければならない頂点と、白く塗る必要がない頂点が分かる。すべて白く塗る、言い換えれば白く塗る必要がない頂点がなければ No と出力する。そうでなければ白く塗らなければならない頂点を 0 、白く塗る必要がない頂点を 1 として出力する。

コードはこちら

累乗の問題は、探索範囲の絞り方が課題である。

$a &lt; b &lt; c$ から、おおよそ $a &lt; 10^{12/4} = 1000$ と解る。なので全探索二重ループと二分探索 $1000^2 \times log_2(1000)$ 回が計算量として容認されるだろう。素数はまばらなので、実際にはもっとループ回数は少ない。いつ探索を打ち切るかが問題である。

• 素数 $a$ を $a^5 \leq N$ まで全探索する
• 素数 $b (&gt; a)$ を $a^2 \times b^3 \leq N$ まで全探索する
• 素数 $c$ の下限と上限を二分探索する。下限は $b+1$ 、上限は $n / (a \times a \times b)$

素数そのものを探索するより、何番目に小さい素数かインデックスを std::upper_bound で求める方が簡単である。 $a,b$ ではなく $a,c$ をについて全探索してもよい(解説より)。別の解説では累積和を用いて、整数 $N$ 以下の素数の数を求めている。

公式解説にある通り、 $c$ を全探索してもC++ならTLEしない。実装は こちら

コードはこちら

三次元DP

$N=2^X3^Y5^Z$ で表現できない数、つまり2,3,5以外の素因数を持つときは $N$ にはたどり着けないので確率0である。そうでなければ、このような $X,Y,Z$ になる確率が答えである。

三次元DPをボトムアップに求めるなら、 $dp[0][0][0]=1$ として、 $dp[0][0][0]..dp[i][i][i]$ から $dp[0][0][0]..dp[i+1][i+1][i+1]$ まで求まっている範囲を膨らませる方法を考える。

1. $x$ を膨らませて、 $dp[i+1][0..i][0..i]$ を作る
2. $y$ を膨らませて、 $dp[0..i+1][i+1][0..i]$ を作る
3. $z$ を膨らませて、 $dp[0..i+1][0..i+1][i+1]$ を作る

とすると、 $2^x3^y5^z$ に行く確率から別の数に行く確率を引くDPで求めることができる。上記の順番にすればループは発生しない。サイコロの1の目は何もしないのと同じなので、2..6がそれぞれ1/5の確率で出るサイコロを考える。確率を引くDPで集めることができる(添え字が0未満のときは確率0とする)。

• 目が2: $2^{x-1}3^y5^z$ から $2^x3^y5^z$
• 目が3: $2^{x}3^{y-1}5^z$ から $2^x3^y5^z$
• 目が4: $2^{x-2}3^y5^z$ から $2^x3^y5^z$
• 目が5: $2^x3^y5^{z-1}$ から $2^x3^y5^z$
• 目が6: $2^{x-1}3^{y-1}5^z$ から $2^x3^y5^z$

十分大きな $i$ まで繰り返せば $dp[X][Y][X]$ が答えとして求まる。

公式解説はメモ化再帰を使ったはるかに簡潔なコードである。実装すると こちら