2019-07-13

Codeforces Round #573 (Div. 1) C. Tokitsukaze and Duel

問題概要

0または1からなる $n$ 文字の文字列 $S$ と整数 $k$ が与えられ、それを用いて2人がゲームをする。交互にターンが回り、それぞれのターンで各プレイヤーは「連続する $k$ 文字を選び、それらを全て0または全て1にする」という操作を行う。プレイヤーの操作後に全ての文字が同じになったとき、そのプレイヤーが勝利する。

2人が最適に行動した時に先攻と後攻のどちらが勝つか、または $10^{9}$ ターン経過しても決着が付かない（引き分け）か、判定せよ。

制約

$1 \le k \le n \le 10^{5}$
$S$ は0または1からなる $n$ 文字の文字列

解法

ゲームの展開を以下のように分類しましょう。

パターン1：先攻が1ターン目で勝つ場合

入力例3のようなケースです。あるいはもっと分かりやすい例だと、

8 4
01111000

などが該当します。4個並んでいる1を全て0に変えると勝ちです。

先攻が1ターン目で勝てるかどうかの判定は次のようにできます。左端から連続して0が並んでいる個数を $L_{0}$ 、右端から連続して0が並んでいる個数を $R_{0}$ として、もし $L_{0} + k + R_{0} \ge n$ であれば間を0に変えることで勝てます。同様に1についても判定できます。

このように、次に1回操作することで勝てるような文字列の状態を「リーチ状態」と呼ぶことにします。

※既に全文字が一致している場合も「リーチ状態」に含めます。テストケース5～8などにあるように、これが初期状態として与えられた場合も先攻の勝ちになります。

パターン2：後攻が1ターン目で勝つ場合

入力例1のようなケースです。

4 2
0101

入力例1では、先攻1ターン目では勝てません。そして先攻が操作した後の文字列として考えられるものは 0001 0100 1101 0111 です。これらは全てリーチ状態であり、どれを渡しても後攻が次の操作で勝つことができてしまいます。

もし操作後の文字列でリーチ状態でないものが1つでもあれば、先攻はそれを渡すことでひとまず負けを免れます。つまり「先攻が1ターン目で勝てないとき、後攻が1ターン目に勝てるかどうか？」は、「先攻1ターン目の操作の結果として考えられるもの全てがリーチ状態であるか？」と言い換えられます。これを調べるために、「先攻が操作する場所」×「0にするか1にするか」を全探索しましょう。

先攻の操作が0に変更するものだったとすると、判定に必要な情報は先ほどと同じく、先攻の操作後に左右端からそれぞれいくつ0が連続で並んでいるかの値です。これを先ほどと同じく $L_{0}, R_{0}$ と表記します（これらは操作位置に依存します）。これを任意の操作位置について高速に計算したいです。

これは前もって、全ての位置について「そこから左/右に連続で0がいくつ並んでいるか？」を調べておくことで可能です。この前計算は端から順番に見ていくことで $O(n)$ でできます。インデックス $i$ の位置から左に連続で0がいくつ並んでいるかを $l_{i, 0}$ 、右に連続で0がいくつ並んでいるかを $r_{i, 0}$ と表記します。

この情報を持っておけば、先攻が0に変更する区間を $\lbrack i, i+k-1\rbrack$ と決めた時に、左端から0が連続している個数 $L_{0}$ は

左端から操作位置まで0が繋がっていない場合、つまり $r_{1, 0} \lt i-1$ であるときには、単に元の状態のまま $L_{0} = r_{1, 0}$
左端から操作位置まで0が繋がっている場合、つまり $r_{1, 0} \ge i-1$ であるときには、操作位置のさらに右まで繋がるので $L_{0} = i+k-1+r_{i+k, 0}$

となります（1-indexedです）。

同様の方法で $R_{0}$ も計算することができて、 $L_{0} + k + R_{0} \ge n$ かどうかでリーチ状態であるかどうかを判定できます。これを1に変更する場合についても全部試して、先攻の全ての操作についてリーチ状態であれば後攻が勝ちです。

パターン3：それ以外の場合

それ以外の場合はどうなるでしょうか。これは実は必ず引き分けになります。

重要な性質として、「1回操作された後の文字列は、直前の相手の操作と全く同じ操作をすることで、文字列を変えないようにできる」ということが言えます。このことから、もし「不利な」文字列があったとして、それが相手から渡されてきた場合は、そっくりそのまま相手に返すことができます。これを永遠に繰り返して引き分けになります。

もう少しちゃんと書くと、後退解析の考え方を用います。

ゲームを解く！Educational DP Contest K, L 問題の解説 - Qiita

つまり、「自分の操作前にどうなっていれば勝ちか/負けか」観点で以下のように状態を分類します。

リーチ状態は、もらうと操作1回で勝てるので「勝ち状態（ゲーム終了）」
パターン2のように勝ち状態しか相手に渡せない状態は「負け状態」
相手に負け状態を渡す操作が1つでも存在する状態は「勝ち状態」
勝ち状態でも負け状態でもない状態は「引き分け状態（無限ループ）」

として状態（今回は文字列）を分類していきます。

先攻も後攻も1ターン目で勝てなかった場合、先攻が操作した後の文字列は勝ち状態とも負け状態とも言えません。もし負け状態であればその負け状態自身を相手に渡せるので負け状態の定義に合いません。負け状態が存在しない以上、リーチ状態でない勝ち状態も存在しません。

