2022-04-24

108. 昨日と今日解いた問題（2022.04.24）

問題一覧

C - Coprime Set (Diff: 1151)
E - Multiplication 4 (Diff: 1607)
E - Lucky 7 Battle (Diff: 1609)

自分の解法など

C - Coprime Set

素数の積で数を構成しながら考えてみます。とりあえず $N=3$ で考えると、 $A = ( 2 \times 3, 3 \times 5, 5 \times 2)$ のような数列は条件を満たします。

ここから $N$ を増やしていくことを考えます。第 3 項までで全体の $\gcd$ が $1$ になることは確定しているので、任意の項と共通約数を持つように数列を構成することのみ考えればよいです。言い換えると、 $(2, 3, 5)$ のうちいずれか 2 つを約数に持つ数を追加していけばよいです。

ここで問題となるのが $1 \le A_i \le 10000$ という条件です。先程述べたような構成方法で第 $2500$ 項まで作れるのかが問題になります。これを証明するのは面倒なので、 $10000$ までの自然数で $(2, 3, 5)$ のうちいずれか 2 つを約数に持つ数がいくつあるのか、プログラムで算出してしまいます。すると、 $2666$ 個存在するので、問題なく構成できることが分かりました。

E - Multiplication 4

負の数が含まれていなければ、降順に取っていくのが明らかに最適です。負の数が含まれている場合でも偶数個選択で正にできるので、この方針で考えてみます。

まず、 $A$ を絶対値の大きな順に並べ直します。また、要素の正負が問題になってくるので対応する sign 配列も作っておくと便利です。

ここから $K$ 個順に取って、積が非負になればそれが答えです。以下、負になった場合を考えます。このとき、

$K$ から順に見て $1 \le i_1 \le K$ で $A_{i_1} \gt 0$ である要素と、 $K+1$ から順に見て $K+1 \le j_1 \le N$ で $A_{j_1} \le 0$ である要素を入れ替える
$K$ から順に見て $1 \le i_2 \le K$ で $A_{i_2} \lt 0$ である要素と、 $K+1$ から順に見て $K+1 \le j_2 \le N$ で $A_{j_2} \ge 0$ である要素を入れ替える

のどちらかを行えばよいことが分かります。この操作の狙いは、「積が負になってしまう原因である要素のうち絶対値が最小のものを追い出し、積を正にしてくれる要素のうち絶対値が最大のものを採用する」です。

どちらかのみ実行可能であればそれを行えばよいですが、どちらも実行可能であれば、 $\left| \frac{A_j}{A_i} \right|$ （採用要素の変更後、残る積の割合）が大きくなる方を行うのが最適です。2つ挙げた中で上の操作を行う場合を考えると、 $\frac{-A_{j_1}}{A_{i_1}} \gt \frac{A_{j_2}}{-A_{i_2}}$ が条件です。浮動小数点数を扱いたくないので、式変形して $A_{j_1}A_{i_2} \gt A_{j_2}A_{i_1}$ であることが条件と言い換えます。

以上の操作後、先頭から $K$ 項の積を取れば答えになります。

最後に例外処理として、両方の操作が実行不可能である場合はどうしても答えが負になるので、小さい方から $K$ 項の積が答えです。

E - Lucky 7 Battle

7の倍数であるかが重要なので、 $\pmod{7}$ で考えます。 $i$ までの要素をみたときの剰余が $a$ だった場合、 $i+1$ の要素で $b$ を採用したときに $10a + b \equiv 3a + b \pmod{7}$ となります。このように考慮すると、 $dp[N, 7]$ のような配列で状態を見ることができます。

$dp[i文字目まで見た, (i-1)文字目まで見たときの剰余] := (1:高橋くんの勝ち, 2:青木くんの勝ち)$

とすると、 $0 \le j \le 6$ について、

ターン目が高橋くんの手番
- $3j \equiv 0$ または $3j + S_N \equiv 0$ ならば、 $dp[N, j] = 1$
- それ以外ならば、 $dp[N, j] = 2$
ターン目が青木くんの手番
- $3j \not\equiv 0$ または $3j + S_N \not\equiv 0$ ならば、 $dp[N, j] = 2$
- それ以外ならば、 $dp[N, j] = 1$

