コンテストでの時間切れや解けなかった過去問を振り返って供養していく

1/22: AtCoder Beginner Contest 152 F - Tree and Constraints

供養

問題

Difficulty: 1903 (記事作成時点)

解法

条件のどれか1つでも満たさないようなパターンを数える
条件を満たさないとき、間の辺は全て白
- 他の辺の彩色は自由にできるので、 $u_{i}, v_{i}$ 間の辺が $n_{i}$ 個あるとき条件 $i$ を満たさないパターンは $2^{N - 1 - n_{i}}$ 通り
一般化して、ある条件集合をすべて満たさないとき、について間の辺は全て白
- これらの辺の数を $n_{C}$ とすると、条件集合 $C$ をすべて満たさないパターンは $2^{N - 1 - n_{C}}$ 通り
「条件 $i$ もしくは条件 $j$ を満たさないパターン」は
(条件 $i$ を満たさないパターン) $\cup$ (条件 $j$ を満たさないパターン) $\setminus$ (条件 $i, j$ を満たさないパターン)
となる
一般化して、全ての条件を含む集合を $\mathcal{C}$ としたとき、その中のいずれかの条件を満たさないパターンの数は
$$ \sum_{C \neq \emptyset, C \subseteq \mathcal{C}}(-1)^{|C| + 1}2^{N - 1 - n_{C}} $$
任意の条件集合 $C$ について、適当な点を根とする根つき木として見たときに、条件 $i \in C$ について $u_{i}, v_{i}$ の最近共通祖先を $\mathit{LCA}_{i}$ とし、 $u_{i}, v_{i}$ に +1 、 $\mathit{LCA}_{i}$ に -2 として葉から根に向けて累積和を取ると、 $u_{i}, v_{i}$ 間が正の数となるので、そのようになる辺の数を数えれば $n_{C}$ を求められる

実装としては

$T$ を適当な点(e.g. 1)を根とする根つき木とする
$1 \le i \le M$ について、 $u_{i}, v_{i}$ の最近共通祖先を求め、 $\mathit{LCA}_{i}$ とする
$1 \le k \lt 2^{M}$ について $k$ の $i$ bit目が立っていれば $i \in C_{k}$ として条件集合 $\mathcal{C}$ の任意の部分集合を作る
$i \in C_{k}$ について $u_{i}, v_{i}$ に1を加算し、 $\mathit{LCA}_{i}$ から2を減算する
$T$ について葉から根に向かって累積和を計算し、 $v \in T$ での累積和 $S_{v}$ が正の値となる数をカウントし $n_{C_{k}}$ とする
を計算して出力する
- $k = 0$ のとき $C_{0} = \emptyset, n_{C_{0}} = 0$ となるので、 $0 \le k \lt 2 ^{M}$ について $\sum_{C_{k} \subseteq \mathcal{C}}(-1)^{|C_{k}|}2^{N - 1 - n_{C_{k}}}$ でもよい

計算量は $n_{C}$ を求めるのに $O(N + M)$ 、それを $2^{M}$ 解繰り返すので全体で $O((N + M)2^{M})$

公式解説

躓いた点

条件を満たさないパターンを数えようとしていなかった

1/23: SoundHound Inc. Programming Contest 2018 -Masters Tournament- E - + Graph

供養

問題

Difficulty: 2127 (記事作成時点)

解法

ある頂点(e.g. 1)の値を $x$ に固定したとすると、その頂点からあるパス $p_{1} \dots p_{k}$ を通って頂点 $i$ に到達できるとき、 $i$ の値は $\Bigl( \sum_{1 \le j \le k}(-1)^{j+1}s_{p_{j}} \Bigr) - (-1)^{k + 1}x$ となり、頂点 $i$ について $a_{i} + x$ もしくは $b_{i} - x$ の形で表現できる
上記 $a_{i}, b_{i}$ は（存在すれば）いかなるパスを通っても一意に定まる
i.e. あるパスで $a_{i} + x$ と表現され、別のパスで $a_{i}^{'} + x$ と表現されるとき、 $a_{i} \neq a_{i}^{'}$ ならば条件を満たす割り当ては存在しない( $b_{i}$ についても同様)
それぞれの表現方法についてもしくはの条件が得られるので、条件をすべて満たすの範囲を求める
- ある点 $i$ について $a_{i} + x, b_{i} - x$ の両方の表現が可能なとき、 $a_{i} + x = b_{i} - x$ より $x = \frac{b_{i} - a_{i}}{2}$ と一意に定まる