このことからこれは引き分け状態であり、ゲームの結果としては引き分けになることが分かります。

ACコード

Submission #56916660 - Codeforces

複数ターンに渡る操作を考えようとするとものすごく大変なので、まずは「1ターン目で決着がつかなかったら必ず引き分け」ということに気づけるか。そしてパターン2の判定を効率的な計算量で実現できるか。この2点がキモでした。

2019-07-08

AtCoder Beginner Contest 133 F - Colorful Tree

AtCoder プログラミング競技プログラミング

F - Colorful Tree

解法

木の2点間距離たくさん→LCA

長さの変更についていったん無視すると、この問題は「木の2点間距離をたくさん求めてください」というものです。これはLCA（最小共通祖先）というものを用いると効率的に求めることができます。

根付き木における2頂点のLCAとは、それらの共通祖先のうち最もその2頂点から近い頂点のことです。2頂点からそれぞれ根までのパスを考えた時に合流するところ、とイメージしてもよいです。

これを用いると、2点間の距離は以下のように求めることができます。

前計算
- 適当に根を決める。
- あらかじめ、根から全点への距離を求めておく。根と頂点 $v$ の距離を $d_{v}$ と表す。
- 2点のLCAを効率的に求めるための前準備をしておく。
頂点の距離の計算
- 頂点 $u, v$ のLCAを求める。これを $l$ とする。
- 頂点 $u, v$ 間の距離を、 $d_{u} + d_{v} - 2d_{l}$ と求める。

f:id:betrue12:20190707233844p:plain

LCAを効率的に求める方法としてはダブリングなどがあります。（仕組みや実装例は蟻本などを参照してください）

各クエリで辺の値が変わるときにもこのテクニックは使えます。つまり各クエリ $(x, y, u, v)$ に対しては、 $l$ を $u, v$ のLCAとして「色 $x$ の辺の長さを全て $y$ に変えた時の、ある1頂点と根との距離を求める」ことを $u, v, l$ の3頂点について求めればよいことが分かりました。これ以降は根との距離を上手く求めることを考えていきます。

長さ変更の影響を考える

色 $x$ の辺の長さを $y$ に変えた時の、頂点 $v$ から根までの距離は

頂点から根までの経路の…
- 初期状態における距離 $D_{v}$
- 経路中にある色 $x$ の辺の長さ合計 $d_{v, x}$
- 経路中にある色 $x$ の辺の本数 $n_{v, x}$

これらを用いて $D_{v} - d_{v, x} + yn_{v, x}$ と求めることができます。

これらの値のうち、 $D_{v}$ を全点について求めることはDFSなどで根から順に計算していけば $O(N)$ で可能です。一方色に依存する $d_{v, x}$ や $n_{v, x}$ は、色ごとに計算すれば求めること自体は $D_{v}$ と同様にDFSでできるものの、全ての頂点×色の組み合わせが $O(N^{2})$ 個あるので全部求めるとTLE/MLEなどになってしまいます。

クエリ先読み！

そこでまず、DFSをしながら「今見ている頂点についての $d_{v, x}, n_{v, x}$ はいくつか？」という値を全ての色 $x$ について管理していくことを考えましょう。DFSで1歩進む・戻るときに通る辺は1本なので、その辺の色についての情報だけを変更すればよいです。

これを全ての頂点×色について記憶するとTLE/MLEになりますが、クエリは事前に分かっているので必要なところだけを記憶しておくことができます。各クエリに対して必要な頂点と色のペアは3個なので、必要になるのは全部で最大でも $3Q$ 個のペアです。あらかじめこれを列挙して頂点ごとに分類しておき、DFSしながら各頂点を通る時に必要な色についての値だけ記憶しておくようにすれば、DFSと差分更新に $O(N)$ 、値の記憶に（mapなどを使うことを想定して） $O(Q\log Q)$ の時間計算量で前計算をすることができます。

あとはこの前計算結果を使って、各クエリに対してこれまで書いてきた計算式を用いれば答えを求めることができます。

ACコード

Submission #6301894 - AtCoder Beginner Contest 133

2019-07-05

AtCoder Regular Contest 085 E - MUL

AtCoder プログラミング競技プログラミング

お題箱より。

E - MUL

解法

私自身、この問題は解説を読んで衝撃を受けた記憶があります。知らないと自力で思いつくのは相当難しいので、テクニックとして覚えてしまいましょう。

先人の知恵

競プロでは俗称「燃やす埋める問題」と言われている問題カテゴリです。この言葉で調べると競プロ関連の情報が出てくると思いますが、特に以下の2つの解説がオススメです。

最小カットを使って「燃やす埋める問題」を解く（後半は難しいです）
最小カットについて - よすぽの日記

私の解説もだいたいこの2つの解説と同じような説明になりますが、今回の問題でどのように解いていくかを具体的に書いていこうと思います。

「燃やす埋める問題」の定式化

「燃やす埋める問題」は、以下のように表現できる問題、およびそれを解くテクニックの呼び方です。これは基本形で、上記リンク先（特に診断人さんのスライド）には色々な応用が紹介されています。

$N$ 個の要素があり、それぞれについてAとBの2択の選択肢がある。