とできます。ゴールから遡っていくことを考えると、 $N - 2 \ge i \ge 0$ について、

ターン目が高橋くんの手番
- $dp[i+1, 3j] = 1$ または $dp[i+1, 3j + S_i] = 1$ ならば、 $dp[i, j] = 1$
- それ以外ならば、 $dp[i, j] = 2$
ターン目が青木くんの手番
- $dp[i+1, 3j] = 2$ または $dp[i+1, 3j + S_i] = 2$ ならば、 $dp[i, j] = 2$
- それ以外ならば、 $dp[i, j] = 1$

とスタートまで状態を伝播できます。 $dp[0, 0]$ が答えで、計算量は $O(7N)$ です。

2022-04-23

107. AtCoder参加記録（AtCoder Beginner Contest 249）

プログラミング AtCoder

16回参加でレート 1056 です。

そろそろパフォーマンス全部載せるのが厳しくなってきたので、今回分のみ。

今回はパフォーマンス 1204 です。

ABCDを通して、EGExは未解答です。Fは通せず。Dでとても痛い2ペナ。

各問題の感想など。

A

5分23秒。

いや、普通に難しすぎる。

入力が横に長過ぎて用意していたユーティリティでは間に合わなかったので、入力のパースから書いてました。そこからも割と難しくて、1秒ずつシミュレートして実装しました。歩く時間と休憩時間を足した剰余で今が歩く時間か判定する感じです。

B

3分25秒。

char 配列にバラして HashSet に突っ込み、長さが一致していることが必要条件。あとは大文字と小文字が両方含まれているか確認すればOK。

C

12分14秒。

問題文が意味不明で、何度考えても理解できなかったので書かれているとおりに実装することにしました。

好きな個数選ぶ → bit全探索

というわけで、ここから英小文字の種類ごとに Dictionary を作って $K$ 個登場した数を数えて最大値を出力。アルファベットの種類数を $A$ として $O(AN2^{N})$ で間に合いそうなのでこれでOK。問題文を考えている時間が無駄だった…。

D

初回提出25分41秒、最終提出41分0秒（2ペナ）。

今回の最悪ポイント。 $A_i = A_jA_k$ のような形で考えて、これを満たす組がいくつあるか、という問題にしました。重複ありなので数列の要素がそれぞれいくつ登場するのか、ということが重要になるのでそれを Dictionary で保持。ここから、要素の昇順に見ていって、 $A_j \times A_k$ を計算し、この答えが $\max A$ 以上であれば早々にループを抜けてよいです。

あんまり計算量を見積もれていなかったのですが、約数の少なさとループの早期脱出からたぶん間に合うでしょ、と提出。すると 1WA。全部 1 とか特殊ケースで引っかかってるのかな…といろいろ考えるも、手元のテストは全部合ってそう。よくよく見ると、計算途中で int 同士の掛け算になっている箇所があり、最悪ケースを考えると int では足りない値が出ることに気付き、ここを直すだけで通せました…。

ちなみに、一発で通せていればパフォ 1394 だったみたいです。悔しすぎる。

E

順位表を見るとどうも F の方が簡単らしい、ということに気づいたのでパス。

F

貪欲法で行けそう？と思って、枝刈りBFSを書きました。TLEしました。終わり。

G,Ex

見てないです。

このA問題はちょっと酷くないですか…という印象の強いコンテストでした。自分のことでいうと、パフォーマンスが若干頭打ち感あって、スランプとまでは行かないですが伸び悩み時期が来ている気がします。単純に問題数をこなせていないと思うので、地道にやっていくしかないですね。

2022-04-19

106. 昨日と今日解いた問題（2022.04.19）

プログラミング AtCoder

問題一覧

E - K-colinear Line (Diff: 1292)
E - Chain Contestant (Diff: 1413)

自分の解法など

E - K-colinear Line

前回ABCのE問題。普通にアプローチを知らなくて解けなかった系なので、じっくり考えながら進めました。

問題のアプローチについて