実装は

を値未定で用意する
- 型が限定される場合十分大きな数や十分小さな数で代用
とし、頂点1から以下のようにを更新していく
- 頂点 $u$ から辺 $i$ を通って頂点 $v$ に到達可能としたとき、 $a_{u}$ が存在するならば $b = s_{i} - a_{u}$ 、 $b_{u}$ が存在するならば $a = s_{i} - b_{u}$ とする
- が定義されたとき、が未定義ならとし、定義済みならか確認する
  - $a_{v} \neq a$ ならば 0 を出力して終了
- $b_{v}, b$ についても同様に行う
- $a_{v}$ もしくは $b_{v}$ の更新が行われたとき、 $v$ を起点に新たに隣接点の探索を実施する
- 上記の探索を更新が止まるまで行う
  - 各辺について高々4回しか見ないので更新はかならず停止する
$X_{\mathit{min}} = 1, X_{\mathit{max}} = s_{1} - 1$ とする
について、以下のようにを更新していく
- $a_{i}$ が定義されていれば $X_{\mathit{min}} = \mathrm{max}(-a_{i}, X_{\mathit{min}})$
- $b_{i}$ が定義されていれば $X_{\mathit{max}} = \mathrm{minx}(b_{i}, X_{\mathit{max}})$
について、の両方が定義されているものについてとする
- $b_{i} - a_{i} \le 0 \lor (b_{i} - a_{i})\; \mathrm{mod}\; 2 \equiv 1$ のとき、 $x_{i}$ が正整数でなくなるので 0 を出力して終了
- $x_{i} \neq x_{j}$ となるような $(i, j)$ が存在するとき、 $x$ を一意に定められないため 0 を出力して終了
- $x_{i} \lt X_{\mathit{min}} \lor X_{\mathit{max}} \lt x_{i}$ のとき、すべての条件を満たす $x$ が存在しないので 0 を出力して終了
- 上記以外の場合、条件を満たす $x$ が一意に定まるので 1 を出力して終了
$\mathrm{max}(X_{\mathit{max}} - X_{\mathit{min}} + 1, 0)$ を出力

計算量は条件を決める探索に $O(M)$ 、条件を満たす $x$ の範囲を決めるのに $O(N)$ なので、全体で $O(N + M)$

公式解説

躓いた点

値を1つだけ固定ということをせずに範囲で求めようとしていた
$x_{i}$ の例外処理などを上手く整理できずにWA連発

1/24: AtCoder Regular Contest 050 B - 花束

供養

問題

Difficulty: 2131(estimated) (記事作成時点)

解法

花束を $k$ 本作ることを考えたとき、どちらの花束を作るにせよ赤い花も青い花も少なくとも $k$ 本必要
赤い花を $x$ 本使う花束はさらに $x - 1$ 本の赤い花を使うので、最大で $\lfloor \frac{R - k}{x - 1} \rfloor$ 束の花束を作ることができる
同様に青い花を $y$ 本使う花束は $\lfloor \frac{B - k}{y - 1} \rfloor$ 束作ることができる
上記を合わせて $k$ 個作れるかで二分探索

実装は

ある $k$ を考えたとき、 $R \lt k \lor B \lt k$ ならば花束を $k$ 束作れない
ならば花束を束作れる
- そうでなければ作れない
$k$ について上記で二分探索して作成可能な最大値を出力する

計算量は $A = \mathrm{max}(R, B)$ として $O(\mathrm{log}A)$

公式解説

躓いた点

$R \lt k \lor B \lt k$ の境界条件を入れ忘れたことによるWA