今回の問題では、各宝石を「残す」と「割る」の2択です。

各要素の選択肢それぞれについて、報酬や罰金が設定されている。

今回の問題では、残すと $a_{i}$ 円の報酬（負なら罰金）。割るとプラマイ0円。

以下のような条件がたくさん存在する。
- ある2要素 $x, y$ について、" $x$ はBだけど $y$ はA" という選び方にすると罰金が発生する。もしくは、この選び方にすることができない。

この条件への対応付けは少し言い換えが必要です。今回の問題の「正整数 $x$ を選ぶ。 $x$ の倍数が書かれた宝石を全て叩き割る。」という条件は、「2以上の整数 $k$ について、 $x$ を割って $kx$ を残すことはできない」と言い換えることができて、この条件の形になります。

罰金の最小化（報酬の最大化）をしたい。

こんな問題です。

グラフを作る（仮）

このように表現できる問題を、以下のようなグラフの最小カット問題に帰着させて解きます。 $N=4$ とします。

f:id:betrue12:20190705005603p:plain

f:id:betrue12:20190705005611p:plain

グラフの作り方を言葉で書くと以下のようになります。

各条件を真ん中に並べて、始点 $S$ からの辺と終点 $T$ への辺をそれぞれ張る。
始点側の辺には選択肢A（残す）の罰金を、終点側の辺には選択肢B（割る）の罰金を重みとして設定する。報酬は全て罰金に言い換える。
「" $x$ はBだけど $y$ はA" という選び方にすると罰金」という条件それぞれについて、AからBにその罰金を重みとする辺を張る。「できない」場合は罰金 $\infty$ とする。

このグラフにおける最小カット、つまり「始点から終点まで到達できないようにするために切る辺集合」（これをカットと呼びます）の重み合計の最小値が、この問題における罰金の最小値になります。

ここで真ん中の頂点それぞれについて、始点側と終点側の2辺のうち必ず一方は切らないといけません。この辺を「切る」ことが、対応する選択肢を「選ぶ」ことに対応します。繋がっている方を採用するわけではないことに注意してください。

※ここで「両方切ったほうがトータルで得になる可能性はないの？」という疑問が浮かぶかもしれません。最後に補足します。

そして「" $x$ はBだけど $y$ はA" という選び方にすると罰金」という条件については、そっちの辺を切ったときにカットが成立しない方向に辺を張る、と覚えましょう。

f:id:betrue12:20190705013402p:plain

「解ける」ように条件を整える

この最小カット問題を解くために、いくつか条件を変形して整える必要があります。先ほど既に書いたものもありますが、確認していきましょう。

まずは全部罰金にして最小化問題に

先ほども書いたように、これは罰金を辺の重みとするグラフの最小カット問題になります。そのため「 $a_{i}$ 円の報酬」を「 $-a_{i}$ 円の罰金」と言い換えることで全条件を罰金にして、罰金を最小化する問題にします。

「できない」は $\infty$ 円の罰金に置き換える

先ほど書いた通りです。実装上は十分大きい数とします。

全部の罰金を非負にする

最小カット問題をよく知られたアルゴリズムで高速に解くためには、全ての辺重みが非負である必要があります。例えば正の報酬を罰金に置き換えると負の罰金が生まれてしまうので、これを上手く非負の罰金に変換します。

今回の場合は、 $a_{i}$ が正のときに「残すと $-a_{i}$ 円の罰金、割ると0円の罰金」となって負の罰金が登場します。これを

無条件で $a_{i}$ 円もらえる。 その上で、残すと0円の罰金だが、割ると $a_{i}$ 円の罰金（もらったものを没収されるイメージ）

と置き換えます。こうすると罰金を非負にすることができます。これは今回の問題に限らずよく使うテクニックです。

グラフを作る（改）

具体的に、入力が

4
1 -3 1 2

の時のグラフを描いてみましょう。先ほどの方法で罰金を非負にしないようにすると、以下のグラフを得ます。

f:id:betrue12:20190705005624p:plain

あとは最小カット問題を解きます。この解は「最大フロー最小カット定理」より最大フロー問題の解と一致するので、最大フロー問題を効率的に解くDinic法などのアルゴリズムで解くことができます。

例えば先ほどの入力例では、以下が答えになります。

f:id:betrue12:20190705005633p:plain

おまけ：「両方切る」可能性は考えなくて良い？

先ほど書いた、「始点側と終点側の辺を両方切ったほうがトータルで得になる可能性はないの？」という話です。もし仮にこれが最適解になってしまうと、「 $N$ 個の要素の2択を選んでいく」元の問題との対応が取れません。

これは両方切ることが得になりそうなグラフを実際に考えてみると分かります。ある頂点 $i$ について、始点からの辺と終点への辺がどちらも正の重みを持ち、最小カットにおいてどちらも切られているとします。

まず最適解において始点からの辺が切られている場合、以下のような経路が存在しているはずです。もしこのような経路がない場合は、単にこの辺を切らないようにして値を改善できるからです。

f:id:betrue12:20190705012238p:plain

同様に終点への辺が切られている場合は、以下のような経路が存在しているはずです。

f:id:betrue12:20190705012250p:plain

これをつなげると…以下のように始点から終点への経路ができてしまいます。

f:id:betrue12:20190705012307p:plain