まず、幾何の問題は（演算の簡潔さ・使える道具の数から）ベクトルに落とし込むことが多いようです。というわけで、2 点 $A, B$ を通る直線は、実数 $k$ を用いて $\overrightarrow{OA} + k\overrightarrow{AB}$ と表現します。これを整理すると、 $A \neq B$ という前提で、 $(x_B - x_A)(y - y_A) = (x - x_A)(y_B - y_A)$ という方程式が出てきます。これを満たす $(x, y)$ は直線上に乗っています。また、入力は全て整数なので、整数で判定を完結できます。これで誤差を考える必要はなくなりました。

今回は $N \le 300$ なので、「2 点の組」を全て走査して直線を作った上で、全ての点を走査してその直線上に乗っているかの計算を行っても間に合います。つまり、 $O(N^3)$ で解くことにします。

直線の表現について

3 つ以上の点が同一直線上に乗っている場合、先ほどの解き方では重複した直線が出てきます。問われていることを考えると、重複したものは弾く必要があります。ここで直線を表現する方法が問題になります。

先ほどの方程式をもう一度整理すると、 $x_A \neq x_B$ のとき、傾き $\displaystyle \frac{y_B - y_A}{x_B - x_A}$ 、切片 $\displaystyle \frac{-x_A y_B + x_B y_A}{x_B - x_A}$ であることが分かります。よって、これらを直線の情報として扱えばよさそうです。

しかし、誤差の問題から浮動小数点数はなるべく扱いたくないです。そこで、既約分数にして分子・分母を整数で保持することで、整数 4 つで直線を表現することを考えます。 $a = y_B - y_A, b = -x_A y_B + x_B y_A, c = x_B - x_A$ として、2 点 $A, B$ を通る直線は、

$x_A \neq x_B$ のとき、 $\displaystyle \left( \frac{a}{\gcd(a, c)}, \frac{b}{\gcd(b, c)}, \frac{c}{\gcd(a, c)}, \frac{c}{\gcd(b, c)} \right)$
$x_A = x_B$ のとき、 $\displaystyle ( x_A, x_A, 0, 0 )$

と表現できます。これを Tuple として表現します。C# では Tuple は HashSet や Dictionary のキーに使えるようなので、HashSet で持っておけば重複チェックできます。

この問題の教訓としては、

幾何はベクトルで考えたい
なるべく浮動小数点数を使わないようにする
直線の表現方法、有理数は既約分数にすればいい感じに扱える
Tuple って HashSet や Dictionary のキーにできたんだ…

という感じです。めちゃくちゃ収穫が多かったです。

E - Chain Contestant

発想10分ほど、実装1時間ほど…。

問題文がややこしいので、問われていることをしっかり理解するところから。入力例 1 を見ると 13 通り。長さ 4 の入力に対して全ての選び方は 15 通り（ $2^4 - 1$ ）なので、BGB と BGBH のみがダメだということがわかります。つまり、BGH や GBH はよいです。

とりあえず DP っぽいです。1 文字ずつ見ていくとして、今までに採用していない文字であれば取ることができます。ということは、「ある文字が今までに採用されているか」が状態の 1 つで、これはビットで表現すればよさそうです。扱うのは 10 文字なので、 $2^{10} = 1024$ の状態数です。また、「今までに採用した文字」であっても「直前に採用した文字」であれば取れます。これも状態に加えます。いわゆる bitDP の問題です。

DPテーブルの定義は、

$dp[i文字目まで見た, 今まで採用した文字(bit表現), 直前に採用した文字] := 通り数$

です。 $(N + 1) \times 2^{10} \times 11$ の状態数なので大丈夫そうです。なお、直前に採用した文字が無い場合はインデックス 10 を利用することにします。よって、初期状態は $dp[0, 0, 10] = 1$ 、それ以外 $0$ です。

この問題で難しいのは遷移で、ちゃんと頭を整理して考える必要があります（ここに50分くらいかかりました）。 $i$ 文字目を見ているとして、