1/25: CODE FESTIVAL 2017 qual C D - Yet Another Palindrome Partitioning

供養

問題

Difficulty: 2152 (記事作成時点)

解法

アルファベット各文字の登場回数が奇数のものが高々1つであるような区間が回文を得られる区間
について、文字目までのそれぞれの文字の登場回数の偶奇を記録し、さらに各文字が偶奇どちらかであるかをハッシュにして記録する
- 文字ごとにbitを割り当て、 $2^{26}$ 通りの整数で表せる
が0もしくは2べきとなる区間が回文が得られる区間
- 逆に言えば、 $H_{i}$ に0もしくは2べきでXORを取って出てくるような $H_{j}$ を探せば回文が得られる空間となる

実装は

$1 \le i \le |s|$ について $i$ 文字目までの各文字の登場回数の累積和を作り、その2の剰余を用いてハッシュ $H_{i}$ を作る
$\mathit{DP} \lbrack 0 \rbrack = 0$ 、 $1 \le i \lt 2^{26}$ について $\mathit{DP} \lbrack i \rbrack = |s|$ とする
$1 \le i \le |s|$ について、 $\mathit{DP} \lbrack H_{i} \rbrack = \mathrm{min}( \mathit{DP} \lbrack H_{i} \rbrack, \mathrm{min}(\lbrace \mathit{DP} \lbrack H_{i} \oplus 2^{j} \rbrack + 1 \mid 0 \le j \le 25 \rbrace ))$ で更新する
とする
- $s$ 全体で回文を得られる場合への対応
$\mathit{DP} \lbrack H_{|s|} \rbrack$ を出力する

計算量は1回のDP表の更新で比較対象とするのが定数なので $O(|s|)$ (ただし定数部分に $2^{26}$ )

公式解説

躓いた点

$2^{26}$ 個のstateを保持しながら更新していく発想が出なかった
stateを64bit intで保持したためMLE

1/26: AtCoder Regular Contest 099 E - Independence

供養

問題

Difficulty: 2155 (記事作成時点)

解法

この問題は「グラフ $(V, E)$ を2つのクリークに分割できるか、可能なら2つのクリークのサイズの差を最小化」という問題
グラフを補グラフで見ると「補グラフを二部グラフ $(U, V, E)$ に分割できるか、可能なら2つの点集合のサイズの差を最小化」という問題になる
補グラフの連結成分ごとに二部グラフになるか判定し、2部グラフになるときはどちらを $U$ に含めるかで $U$ のサイズの候補を持っておく
$U$ のサイズを $k$ としたとき、2つのクリークの辺の数の合計は $k(k - N) + \frac{N(N - 1)}{2}$

実装は

補グラフの隣接行列を作成する
$1 \le i \le N$ について $D = \lbrack d_{i} \rbrack$ を $d_{i} = -1$ で初期化する
についてならば、としてから幅優先探索をして連結成分が二部グラフか判定する
- 点 $v$ が発見されたとき、 $d_{v}$ を $i$ からの距離で更新する
- 奇数長閉路があれば二部グラフではないので -1 を出力して終了
連結成分のうち $i$ からの距離が奇数の点集合と偶数の点集合に分割し、それぞれのサイズを $U_{i}, V_{i}$ とする
$0 \le i \le N$ について $\mathit{DP} = \lbrack \mathit{dp}_{i} \rbrack$ を $\mathit{dp}_{0} = 1, \mathit{dp}_{1 \le i} = 0$ で初期化する
各 $U_{k}, V_{k}$ および $0 \le i \le N$ について $\mathit{dp}_{i} = 1$ ならば $\mathit{dp}^{'}_{i + U_{k}} = 1, \mathit{dp}^{'}_{i + V_{k}} = 1$ となるようDPを更新していく
$\mathit{dp}_{k} = 1$ なる $k$ について $k(k - N) + \frac{N(N - 1)}{2}$ を計算し最小値を出力する

計算量は隣接行列による幅優先探索、サイズと更新回数が $O(N)$ のDPなので $O(N^{2})$

公式解説