これは最小カットだという仮定で出発したのに、カットになっていません。つまりこのことから、「始点からの辺と終点への辺がどちらも正の重みを持ち、最小カットにおいてどちらも切られている」ということは有り得ないことが分かります。

ただしこれはあくまで、今回紹介した方法で構成したグラフに限定した証明です。私自身、別の問題で最小カットに帰着したときに「余分に切ったほうが得になる場合がある」ようなグラフを作ってしまってACできなかった経験があるので、とても重要な着眼点だと思います…。

ACコード

Submission #6238817 - AtCoder Regular Contest 085

ちゃんと手元で図を描いて、どっち側の辺を切ることがどっちの選択肢に対応しているかも書いて、グラフを構成していくのが慣れるコツだと思います。

類題

比較的考察がやさしい類題です。AtCoderだとフローに帰着するまでが難しい問題が多いので、Codeforcesから。

Problem - 1082G - Codeforces

2019-06-27

Codeforces Round #570 (Div. 3) F. Topforces Strikes Back

Codeforces プログラミング競技プログラミング

ちょっと変わった解き方をしたので記録。

Problem - F - Codeforces

（追記）公式Editorial もこの解き方でした。

問題概要

以下の問題を $q$ ケース解け。

$n$ 個の正整数 $a_{1}, ..., a_{n}$ が与えられる。この中から3個以下の整数を「どの2要素も約数・倍数の関係にない」という条件を満たすように選んだ時の、合計値の最大値を求めよ。

制約

$1 \le q \le 2\times 10^{5}$
各ケースについて、
- $1 \le n \le 2\times 10^{5}$
- $2 \le a_{i} \le 2\times 10^{5}$
全ケースの $n$ の合計は $2\times 10^{5}$ 以下

解法

「どの2要素も約数・倍数の関係にない」ことを単に「条件を満たす」と書くことにします。

同じ整数を2個以上選ぶことはできないので、とりあえず重複要素を除いておきます。以降は全要素が異なっているとします。

貪欲で行けないか？

$O(n^{2})$ 以上の解法は通りそうになく、DPを組むのも難しそうなので、貪欲を疑ってみます。大きい方の要素から決められると嬉しいので、試しに「一番大きい要素を取ると決めてしまって良いだろうか？」「もしそれがダメなら、どのような反例が考えられるか？」を考えてみましょう。

これを証明するための常套手段は、

一番大きい要素を $M$ として、 $M$ 以外から3個以下の要素を条件を満たすように選んだとき、ここから $M$ を選ぶように変更することで値を改善できる

ことを示すことです。

実際に、ほとんどの場合では値を改善できると示すことができます。選んだ要素の中に $M$ の約数が何個含まれるかで場合分けします。

$M$ の約数が0個の場合

この場合、どれか1個の要素を選ばないことにして代わりに $M$ を選ぶことで値が改善します。どれも $M$ の約数でないので条件に違反することはありません。

$M$ の約数が1, 2個の場合

この場合、 $M$ の約数であるものを選ばないことにして代わりに $M$ を選ぶと、条件に違反せずに必ず値が改善します。なぜなら $M$ の約数で $M$ でないものは $\frac{M}{2}, \frac{M}{3}, \frac{M}{4}, ...$ のいずれかであり、この中から1個または2個を選んだ和は必ず $M$ よりも小さくなるからです。

$M$ の約数が3個の場合

同様に「 $M$ の約数を全部外して代わりに $M$ を選ぶと値が改善する」と言いたいところですが、3個ある場合は少しだけ事情が違います。3個の和が $M$ を超えるものが1パターンだけ存在し、それは $\frac{M}{2} + \frac{M}{3} + \frac{M}{5} = \frac{31}{30}M$ の3個を選んでいる場合です。これは親切にサンプルにも含まれています。

これ以外に和が $M$ を超えるパターンがないことを示します。先ほどと同様に、 $M$ の約数で $M$ でないものは $\frac{M}{2}, \frac{M}{3}, \frac{M}{4}, ...$ のいずれかであることを使います。

まず、3個全てが $\frac{M}{3}$ 以下だと和が $M$ を超えられないので、 $\frac{M}{2}$ は必ず含まれている必要があります。そうすると $\frac{M}{2}$ の約数となる $\frac{M}{4}, \frac{M}{6}, \frac{M}{8}, ...$ は採用できません。

あと2個で残りの $\frac{M}{2}$ を超える必要があるので、同様の理由で $\frac{M}{3}$ が必ず含まれる必要があります。そうなると最後の1個はどちらの約数でもない $\frac{M}{5}, \frac{M}{7}, \frac{M}{11}, ...$ から選ぶ必要があり、 $\frac{M}{2} + \frac{M}{3} + \frac{M}{7} = \frac{41}{42}M \lt M$ であることから、最後の1個は $\frac{M}{5}$ しかありえません。

以上の考察を踏まえて

つまり、答えは以下の2通りのどちらかに絞られます。

最大要素 $M$ を使うと仮定したときに実現できる最大値。
$\frac{M}{2}, \frac{M}{3}, \frac{M}{5}$ が全て含まれている時に限り、これら3個を選んだ合計値 $\frac{31}{30}M$ 。