「採用しない」選択はいつでもOK
- $dp[i, j, k] = dp[i-1, j, k]$
文字目が今まで採用した文字に含まれないなら、「採用する」選択はOK
- $dp[i, j \; or \; 2^{S_i}, S_i] = dp[i-1, j, k]$
文字目が今まで採用した文字に含まれないなら、最後に採用した文字が等しい場合のみ「採用する」選択はOK
- $dp[i, j, S_i] = dp[i-1, j, S_i]$

ただし、同じ状態に複数回演算を行う可能性があるので、（分かりやすさのため）代入のように表現していますが常に加算することに気をつけます。

答えは $\displaystyle \sum_{j = 1}^{2^{10} - 1} \sum_{k = 0}^{9} dp[N, j, k]$ です。

扱う文字の種類数を $A$ として、計算量は $O(N \cdot 2^{A} \cdot A)$ です。この問題では $A=10$ 。

2022-04-17

105. 昨日解いた問題（2022.04.17）

プログラミング AtCoder

問題一覧

D - Handstand (Diff: 1138)
E - Train (Diff: 1135)
D - Grid Components (Diff: 1445)
E - Stronger Takahashi (Diff: 1423)

自分の解法など

D - Handstand

24分。

連続で並ぶ 1 の数を増やす必要があるので、反転させる区間は全て 0 であるのが最適です。この問題を言い換えると、「連続して 0 が並ぶ区間のうち、最大 $K$ 個を選択して反転させた結果、最大で何個の 1 を連続して並べられるか」です。連続して並ぶ数を増やしたいので、選択する区間は（1 の区間を除いて）連続である必要があります。ここまで来ると、しゃくとり法的なイメージが出てきます。

$S$ をランレングス圧縮する
（1 の区間を除いて）連続な 0 の区間を最大 $K$ 個選択して、1 が連続で並ぶ最大数をしゃくとり法的に探索する

という感じで解けます。最大 $K$ 個というのが厄介そうに見えますが、選択できる最大数を選択する方が明らかによいので、最初の方の $K$ 個に満たない区間に気をつけるだけです。

計算量は $O(N)$ 。

E - Train

14分。

出発点が決まっていて、コスト（所要時間）が正なのでダイクストラ法を使いたくなります。ただし、各列車の出発タイミングが決まっているので、単純な方法では無理です。

ダイクストラ法でコスト最小の頂点から次の頂点へ向かうコスト計算に、このタイミング計算を組み込みます。現在の頂点へ到達できる最小コストを $c$ 、列車の出発タイミングを $k$ 、所要時間を $t$ とすると、次の頂点へ到達したときの総コストは $\lceil \frac{c}{k} \rceil \cdot k + t$ です。

計算量は $O( (N + M)\log (N) )$ 。

D - Grid Components

40分。

よく分からないので、 $A = 1, B = 1$ から始めて 1 つずつ増やしていく方法を考えてみます。たとえば $A$ を 1 つ増やしたければ、黒マスの海の中に 1 つ白を作ればよいイメージです。以下のような初期状態を考えます。

f:id:ibako_piyo:20220416174927p:plain — 初期状態

初期状態は $A=1, B=1$ です。ここから $A=3, B=4$ という状態を作りたければ、以下のように点を打っていけばよさそうです。

f:id:ibako_piyo:20220416175143p:plain — $A=3, B=4$

このような手順で考えます。なお、複数行に渡る場合は以下のように打てばよさそうです（盤面の大きさを変えています）。

f:id:ibako_piyo:20220416175459p:plain — $A=8, B=1$

ところで、この手順で大丈夫なのでしょうか。白点を打っているのに白の海に突入したり、連結したりすると破綻してしまいます。ここで最悪状態を考察します。どのような条件でも $100 \times 100$ の盤面を取った方がよいので、その前提で考えます。

$A, B \le 500$ なので、たとえば白は下から $2 \times \lceil \frac{499}{50} \rceil - 1 = 19$ 行目までを使います。黒で塗りつぶすのは下から 50 行目までなので、十分足りています。黒についても同様です。よって、問題ないことが分かりました。

E - Stronger Takahashi

25分ほど。解いている途中で自作 Deque のバグに気付き、修正していました。