躓いた点

補グラフを使わずに求めようとしてWA

1/27: AtCoder Grand Contest 027 C - ABland Yard

供養

問題

Difficulty: 2168 (記事作成時点)

解法

AABB の1回以上の繰り返しからなる閉路を作れるならば任意の文字列を作成できる
$\because$ 閉路の中にある頂点は A の頂点にも B の頂点にも移動できる

$1 \le i \le N$ について、 $a_{i}, b_{i}$ をそれぞれ頂点 $i$ とラベル A の頂点との接続数、ラベル B の頂点との接続数とする
空のキューを用意し、についてであるようなをキューに追加する
- グラフから $i$ を取り除くことを意味する
キューから1つ取り出したものをとし、の各隣接点についてならばのうちのラベルと同じほうを1減少させる
- グラフに残った頂点 $v$ の隣接点から $u$ を取り除くことを意味する
上記の操作の結果 $a_{v} = 0 \lor b_{v} = 0$ となった場合、 $v$ をキューに追加する
キューが空になるまで繰り返した後、であるようなが存在すれば Yes を、存在しなければ No を出力する
- 残った頂点は自身も移動先も A の頂点にも B の頂点にも移動できる頂点であり、AABB を繰り返しながら移動すると鳩の巣原理によりいつか閉路を作る
  $\because$ 閉路を作らないためには BA のタイミングで今まで AABB の起点になったことがない A の頂点を選ぶしかないが、そのような頂点はいつか選べなくなる

計算量は $O(N + M)$

公式解説

躓いた点

AABB の閉路検出のみをしていてWA

1/28: 第二回全国統一プログラミング王決定戦予選 C - Swaps

供養

問題

Difficulty: 2178 (記事作成時点)

解法

$A, B$ を昇順にソートしたときの $1 \le i \le N$ 番目の要素 $a^{'}_{i}, b^{'}_{i}$ について $a^{'}_{i} \gt b^{'}_{i}$ だった場合、条件を満たすことはない
上記の場合を除いて、 $1 \le i \lt N$ について $a^{'}_{i + 1} \le b^{'}_{i}$ であるような $i$ が存在するとき、 $a^{'}_{1} \dots a^{'}_{i} a^{'}_{i +1} \dots a^{'}_{N}$ と $a^{'}_{1} \dots a^{'}_{i + 1} a^{'}_{i} \dots a^{'}_{N}$ のどちらかで $b^{'}_{1} \dots b^{'}_{N}$ に対応するように並べ替えれば条件を満たすことができるので $N - 2$ 回以下の置換で達成できる
すべての $1 \le i \lt N$ について $a^{'}_{i + 1} \gt b^{'}_{i}$ であるときも、必要な入れ替えを2つ以上のPermutaionで表現できるときは $N - 2$ 回以下の置換で達成できる
すべての $1 \le i \lt N$ について $a^{'}_{i + 1} \gt b^{'}_{i}$ で、必要な入れ替えを1つのPermutaionでしか表現できないときは $N - 1$ 回の置換が必要

実装は