最大要素を使うと仮定すれば、あとは $M$ の約数を全て消した上で、約数・倍数関係でない残り2個の合計を最大化する問題になります。これは先ほどの「 $M$ の約数が2個以下」のときの議論がそのまま使えて、やはり選べるものの中で最大のものを2個目として選ぶのが最適となります。さらに残ったものの中から3個目を選べば良いので、結局3個とも大きい方から貪欲で選べます。

$\frac{M}{2}, \frac{M}{3}, \frac{M}{5}$ が全て存在する場合は貪欲解と $\frac{31}{30}M$ の大きい方を採用し、存在しない場合は貪欲解をそのまま答えとすれば良いです。ソートやsetの利用などを考慮して、ケースごとに計算量 $O(n\log n)$ で解けます。

ACコード

Submission #56104187 - Codeforces

2019-06-22

yukicoder No.778 クリスマスツリー

yukicoder 競技プログラミングプログラミング

お題箱より。

No.778 クリスマスツリー - yukicoder

解法

飾りを頂点0を根とする根付き木とみなします。言葉を言い換えると、求めるものは以下の2条件を満たすペア $(i, j)$ の個数です。

頂点 $i$ が頂点 $j$ の先祖である。
頂点番号について、 $i \lt j$ である。

ここでの「先祖」は、ある頂点の親、その親、その親…を根まで辿った頂点全てを指します。また、先祖と逆の関係にあるものを「子孫」と表現することにします。

つまり「位置関係（親子関係）」と「頂点番号の大小関係」の2つが条件になっています。このような問題では、片方の条件が扱いやすいような探索順番で頂点を見ていきながら、データ構造などを用いてもう片方の条件を満たすものを効率的に数える、という方法が有効であることが多いです。

そのような解法を2つ紹介します。

解法1

解法1では、親子関係を扱いやすい探索順で探索していくことを考えましょう。深さ優先探索で頂点を1つずつ見ていくことを考えます。

木の深さ優先探索では「今見ている頂点の先祖にある頂点たち」の集合を管理しながら探索することができます。具体的には頂点 $i$ を訪れたとき、以下のような手順で処理します。

まずは、頂点 $i$ とその先祖たちについて求めたい何かを計算する。（今回の場合は、 $i$ より番号の小さい先祖の個数を答えに足す）
先祖たち集合の中に頂点 $i$ を加える。
頂点 $i$ の子それぞれについて、再帰的に同じ処理を行う。
子を全て処理し終わって頂点 $i$ を出る時、先祖たち集合から $i$ を除く。

先祖たち集合として set を利用したC++の実装イメージは以下です。処理全体で同じものを使うので、グローバル変数にするか参照渡しで渡してあげてください。

set<int> ancestors;
void dfs(int i){
    ans += <iより番号の小さい先祖の個数>;
    ancestors.insert(i);
    for(int j : child[i]) dfs(j);
    ancestors.erase(i);
    return;
}

あとは、各頂点 $i$ を訪れた時に「 $i$ より番号の小さい先祖の個数」を効率的に求めることが必要です。これはデータ構造を用いましょう。上記のコード中でsetを使っている代わりに、頂点番号をインデックスとしたBITやセグメント木を用いればよいです。

解法1 ACコード

#353465 No.778 クリスマスツリー - yukicoder

これは

親子関係を扱いやすい探索順にして、
頂点番号の大小関係をデータ構造で処理する

という解法でした。個人的にはこちらの解法が解きやすくてオススメです。

解法2

次に公式解法のほうです。こちらは解法1とは逆で、

頂点番号の大小関係を扱いやすい探索順にして、
親子関係をデータ構造で処理する

というものになっています。

頂点番号を大きい方から見ていくことを考えます。そうすると、ある頂点 $i$ を見ているときに数えるべきものは、

既に見た頂点であって、頂点 $i$ の子孫であるものの個数

となります。解法1では数える条件が「頂点番号が $i$ より小さい」だったので区間和が使えましたが、「子孫である」という条件はどう扱いましょう？

ここで使えるのがオイラーツアーというテクニックです。これは根付き木に対して「DFSで訪れた頂点の順番を、行き帰り含めて全て並べた数列」を求めたものです。

英語ページですが、図があったほうが良いと思ったので参考としてこちらを紹介します。

Euler Tour of Tree - GeeksforGeeks

このオイラーツアーの数列において、部分木（ある頂点自身とその子孫からなる木）は連続した1つの区間を構成しています。つまりオイラーツアーの数列に対応したBITを作ると、「頂点 $i$ の子孫であるものの個数」は区間和として効率的に計算することができます。

つまり頂点番号を大きい方から見ていきながら、それぞれの頂点 $i$ を見る時に

頂点 $i$ 以下の部分木に対応するオイラーツアー上の区間について、BIT上で区間和を取り答えに加算する。
頂点 $i$ に対応するオイラーツアー上の点1箇所について、BIT上で1を加算する。

のように処理することで解けます。一般にオイラーツアーでは1つの頂点のインデックスが複数個入るので、値を足す際には注意してください。この問題の場合はどこでもいいので1箇所に足せば大丈夫です。

解法2 ACコード

#353478 No.778 クリスマスツリー - yukicoder

2019-06-20

スクリプト言語などで競プロをすることについて

「スクリプト言語」と呼ばれるRuby、Pythonなどの言語に代表される、比較的実行速度の遅い言語で競技プログラミング（特にAtCoder）をすることについて。