塀を壊さずに到達できる範囲はコスト 0 です。塀を壊して到達できる範囲はコスト 1 です。ということで、01-bfs で解ける問題です。

現在位置から上下左右に移動しようとして、塀が無い場所はコスト 0 とみなします。塀がある場所は、その塀を壊した上で移動可能な範囲がコスト 1 になります。たとえば、以下の画像で緑が現在位置だとして、上に塀がある場合は青の範囲がコスト 1 になります。

f:id:ibako_piyo:20220416180948p:plain — 緑の上に塀があるとき、コスト 1 で移動できる範囲（青）

（厳密に言うと上の図は若干違ってたりしますが、上下左右見るならこの範囲で考えればよいです）

計算量は $O(HW)$ 。

2022-04-16

104. AtCoder参加記録（AtCoder Beginner Contest 248）

プログラミング AtCoder

15回参加でレート 1035 です。

f:id:ibako_piyo:20220416231256p:plain

f:id:ibako_piyo:20220416231325p:plain

今回はパフォーマンス 1188 です。

ABCDを通して、FGExは未解答です。Eは通せず。

f:id:ibako_piyo:20220416231415p:plain

各問題の感想など。

A

2分6秒。

数列に分解して HashSet から除外して残ったものを出すようにしました。

B

2分2秒。

倍々ゲームなので早々に決着します。というわけで、計算量を深く考えなくても普通にシミュレーションすればOK。

C

13分55秒。

割とややこしいDPです。 $dp[i 番目まで見た, 総和が j ] := 通り数$ 。

遷移は、 $\displaystyle dp[i, j] = \sum_{k=\max(1, j-M)}^{j - 1} dp[i - 1, k]$ 。

初期状態は、 $dp[1, j] = 1 (1 \le j \le M)$ 、 $dp[1, j] = 0 (M \lt j \le K)$ 。

計算量は $O(NKM)$ です。

D

14分33秒。

数列に登場した数ごとに、前から順にインデックスリストを作っておきます。クエリでは二分探索で条件を満たす（インデックスリストにおける）最大インデックス・最小インデックスを出せば、答えを求められます。

計算量は $O(N + Q \log N)$ 。

E

$K = 1$ のとき明らかに Infinity です。また、 $K \ge 2$ であれば直線は一意に定まります。

2点を取って直線を算出し、ここから重複したものを省けばよいとは思いましたが、何か無限にバグらせていて 3WA で撃沈。幾何を久々に見たので、ちゃんと復習しておきます…。Diff 的にも解きたい問題でした。

F

Eを見て嫌な予感がしたのでこっちも見てみましたが、少し考えて青Diffっぽさを感じたのでやめました。

G,Ex

見てないです。

C をもう少し早く通したかったのと、E は普通に悔しいな、と思いました。水パフォ出せるようにならないと…。

2022-04-15

103. 今日解いた問題（2022.04.15）

プログラミング AtCoder

問題一覧

D - Lamp (Diff: 1103)
E - Simple String Queries (Diff: 1443)

自分の解法など

D - Lamp

12分。

累積和的な処理で解けないかな、と考えました。たとえば「#....#」となっている箇所は、「012340」という風に置き換えられます。これを、その場所に明かりを置いたとき照らせるマスの数と考えると、「044440」が適切です。ということは、左から累積和的なものを作ったあと、右から「最大値」（ただし、0で囲まれた範囲で）で上書きしていけばよさそうです。

行方向・列方向でそれぞれこの処理を走らせて得られた配列を $A, B$ とします。 $(i, j)$ に明かりを置いたとき照らせるマスの数は $A_i + B_j - 1$ なので、これの最大値を全探索すればよいです。

というわけで、最初の累積和的な処理が $O(H + W)$ 、最後の全探索処理が $O(HW)$ で全体として $O(HW)$ です。

E - Simple String Queries

13分。

いかにもセグ木を使いたくなる問題です。クエリ 1 はセグ木を使えば $O(\log N)$ で更新できるのでよさそうです。クエリ 2 にどうやって対応するか考えます。