$1 \le i \le N$ について $A^{'} = \lbrack \lbrack a_{i}, i \rbrack \rbrack, B^{'} = \lbrack \lbrack b_{i}, i \rbrack \rbrack$ として、 $A^{'}, B^{'}$ の要素を $a_{i}, b_{i}$ について昇順にソートする
$1 \le i \le N$ について $a^{'}_{i} \lbrack 0 \rbrack \gt b^{'}_{i} \lbrack 0 \rbrack$ であるような $i$ があれば No を出力して終了
$1 \le i \lt N$ について $a^{'}_{i + 1} \lbrack 0 \rbrack \le b^{'}_{i} \lbrack 0 \rbrack$ であるような $i$ があれば Yes を出力して終了
についてとする
- $a_{j}$ が $A^{'}$ では何番目になるかのマッピング
$s = a^{'}_{1} \lbrack 1 \rbrack, t = b^{'} \lbrack 1 \rbrack, c = 1$ とし、 $s = t$ となるまで $t = b^{'}_{m_t} \lbrack 1 \rbrack$ と更新していき、更新回数だけ $c$ を増加させる
ならば Yes 、そうでないなら No を出力
- あるPermutaionが $N$ より真に小さければ 2つ以上のPermutaionが存在する

計算量は $O(N\mathrm{log}N)$

公式解説

躓いた点

~~公式解説が分かりにくい~~ 判定条件を整理しきれずWA

1/29: AtCoder Regular Contest 031 C - 積み木

供養

問題

Difficulty: 2181(estimated) (記事作成時点)

解法

小さいものから 自身より大きい積み木の数が少ない方向に寄せる という方法で決めていく

$1 \le i \le N$ について $(B_{i}, i)$ を $B_{i}$ の大きさで昇順にソートしたものを $B^{'} = \lbrack B^{'}_{k} \mid B^{'}_{k} = (B_{i_{k}}, i_{k})\; \mathit{if}\; k \lt k^{'}\; \mathit{then}\; B_{i_{k}} \lt B_{i_{k^{'}}} \rbrack$ とする
長さ $N$ のBITを用意し、1で初期化する
$1 \le k \le N$ について、 $\mathit{BIT}_{i_{k}} = 0$ に更新し、 $i_{k}$ より左にある1の個数と右にある1の個数のうち小さい方を足していき合計を出力する

計算量は $O(N\;\mathrm{log}\; N)$

公式解説

躓いた点

各点についてそれより左を昇順、右を降順ソートしたときの転倒数の和の最小値を求めていたがWA

1/30: AtCoder Regular Contest 013 C - 笑いをとれるかな？

供養

問題

Difficulty: 2184(estimated) (記事作成時点)

解法

Nimの解き方を知っていれば簡単

について、以下をそれぞれ求める
- $x_{i}^{\mathit{max}} = X_{i} - 1 - \mathrm{max}( \lbrace x_{i, j} \mid 0 \le j \le M_{i} - 1 \rbrace )$
- $x_{i}^{\mathit{min}} = \mathrm{min}( \lbrace x_{i, j} \mid 0 \le j \le M_{i} - 1 \rbrace )$
- $y_{i}^{\mathit{max}} = Y_{i} - 1 - \mathrm{max}( \lbrace y_{i, j} \mid 0 \le j \le M_{i} - 1 \rbrace )$
- $y_{i}^{\mathit{min}} = \mathrm{min}( \lbrace y_{i, j} \mid 0 \le j \le M_{i} - 1 \rbrace )$
- $z_{i}^{\mathit{max}} = Z_{i} - 1 - \mathrm{max}( \lbrace z_{i, j} \mid 0 \le j \le M_{i} - 1 \rbrace )$
- $z_{i}^{\mathit{min}} = \mathrm{min}( \lbrace z_{i, j} \mid 0 \le j \le M_{i} - 1 \rbrace )$
求めた値すべてのXORをとって、結果が0なら LOSE 、そうでないなら WIN を出力
- 6方向から削れる量を独立に取るのでNimと同値になり、Nimは対象となる数字のXORで勝敗がわかる

計算量は $O(\sum_{1 \le i \le N}M_{i})$ で、 $M = \mathrm{max}(M_{i})$ として $O(MN)$ 、もしくは $M$ を定数として $O(N)$

非公式解説

躓いた点

Nimの性質を知らなかった

1/31: AtCoder Grand Contest 021 B - Holes

供養

問題

Difficulty: 2191 (記事作成時点)

解法

頂点集合の凸包を選び、凸包の任意の頂点から時計回りに $p_{1}, \dots, p_{m}$ とする
について、の外心との中点 , の中点からなる角の大きさを求め、を穴に落ちる確率とする
- $R$ が十分大きいため、凸包の頂点でない穴に落ちるような確率は許容誤差以下となるので0としてよい
- 同様に、凸包の頂点の穴に落ちる確率も凸包の頂点でない穴に落ちる分の誤差を無視できる
$1 \le i \le N$ について穴 $i$ に落ちる確率を順に出力する