最近色々ともやもやすることが多いので、思っていることを書きます。まさにこれらの言語を使っている方々、これらの言語を使うことについて何か物申したがる方々、そしてコンテストを運営されている方々それぞれに向けて。

長いです。興味があれば読んでください。

2023/03/06追記

この記事の内容は、公開当時である2019年頃のTwitter 競技プログラミングコミュニティに関するものです。いくつかの要因で現在このような風潮は弱くなっていると感じます。記事を読まれる際はその点にご注意ください。当時のような風潮が再び蔓延しないことを願います。

私の立場

私は競技プログラミングを始めた当初はRubyを使っていました。AtCoder青まではRubyのみで問題を解いていました。

その後、徐々に速度面での限界を感じてC++への移行をしました。現在はratedコンテストでは（多倍長整数を使いたいなどの）特別な理由がない限りはC++を使っています。

現在AtCoder橙ですが、もし仮にRubyだけを使い続けていたとしたら橙にはなれていない（もしくは、もう数年かかっている）と思っています。

スクリプト言語での競技プログラミングについて

実際に使っている方は十分身に沁みていると思いますが、問題によっては想定解法を実装してもTLEが出てしまい通せないことがあります。これは確かな事実です。

もちろんスクリプト言語の中でもその速度差はあり、私の体感ではPython（いわゆる普通のPython）よりはRubyのほうが多少速いように思います。一方でPythonにはPyPyという高速な実装があり、これはRubyより遥かに高速です。競技プログラミングでもよく活用されています。

なので一概には言えませんが、私がRubyで問題を解いていた頃は、AtCoderのratedコンテストの点数で

400点以下の問題は素直な実装でほぼ通る
500～600点には、定数倍高速化を考慮しない実装では通りにくいものが存在する
700点以上では、体感でおよそ半分ほどの問題は通すために（可読性を損なうレベルの）定数倍高速化が必要か、またはそれでも通らない

という印象です。ただこれはあくまで体感であり、コンテスト開催側が「○○点問題は○○言語でACできることを保証します」と宣言しているわけではありません。

ただしこれは私がRubyで問題を解いていたおよそ1年前の頃の話で、直近のコンテストでは300～400点でもスクリプト言語に厳しい問題が出題される頻度が上がっているように思います。AC者がいることから分かるように、定数倍高速化をすれば通るレベルのものではあります。

A - Darker and Darker

D - Lamp

そのため以前私は「青までならスクリプト言語で問題なく到達できる」と主張していましたが、この傾向が今後も続くようであればRubyで到達できるかは少し怪しいかもしれません。

やはり現在のAtCoderではC++に次いでPythonの利用者が多く、PythonユーザであればPyPyという強力な武器を使うことができます。AtCoderのコンテスト運営に携わっているとある方が「PyPyなら通ります」ということをよく言われていますし、やはり「PyPyで通る」が1つの基準になっているのかなと想像します。そのぶん他のスクリプト言語利用者には厳しい状況になっていくかもしれません。

また実際に問題をACできないこと以外に、「遅い言語で競プロをすることについてTwitter等で人々が物申す現象が定期的に発生する」というのも、実情としてはつらい点です。「物申す」という表現は失礼かもしれませんが、すみません、あえて書きました。私の受けている印象をそのまま書くとこういう表現になってしまいます。

問題をACしたいなら速い言語を使うべきという主張は「正論」です。ド正論です。正論だからこそ言いたくなってしまうのかもしれませんね。ただし、少なくとも私は「そんなことは百も承知でRubyを使っていた」わけで、分かりきった「べき」論を言及されることに正直良い気はしません。同じような思いのスクリプト言語使いも多いのではないでしょうか。特に最近はユーザが多く目立つからなのかもしれませんが、やたらPythonユーザに対する言及が多いように思います。

スクリプト言語利用者の方へ

先述した通り、問題面でも環境面でも今後より厳しい状況になっていく可能性があります。私は自身の経験もありこれらの言語で競技プログラミングをする人を応援したいと思っていますが、この状況を変えることはとても難しいと思っています。

まずお願いしたいのは、「通せない問題があることを受け入れる」ということです。もっと言うと「特定の言語で通せない問題を出題するコンテストに非がある」ということは無いし、「全ての言語でACを取れるようにコンテストを構成すべき」という主張は良くないものだと理解してほしいです。いえ、そう思うこと自体は構わないのですが、今の競プロコミュニティではそれをSNS等で主張することのデメリットが予想以上に大きく、またこの問題が完全に解消される望みが薄いことからあえて「良くない」という言葉を使っています。

コンテスト運営側としても、想定解法が通らないことはなるべく避けたいと思っているでしょう。しかし実際問題としてこれを本質的に改善することは非常に困難です。

その上で、「可能な限りハンデを緩和するテクニックを身に付ける」ようにしましょう。同じような処理に見えても、書き方1つで大きく実行時間は変わるものです。これは同じ言語を使っていて、競プロ歴が長い人やレートの高い人を頼るのが一番です。

Pythonであればこちらの記事が非常に有用です。

https://juppy.hatenablog.com/entry/2019/06/14/Python%5F%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E9%AB%98%E9%80%9F%E5%8C%96tips%5F%28Python%E3%81%A7Atcoder%E3%82%92%E3%82%84%E3%82%8B%E9%9A%9B%E3%81%AB%E5%80%8B