アルファベットがそれぞれ含まれる・含まれないという状態をビットで管理できないか考えます。26文字なので int で十分管理できます。この上で考えてみると、セグ木のデフォルト値を 0、子 $(x, y)$ から親への更新演算を $x \; or \; y$ とすればよいことが分かりました。クエリ 2 には、セグ木から得られた値で 1 となっているビットの数を答えとして出力すればよいです。

セグ木構築とクエリ処理のどちらかがボトルネックとなり、計算量は $O(N \log N + Q \log N)$ です。

2022-04-14

102. 今日解いた問題（2022.04.14）

プログラミング AtCoder

本日より、問題を開いてから AC まで掛かったおおよその時間も記録しようと思います。

問題一覧

D - Harlequin (Diff: 1106)
E - Colorful Blocks (Diff: 1442)
E - Friendships (Diff: 1433)

自分の解法など

D - Harlequin

8分。

各色のりんごの残りを $b_i$ 個とします。任意の $i$ について $b_i = 0$ または $b_i = 1$ であるとき、 $b_i = 1$ であるりんごを全て食べれば勝てます。 $b_i \ge 2$ であるりんごがあるとき、この色のりんごは1ターンで食べきれないので、このターンでは勝てません。よって、相手の行動によって「必勝パターン」を作らせれば勝てます。

少し考察すると、「相手に偶数を押し付ければ必勝パターンに持ち込める」ことがわかります。奇数になっているりんごを食べて偶数にする、という行動を繰り返せば勝てます。よって、基本的に先手必勝です。ただし、最初のりんごが全て偶数だった場合のみ、先手が奇数を作らざるを得ないので後手が勝ちます。

以上より、「 $a_i = 1 \pmod 2$ である $i$ が存在するなら先手の勝ち、それ以外なら後手の勝ち」です。計算量は $O(N)$ 。

E - Colorful Blocks

15分。

まず、隣り合うブロックが全て異なる色で塗られているパターンを考えます。最初は $M$ 色で塗れて、その次は最初に選んだ色以外 $(M - 1)$ 色で塗れて、さらにその次は前に選んだ色以外 $(M - 1)$ 色で塗れて…となるので、 $M(M-1)^{N-1}$ 通りです。

次に、 $i$ 組同じ色で塗られているパターンを考えます。このような組は ${}_{N-1}C_i$ 通り考えられます。組にしたブロックを 1 つにして考えると、 $(N - i)$ 個のブロックを隣り合うものが異なる色になるように塗るパターン数を求める問題になります。以上より、 $({}_{N-1}C_i)M(M-1)^{N-i-1}$ 通りです。

出力する答えは $\displaystyle \sum_{i=0}^{K} ({}_{N-1}C_i)M(M-1)^{N-i-1}$ です。Combination の計算は、ループごとに分子・分母に数値を1つずつ掛けていくことで定数時間で行えます。計算量は $O(K)$ 。

E - Friendships

20分。

よく分からないので図を書いて考えてみます。 $N=4$ くらいで考えましょう。 $K=0$ のとき、完全グラフが条件を満たします。

f:id:ibako_piyo:20220414220446p:plain — $K=0$

ここから少しずつ辺を削って、 $K \ge 1$ のグラフを作れないか考えてみます。まず、現在隣り合っている頂点の組を列挙すると、

$(1, 2), (1, 3), (1,4)$
$(2,3),(2,4)$
$(3,4)$

です。

$K = 1$ の場合、 $(3, 4)$ の辺を消せばよいです。

f:id:ibako_piyo:20220414220631p:plain — $K = 1$

$K = 2$ ですが、 $(2, 4)$ を消せばよいです。…と考えると、最初に列挙した「完全グラフで隣り合う頂点の組」を逆に削っていけば $K$ の値を増やせることに気付きます。ただしグラフは連結であるという条件があるため、頂点 $1$ との組は削れません。そして、ここが $K$ の上限値です。

f:id:ibako_piyo:20220414221008p:plain — $K=3$

まとめると、

$K \gt \frac{N(N-1)}{2} - (N - 1)$ であれば不可能
それ以外なら、上記手順で完全グラフから順に辺を削ったグラフが答え

となります。完全グラフ構築に最も時間がかかり、計算量は $O(N^2)$ です。