第10回 アルゴリズム実技検定 バチャ録

83:42+2ペナで完走しました.

A - 3枚のカード (5:03 (+5:03))

格好付けて minmax_element で出力しようとしたら色々おかしくなって原因を探ったりしてたら 5 分掛かった (?)

B - 花束 (6:00 (+0:57))

赤と青でそれぞれ花束を作ると誤読して $\lfloor X/A \rfloor + \lfloor Y/B \rfloor$ を出力するコードを書いたら合わない.よく読むと和じゃなくて $\min{\lfloor X/A \rfloor, \lfloor Y/B \rfloor}$ だった.

C - Go Further (8:47 (+2:47))

ちょっと面倒.$\lfloor \log _ {10} \alpha \rfloor \bmod 3$ で場合分け.

D - ハイスコア (11:06 (+2:19))

差分更新の問題だと思ってコードを書き上げてから愚直でいいことに気付いた.ただ,この問題は愚直より差分更新の方が楽そう.

E - 良い日付 (17:56 (+6:50))

こういう問題が出ると困ってしまう.Python の datetime にこういうのがあるので,検索して使い方を見ながら書いた.

答えの上限は 3000/03/03 なので,日付を $1$ つずつ試しても高々 $366\times 100 + 100$ 回の操作で終わる.余裕かと思って生 Python で出すと 601 ms で焦った.

F - 地図の塗り分け (20:50 (+2:54))

こういうのは $4$ 隣接のうち $[0,H)\times [0,W)$ に含まれるものだけを列挙する便利ライブラリを用意しておくと楽だと思います.

G - 方程式 (32:11 (+11:21))

まず二分法が思い浮かぶ.初めは $x$ 軸に接するケースをケアしないといけないと思ったけど,$f' = 0$ となるのは $x ^ 4 = -b/5a$ のときで,制約から $-b/5a \lt 0$ が分かるので実はケアしなくても良い.次にケアする必要があるのは $f(1) = 0$ や $f(2) = 0$ となるケース.これは,二分法の初期区間を $[1 + \varepsilon, 2 - \varepsilon]\ (\varepsilon = 10 ^ {-10})$ とすることで回避できる.

あとで気付いたけど,$f(1)=f(2)=0 \Rightarrow 31a+b=0$ の一方で $a,b\gt 0$ だから結局 $f(1)\neq 0$ または $f(2) \neq 0$ が成り立って,つまり符号を確定できるので $\varepsilon$ だけずらしたりしなくても良かったかも.

H - 連結成分 (35:12 (+3:01))

貼るだけ.

連結成分を取得できる Union Find | cp-library-cpp

BFSをすると,密な連結成分ばかり指定された場合に計算量が壊れるので注意.

I - 対称変換 (42:29 (+7:17, 1 WA))

$y$ 軸に平行な直線で対称移動すると,$S$ の $x$ 座標最小の点は $T$ の $x$ 座標最大の点に移るはずなので,対称軸が一意に定まる.$x$ 座標と $y$ 座標を入れ替えて $2$ 回試すことで $x$ 軸に平行な直線での対称移動を考慮できる.

ソート忘れで 1 WA.

J - 区間の期待値 (45:20 (+2:51))

$A$ をソートすると,寄与が簡単に書ける.総和は $\displaystyle \sum _ {i = 1} ^ {N} A _ i \cdot \binom{i - 1}{K - 1} - \sum _ {i = 1} ^ {N} A _ i \cdot \binom{N - i}{K - 1}$ になるので,これを $\displaystyle \binom{N}{K}$ で割ったものが答え.

K - 旅行計画 (50:39 (+5:19))

問題文で与えられている有向グラフ $G$ と,辺を逆向きに張った有向グラフ $H$ を構築する.$G$ における $1$ から $k$ までの最短距離と $H$ における $N$ から $k$ までの最短距離の和が答え.ただし,どちらか一方で到達不可能なら $-1$ を出力.

L - N mod M (57:12 (+6:33))

厄介なのは $\underbrace{1\cdots 1}_{d個} = \dfrac{10 ^ d - 1}{9}$ を $\mathrm{mod}\ M $ で計算したくなる点 ($\mathrm{mod}\ M $ において $9$ の逆元が存在するとは限らない).

ただ,これも繰り返し二乗法の要領で半分に割って再帰的に計算すれば $\Theta( (\log d) ^ 2)$ で計算出来る.$10 ^ d$ の計算も同時にやれば $\Theta(\log d)$ に落とせるが,この問題では $\Theta( (\log d) ^ 2)$ で十分だった.

M - ランキング (63:13 (+6:01) )

Binary Trie や平衡二分探索木などを使えばよい.Binary Trie で適当にやったら 2499 ms で冷や汗.

N - 400億マス計算 (65:28 (+2:15) )

畳み込んで非零の係数を数える.

O - 3-順列 (83:42 (+18:14, 1WA) )

$(A _ i, B _ i)$ に辺を張ったグラフを構築する.各連結成分に関して,それが二部グラフでなければ,その成分に属する頂点は全て $3$ で割った余りが $0$ でなければならない.一方で,二部グラフであれば,彩色時に色 $0$ で塗った頂点数を $X$,色 $1$ で塗った頂点数を $Y$ とすれば,次の $3$ つの可能性がある.

  1. $X+Y$ 個の頂点は全て $3$ で割った余りが $0$
  2. $X$ 個の頂点は $3$ で割った余りが $1$,$Y$ 個の頂点は $3$ で割った余りが $2$
  3. $X$ 個の頂点は $3$ で割った余りが $2$,$Y$ 個の頂点は $3$ で割った余りが $1$

あとは,部分和問題なので $\Theta(N ^ 3)$ の DP が生える.bitset で高速化出来る形なので,$w$ をワードサイズとして $\Theta(N ^ 3 / w)$ へと計算量を削減でき,これは十分高速.

彩色パートのBFSで実装をミスっていたのと,$1,\ldots, N$ を $3$ で割った余りを集計するパートで間違えて $0,\ldots, N-1$ を $3$ で割った余りを集計するミスがあり,1WA.同時に両方見つけられて良かった.