Rubyについては私が記事を書いていますが、あまり高速化技法に触れられていない点は申し訳ないです…

Rubyで競プロするときのTips - ARMERIA

そして、より高いレートを目指すのであれば「いずれは他の言語に移行する必要がある」ことを頭の片隅に入れておいてください。これも言語ごとの事情や今後の出題傾向に大きく依存しますが、目安としては「青になったらそろそろ」という感じです。言語の移行は簡単に出来ることではないですが、出来る限り道を用意していけたらと思っています。

そうではない方々へ

スクリプト言語を使っているのはあなたと同じ競プロerであり人間です。そのことを忘れないでください。

…と言うのも変な話ですが、こう言いたくなるくらい現状はつらいと思っています。意図的に攻撃的なことを言いたがるような一部の人は別としても、それに限らずこの話題は「正論の言及」をしたがる人が多いようです。

私の知る限り、スクリプト言語である程度の期間競プロをやっている人のほとんどは言語のデメリットを受け入れた上で競プロをしています。自分でも理解している正論をことあるごとに投げつけられるとつらい…ということは、この話題に限らず多くの人は経験があるのではないでしょうか。

そうではない人への言及、特に「通せない問題があることについてコンテスト運営に文句を言う人」への批判も見られます。確かにそのような人も中にはいるでしょうし、それは違うと私も思います。ただ得てしてこのような言及は攻撃的になりやすく、連鎖的に言及範囲が広くなり先述の「正論の言及」が発生しがちです。つらいです。

たかがTwitter、それなりの節度を持って好きなことを書けば良いと思います。ここで書いたことを辞めてくれと強制することもしないしできません。ただ、その言語を使っている当事者たちはそれを見てどう感じているのか、よかったら一度考えてみてください。私はつらいです。

コンテストを運営されている方々へ

言語間の速度差に関する問題は運営の方も頭を悩ませていると思います。よく言われるような、言語ごとの実行時間制限や制約の大幅な緩和をしてしまってはコンテスト全体の公平性を維持できない、という論は私も全く正しいと思います。

本音を言えば、先程書いた「400点以下の問題はRuby・Pythonの素直な実装でほぼ通る」状態はなるべく維持するように問題選択をしてくれたら嬉しい、とは思っています。AtCoder（特にBeginner Contest）の運営思想として、いわゆる「アスリート」指向の競技者に限らず広く参加者を集めたい、という思いがあるのであれば尚更です。ただ通ることを「保証する」ことはとても手間がかかると思うので、あくまで問題選択の指針として、です。

また、運営の方も我々参加者もTwitterがかなりの情報共有場になっているので、Twitterで頻繁に話題になっていると十分周知されていると勘違いしがちですが、実際にはそうでない参加者の方が多くいると思います。「全言語でACできることは保証していない」などの記述がAtCoderのサイトでちゃんと分かるようになっていると良いと思います。例えば非公式コンテストのs8pcではトップページにそのような記載がありますが、これと似たような記載が公式ratedにあってもいいのかなと。

あと例えばCodeforcesのDiv.3コンテストだと、時間制限が厳しい問題の問題文には「この問題では、Python利用者はPyPyを使うことを推奨します」という注意書きがあったりします。AtCoderもBeginner Contestであればそのような注意書きを入れるのも一案なのかな、と思っています。

文句を言われることは運営の方にとっても本意でないと思いますが、それらの文句は「悪意」ではなく「無知」によるものではないかと考えています。これらがより広く・公式に周知されるよう、今後改善されていくことを期待します。

おわり

同じ趣味を持つ人同士で、同じように問題を解いて、知識を共有して、レートを競い合って、なのに何故「遅い言語」の話題になるとこうなってしまうんだろう。この状況が少しでも変わるきっかけになればいいなと思い、この記事を書きました。

読んでくださってありがとうございました。

2019-06-17

AtCoder Beginner Contest 130 E - Common Subsequence

AtCoder プログラミング競技プログラミング

E - Common Subsequence

公式解説とほとんど同じだけど、二次元累積和が出てこないようなDPで解いたので記録しておきます。

解法

記法について

数列 $S_{1}, ..., S_{N}$ を単に $S$ 、数列 $T_{1}, ..., T_{M}$ を単に $T$ と書くことにします。

与えられた数列は1-indexedで扱い、「0要素目」として空の要素を考えることにします。空部分列" $()$ "は0要素目が入っているものとみなします。

基本の考え方

いくつか微妙に違う解き方を紹介しますが、基本の考え方は同じです。それは

$S$ のほうは $S_{i}$ より前で終わっていて、 $T$ のほうも $T_{j}$ より前で終わっているような等しい部分列の組に対して、 $S_{i} = T_{j}$ である要素をそれぞれくっ付けることによって、等しい部分列の組が新しく出来る

ということです。図で表すとこんな感じです。

f:id:betrue12:20190617232048p:plain

このような考え方を元にDPを組んでいく、という点ではどの解法も共通しています。

公式解説のDP

公式解説のDPは、もうすこし具体的に書くと以下のものを状態として定義しています。

$dp\lbrack i \rbrack\lbrack j \rbrack =$ 数列 $S$ の $i$ 要素目までを使いちょうど $S_{i}$ で終わるような部分列と、数列 $T$ の $j$ 要素目までを使いちょうど $T_{j}$ で終わるような部分列の組で、列として等しいものの個数。

このように定義すると、もちろん $S_{i} \ne T_{j}$ のときは $dp\lbrack i \rbrack\lbrack j \rbrack = 0$ です。そして $S_{i} = T_{j}$ のときはそれより前で成立している部分列の組全てから遷移してくるため、公式解説のように二次元累積和を用いて遷移を計算できます。

この場合、答えは $\sum_{i=0}^{N}\sum_{j=0}^{M}dp\lbrack i \rbrack\lbrack j \rbrack$ になります。

ちょっとちがうDP

これとは少し違うやり方として、以下のような状態を考えることもできます。

$dp\lbrack i \rbrack\lbrack j \rbrack =$ 数列 $S$ の $i$ 要素目までを使った部分列と、数列 $T$ の $j$ 要素目までを使いちょうど $T_{j}$ で終わるような部分列の組で、列として等しいものの個数。

ここでは $T$ のほうだけに「ちょうど終わる」条件を付けています。ここで、空部分列同士のペアはそれぞれ0要素目で終わるものと見なします。

このDPテーブルを $i$ が小さいところから埋めていく遷移を考えましょう。

「貰うDP」で考えます。 $dp\lbrack i \rbrack\lbrack j \rbrack$ に遷移してくる遷移元として2通り考えられます。まずは、

$S$ のほうは $S_{i}$ より前で終わっていて、 $T$ のほうは $T_{j}$ でちょうど終わるような部分列の組

です。その個数はまさに $dp\lbrack i-1 \rbrack\lbrack j \rbrack$ で、これは $dp\lbrack i \rbrack\lbrack j \rbrack$ にもそのまま含まれます。

それとは別に、 $S_{i} = T_{j}$ のときに限り次のようなものが考えられます。

$S$ のほうは $S_{i}$ より前で終わっていて、 $T$ のほうも $T_{j}$ より前で終わっているような部分列の組に対して、それぞれ $S_{i}, T_{j}$ を付け足したもの

この場合の遷移元は、 $\sum_{k=0}^{j-1} dp\lbrack i-1 \rbrack\lbrack k \rbrack$ になります。「 $T_{j}$ より前で終わっている」という条件に合致するように、 $T$ のほうの添字について $j-1$ までの和を取っている形です。

これは言うなれば「一次元累積和」ですね。この和は各 $i$ について遷移を計算する際に、 $j$ を0から $M$ まで順に動かしながら順番に足していくことで管理することができます。

このDPを最後まで計算して、 $\sum_{j=0}^{M} dp\lbrack N \rbrack\lbrack j \rbrack$ が答えです。

もうちょっとちがうDP

詳しくは説明しませんが、他にも次のような状態を定義しても解くことができます。

$dp\lbrack i \rbrack\lbrack j \rbrack =$ 数列 $S$ の $i$ 要素目までを使った部分列と、数列 $T$ の $j$ 要素目までを使った部分列の組で、列として等しいものの個数。

どっちも「ちょうど終わる」という条件がなくなってますね。この場合の遷移はLCS（最長共通部分列）のDP遷移によく似たものになり、「LCSっぽく解く」と言っている人は多分これで解いていると思います。これでも解けます。

この場合は答えは $dp\lbrack N \rbrack\lbrack M \rbrack$ になります。

このように、状態の定義がちょっとずつ違うので遷移と最終的な答えがちょっとずつ違ってきます。冒頭に書いたとおり、本質的にやっていることは同じです。

ACコード

Submission #5962772 - AtCoder Beginner Contest 130

私が本番書いた解法は2番目に紹介した「一次元累積和」のものなので、そのコードリンクです。

ちょっとずつ違う解き方が色々あるぶん、解法の情報を断片的に見るとかえって混乱するかもしれません。どのように状態を定義した場合の解法なのかを区別しながら理解し、どれでもいいので1つ決めてから解いてみることをオススメします。

問題概要

制約

解法

パターン1：先攻が1ターン目で勝つ場合

パターン2：後攻が1ターン目で勝つ場合

パターン3：それ以外の場合

ACコード

解法

木の2点間距離たくさん→LCA

長さ変更の影響を考える

クエリ先読み！

ACコード

解法

先人の知恵

「燃やす埋める問題」の定式化

グラフを作る（仮）

「解ける」ように条件を整える

まずは全部罰金にして最小化問題に

「できない」は 円の罰金に置き換える

全部の罰金を非負にする

グラフを作る（改）

おまけ：「両方切る」可能性は考えなくて良い？

ACコード

類題

問題概要

制約

解法

貪欲で行けないか？

の約数が0個の場合

の約数が1, 2個の場合

の約数が3個の場合

以上の考察を踏まえて

ACコード

解法

解法1

解法1 ACコード

解法2

解法2 ACコード

2023/03/06追記

私の立場

スクリプト言語での競技プログラミングについて

スクリプト言語利用者の方へ

そうではない方々へ

コンテストを運営されている方々へ

おわり

解法

記法について

基本の考え方

公式解説のDP

ちょっとちがうDP

もうちょっとちがうDP

ACコード

「できない」は $\infty$ 円の罰金に置き換える

$M$ の約数が0個の場合

$M$ の約数が1, 2個の場合

$M$ の約数が3個の場合