2023-01-20

AtCoder Beginner Contest 285 メモ

コンテストページ:AtCoder Beginner Contest 285 - AtCoder

コンテスト中AC:A〜D
コンテスト後自力AC:E,F

D - Change Usernames
E - Work or Rest
F - Substring of Sorted String

D - Change Usernames

ユーザ名の重複を取り除き、番号を振り直したものを $s=\{s_0,\ s_1,\ \cdots\ ,\ s_m\}$ とします。

$s_i$ から $s_j$ に、 $s_j$ から $s_k$ に変更することを考えます。
配列の途中に要素を挿入する場合に末尾要素から順に後ろにずらしてスペースを作りますが、同じように、 $s_j$ を $s_k$ に変更してから $s_i$ を $s_j$ に変更すれば、2つの変更を達成できます。

達成できない場合を考えると、例えば、 $s_i$ から $s_j$ に、 $s_j$ から $s_k$ に、 $s_k$ から $s_i$ にする変更は不可能です。

これらの関係を有向グラフの問題にすると見通しが良くなります。

$s$ の各要素を頂点、 $s_i$ から $s_j$ に変更したい場合に $s_i$ を始点、 $s_j$ を終点として有向辺を張ります。ユーザ名の変更は、有向辺を一回辿ることと考えることができます。

この有向グラフに閉路があると、移動順を決められず、達成できないことがわかります。逆に閉路がない場合、トポロジカルソートして、末尾から順に移動すれば達成できます。

従って、このグラフに閉路存在するかを判定すればよいです。
コンテストでは、AtCoder Libraryの強連結成分分解を使いました。
実装: Submission #38053494 - AtCoder Beginner Contest 285

E - Work or Rest

連勤する日数に対して、得られる生産量は固定です。

例えば3連勤すれば $A_1+A_2+A_1$ が生産量です。
これは、 $A$ の累積和をとっておき、連勤する日数の偶奇で場合分けすることで $O(1)$ で計算できます。

この問題では、以下のように考えることができます。

$i$ 連勤に必要な日数を $w_i$ 、 $i$ 連勤で得られる生産量を $v_i$ とする。合計日数が $N$ 以下となるように選んで連勤する時、得られる生産量の最大値を求めよ。但し、各連勤は何度してもよい。

これは個数制限の無いナップサック問題と同じです。連勤日数は最大で $N-1$ 日なので、 $O(N^2)$ で解けます。

注意が必要なのは、 $i$ 連勤に必要な日数は $i$ 日ではないということです。
前か後ろの一方にのみに休日を入れておけば全体として矛盾がないので、 $i+1$ 日としておけば良いです。
実装: Submission #38131229 - AtCoder Beginner Contest 285

F - Substring of Sorted String

$S_l,\ S_{l+},\ \cdots ,\ S_r$ を、 $S_{l,r}$ と表現します。

$S_{l,r}$ が $T$ の連続する部分列であるための条件は以下の2つです。

$S_{l,r}$ が昇順に並んでいる
文字をabc順に並べた時に $S_{l}$ より後ろ、かつ、 $S_r$ より前の文字 $c_i$ について、 $S_{l,r}$ に含まれる $c_i$ の個数と $S$ 全体に含まれる $c_i$ の個数が等しい

1つ目は自明だと思うので、2つ目を具体例で示します。

$S_{l,r}=aabccdf$ とします。
まず、 $S_l = a,\ S_r = f$ は $S_{l,r}$ の先頭と末尾ですが、これは $S$ に何個含まれていても良いです。例えば、 $T$ の連続する部分列が、

$aaabccdfffff$

であったとしても、

$a|aabccdf|ffff$

という感じに分けることを考えれば $S_{l,r}$ に一致させることができることがわかります。

反対に $a$ と $f$ の間の文字、 $b,c,d,e$ は $S_{l,r}$ に含まれる個数と $S$ 全体に含まれる個数が一致しなければいけません。
もし、 $S_{l,r}$ 以外の箇所にこれらの文字が含まれていた場合、昇順ソートして $T$ にした時に、 $S_{l,r}$ の間に1文字以上挿入されることになり、一致しなくなります。

次に、これらの計算方法です。
まず、昇順に並んでるかどうかですが、これは順序付き集合 $U$ で、以下を管理します。

$S$ の連続する部分列であって、その部分列が昇順であるように(最長に)分割した時の、各部分列の開始位置

例えば、 $S=aabcdacfda$ は、 $aabcd|acf|d|a$ と分割できるので、 $U=\{1,6,9,10\}$ となります。

$l,r$ が与えられたとき、 $U$ 上を二分探索し、 $l$ 及び $r$ より大きい最小の整数(upper_bound)が一致すれば、 $S_{l,r}$ は昇順です(実装では、 $\infty$ を $U$ に入れておけば扱いやすいです)。

文字変更クエリでは、 $U$ の中身を変更していきます。変更される可能性があるのは $x,x+1$ の2つです。文字変更によって、新たに昇順になったか、または昇順でなくなったか、に応じて、 $U$ から $x,x+1$ を追加または削除すればよいです。

値の追加、削除、二分探索が可能なデータ構造(C++ならset)を用いれば各クエリで $O(logN)$ で処理できます。

次に、2つ目の条件ですが、これは値の1点更新を伴う区間和を処理できればよいので、Fenwick Treeで対応できます。

なお、2個目のクエリで全ての文字について、その個数を求めたとしても、文字種が26しかないので計算量としては問題ないです。

実装: Submission #38099915 - AtCoder Beginner Contest 285

2022-12-23

AtCoder Beginner Contest 282 備忘録

ABC 最小全域木 Sparse Table 2部グラフ

コンテストページ: HHKB Programming Contest 2022 Winter(AtCoder Beginner Contest 282) - AtCoder
コンテスト後にAC: A〜C
コンテスト後にD,Eは自力で解けず。Fは自力AC

D - Make Bipartite 2
E - Choose Two and Eat One
F - Union of Two Sets

D - Make Bipartite 2

コンテスト中はよくわからない勘違いでACできませんでした。

まず、連結成分に2部グラフでないものが含まれていた場合、辺追加後のグラフも2部グラフにならないので0です(これが抜けていました)。以下、全ての連結成分が2部グラフであるとします。

まず、連結成分内同士を繋ぐ場合の辺の本数を求めます。
連結成分の1つ $C$ について、頂点を2つの独立集合 $U=\{u_1,\cdots ,u_k\}$ と $V=\{v_1,\cdots ,v_m\}$ に分けます。これは頂点を2色彩色した場合に同色となる頂点集合と同じです。

$U$ または $V$ 内で辺を繋ぐと2部グラフでなくなります。 $U$ と $V$ の頂点同士はどのように繋いでも2部グラフのままです。

$U$ の任意の頂点 $u$ について、 $V$ の全ての頂点と辺を繋ぐことが可能なので、合計 $m$ 本の辺を繋ぐことができるわけですが、既に辺が存在する場合はその分を引かなければなりません。

つまり、 $u$ は $m-N(u)$ 本の辺を繋ぐことができます。但し、 $N(u)$ は $u$ から出ている辺の本数とします。
従って、連結成分内で繋げる辺の本数は $i=1,\cdots ,k$ について、 $u_i$ で繋げる辺の本数の総和を求めればよいです。

次に、連結成分間です。
任意の連結成分 $C_i,C_j$ 間では、全ての頂点間の辺を繋ぐことができます。もし、頂点を2色彩色した場合の同色同士を辺で繋いだとしても、一方の連結成分の色を全て反転させればよいです。

よって、連結成分 $C_1,\cdots C_{i-1}$ の頂点数の合計が $S$ であり、 $C_i$ の頂点数が $|C_i|$ だとすれば、 $S\times |C_i|$ 本の辺を繋ぐことができます。
以上から、連結成分間について、連結成分の頂点数の和を順次計算しながら、辺の本数を求めていくことができます。

実装: Submission #37366599 - HHKB Programming Contest 2022 Winter(AtCoder Beginner Contest 282)

E - Choose Two and Eat One

公式解説を見ました。
こういう問題はどうやったら気づけるのか難しいところです。 AtCoderの過去問 (ネタバレ注意)で、似たような感じの木で考える問題もありました。これも葉から順に操作していくというものでした。
1つずつ選んでいく感じの問題は木を疑ってみると良いのかもしれません。

F - Union of Two Sets

公式解説そのままだったので、解法の詳細は省略し、解法に至った経緯だけメモしておきます。

まず、全ての区間の組を得ようとした場合、 $N^2$ 個必要です。ワーストケースの $N=400$ の場合だけを考えても、 $M\leq 50000$ という制約を越えるため、全ての区間を列挙することは不可能です。

そこで、例えば、区間の数を $NlogN$ 個に落とすことができれば、解決できそうです。
そんなわけで、区間の長さを2分の1ずつ小さくすることを考えます。

N=10を例にします。10/2=5なので、長さが5の区間について考えます。全ての長さ5の区間をカバーするためには、始点を1つずつずらす必要があります。そのため、

[1,5] [2,6] [3,7] [4,8] [5,9] [6,10]

が必要です。
これを眺めたところ、ここから適切に区間を2つ選ぶことで長さ5〜10の区間すべてをカバーできることがわかりました。
一般化すると、

長さ $i$ の閉区間について、 $[1,i],\ [2,i+1],\ \cdots , \ [N-i+1,N]$ から適切な2組を選ぶことで、長さ $1,2, \cdots ,2i$ の全ての区間を作ることができる。

また、各長さの区間の個数は $N$ 個以下となることから、全ての区間を列挙しても $NlogN$ 個以下となります。
以上から、 $1\leq 2^i \lt N$ のすべての区間を列挙しておけば、クエリに答えられます。

クエリでは、区間の長さ以下となる最大の2の冪乗について、その指数が必要になります。
これは、ビットが1である最上位のビットが何番目かを得ればよいです(__builtin_clzが使えます)。

実装: Submission #37417443 - HHKB Programming Contest 2022 Winter(AtCoder Beginner Contest 282)

2022-12-15

AtCoder Beginner Contest 281 参加記録

ABC ウェーブレット行列

コンテストページ: https://atcoder.jp/contests/abc281
コンテスト中AC: A〜D
コンテスト後にEをAC(自力)

D - Max Multiple

$N,K,D$ が小さい
倍数は $mod$ の情報があれば良い

これらからDPだろうと判断しました。
情報としては、

何項目までを考慮したか
選んだ項の総和の $mod\ D$
選んだ項の個数

が分かればよいので、

$dp[i][j][k]:=$ $A$ の $i$ 項目までを考慮し、選んだ項の総和の $mod\ D$ が $j$ であり、選んだ項の個数が $k$ であるときの選んだ項の総和の最大値

遷移は以下のとおりです。

$A_{i+1}$ を選ばない場合
$dp[i+1][j][k]\leftarrow max(dp[i+1][j][k], dp[i][j][k])$
$A_{i+1}$ を選ぶ場合
$dp[i+1][(j+A_i)\ mod\ D][k+1]\leftarrow max(dp[i][(j+A_i)\ mod\ D][k+1], dp[i][j][k]+A_i)$

初期値は、 $dp[0][0][0]\leftarrow 0$ としておき、その他は $-1$ などで埋めておけばよいです。

なお、 $dp[i][j][k]$ が $-1$ の場合は遷移元としないようにする必要があることに注意します。

答えは、 $dp[N][0][K]$ です。

提出コード: Submission #37160568 - AtCoder Beginner Contest 281

E - Least Elements

コンテスト中multisetで解こうとして結局だめでした。コンテスト後にWavelet Matrixで解けました。

$A_{i-M+1}$ から $A_i$ までを昇順に並べた数列を $B_i$ とします。 $B_i$ の先頭 $K$ 項の和を $S_i$ とします。

$i=M+1,M+2,\cdots ,N$ について、 $A_{i-M}$ を削除し、 $A_i$ を追加した場合に、 $B_{i-1}$ から $B_i$ にどのように変化したかがわかれば、 $S_{i-1}$ から変化分を増減させることで、 $S_i$ を計算できます。

これを考える時、 $A_{i-M},A_i$ がそれぞれ $B_{i-1},B_i$ の $K$ 番目以内かそうでないかの4通りを考えれば良いです。

具体的に説明します。

$A_{i-M}$ が $B_{i-1}$ の $K$ 番目以内
この時、 $A_{i-M}$ の分、和は減少します。
- $A_{i}$ が $B_i$ の $K$ 番目以内
  $A_{i-M}$ が削除され、 $A_i$ が挿入することを考えると、削除されて空いた箇所に左詰めまたは右詰めで各要素が移動し、 $A_i$ が挿入されたと考えることができます。
  このケースでは、新たに $A_i$ が $K$ 番目以内となってその分の和が増加するので、
  $S_i \leftarrow S_{i-1}-A_{i-M}+A_i$
  と計算できます。
- $A_{i}$ が $B_i$ の $K$ 番目より後ろ
  $A_{i-M}$ が削除されて空いた箇所にそれより後ろの要素が左詰めされて、 $A_i$ が挿入されます。
  このケースでは、 $B_{i-1}$ における $K+1$ 番目の要素が $B_i$ で新たに $K$ 番目となり、この分の和が増加するので、これを $B_{i,K+1}$ とおけば、
  $S_i \leftarrow S_{i-1}-A_{i-M}+B_{i,K+1}$
  と計算できます。
$A_{i-M}$ が $B_{i-1}$ の $K$ 番目より後ろ
このケースでは、 $A_{i-M}$ による和の減少はありません。
- $A_{i}$ が $B_i$ の $K$ 番目以内
  $A_i$ が挿入されると、 $A_{i-M}$ の削除によって空いた箇所に右詰めされるように動きます。このケースでは、新たに $A_i$ が $K$ 番目以内となってその分の和が増加し、 $B_{i-1}$ で $K$ 番目だった要素が $B_i$ における $K+1$ 番目となって、この分が減少するので、
  $S_i \leftarrow S_{i-1}+A_i-B_{i-1,K}$
  と計算できます。
- $A_{i}$ が $B_i$ の $K$ 番目より後ろ
  $A_i$ は和に影響しないので、 $S_i \leftarrow S_{i-1}$
  となります。

$B_i$ を全て記録することは $N^2$ の領域が必要となるので、不可能だと思います。また、仮にそれが可能だとしても、C++のvectorなら昇順ソートが毎回必要ですし、multisetでは何番目の要素かを得るのに時間がかかります。

そこで、Wavelet Matrixを使います。Wavelet Matrixは $O(NlogA_{max})$ で構築し、 $O(logA_{max})$ で指定区間の任意のx番目に小さい要素を得ることが可能です。(但し、 $A_{max}$ は $A$ に含まれる要素の最大値)
これで、 $O(NlogA_{max}+QlogA_{max})$ で解くことができます。

実装: Submission #37188154 - AtCoder Beginner Contest 281

2022-12-09

AtCoder Beginner Contest 280 備忘録

ABC エラトステネスの篩期待値DP 素因数分解

コンテストページ:
コンテスト中AC: A〜E

D - Factorial and Multiple
E - Critical Hit

D - Factorial and Multiple

制約上、 $O(\sqrt{K})$ くらいの解法、すなわち素因数分解や約数を利用した解法を疑います。今回は素因数分解で解けました。

$K$ が素因数 $p$ を1つだけ持つとします。 $N!$ は $K$ の素因数を全て含む必要がありますが、 $p$ は合成数ではないので、2つ以上の正整数の積で表すことができません。従って、少なくとも $p!$ は必要であり、 $N\geq p$ であることが確定します。

$p$ が2個含まれる場合を考えると、 $p!$ の次に $p$ が現れるのは $2p!$ なので、 $N\geq 2p$ が確定します。

一般化すると以下が言えそうですが、これは誤りです。

$K$ に素因数 $p$ が $e$ 個含まれる時、 $N\geq ep$ が成り立つ

反例として、 $K=8$ があります。
2が3個含まれるので、 $N\geq 6$ が必要かといえば、そうではなく、 $N\geq 4$ で達成できます。
これは $p$ の倍数に $p$ が2個以上含まれることによって発生しています。

そこで、以下は成り立つと言えます。

$K$ に素因数 $p$ が $e$ 個含まれるとする。 $p,2p,\cdots ep$ の順に探索し、 $p$ の数が $e$ 個以上に初めてなるものを $kp$ とするとき、 $N\geq kp$ が成り立つ

これを $K$ に含まれる素因数全てについて求めていきます。
$K=p_1^{e_1}\times p_2^{e_2} \times \cdots \times p_m^{e_m}$ と素因数分解されたとすれば、各素因数について前述の値を求め、それらを $x_1,x_2,\cdots ,x_m$ とすると、

$N\geq max\{x_1,x_2,\cdots x_m\}$

が成り立つ必要があるので、 $N$ としてとりうる最小値は $max\{x_1,x_2,\cdots x_m\}$ であり、これが答えです。

かなり大雑把に計算量を見積もります(間違っていたらすみません)。
素因数は2以上なので、素因数の個数の和は $logK$ 個以下です。よって、各素因数について各倍数を調べる部分は合計 $logK$ 回以下です。また、各倍数に含まれる素因数の個数も $logK$ を超えないはずなので、かなり大雑把に見積もっても $O(log^2 K)$ で済みます。

そのため、おそらく素因数分解の計算量がボトルネックとなります。
素因数分解はあまり効率的ではない試し割りであっても、 $O(\sqrt{K} + logK)$ くらいかと思います。(素因数の個数が合計で $logK$ 個以下なので、同じ素因数で複数回割る部分を考慮して $logK$ をつけましたが、不要かもしれません)

提出コード: Submission #36979663 - Denso Create Programming Contest 2022 Winter(AtCoder Beginner Contest 280)

E - Critical Hit

期待値DPの典型的な考え方で解けます。

状態 $u$ が遷移元でその期待値を $E_u$ とする。
状態 $v_1,v_2,\cdots v_m$ に遷移し、
遷移先の期待値が $E_{v_1},E_{v_2},\cdots E_{v_m}$ で、
遷移する確率が $p_{v_1},p_{v_2},\cdots p_{v_m}$ で、
遷移にかかる操作回数が $w_{v_1},w_{v_2},\cdots w_{v_m}$ の時、
$E_u = p_{v_1}(E_{v_1} + w_{v_1}) + p_{v_2}(E_{v_2} + w_{v_2})+\cdots + p_{v_m}(E_{v_m} + w_{v_m})$

今回の場合、体力が $i$ の状態からは、
体力が $i-2$ と $i-1$ の状態に遷移し、
遷移する確率が $\frac{P}{100}$ 、 $\frac{100-P}{100}$ で、
遷移にかかる操作回数が、いずれも $1$ 回なので、

$E_i = \frac{P}{100}(E_{i-2}+1) + \frac{100-P}{100}(E_{i-1}+1)$

この式に従って計算すれば、メモ化再帰やDPなどで解けます。
なお、メモ化再帰では $i\lt 0$ となる場合の処理について注意します。

提出コード: Submission #36983677 - Denso Create Programming Contest 2022 Winter(AtCoder Beginner Contest 280)

計算方法がフィボナッチ数列に似ているので、以下のように考えれば行列累乗で解けそうです。

2022-12-02

AtCoder Beginner Contest 279 備忘録

ABC 左右から計算三分探索下に凸なグラフ Union-FInd

コンテストページ: TOYOTA SYSTEMS Programming Contest 2022(AtCoder Beginner Contest 279) - AtCoder

コンテスト中AC:A〜D
コンテスト後にE,Fを自力AC。

D - Freefall
E - Cheating Amidakuji
F - BOX

D - Freefall

下に凸な関数っぽい感じだったので、下のサイトを参考に三分探索しました。
三分探索を救いたい - Qiita

誤差が出てくるので、出てきた操作回数±10くらいの範囲を探索しました。
一応、ACできましたが、疑問がいくつか残ったままだったので、コンテスト後に調べてみました。

整数の三分探索の方法

公式解説によれば、繰り返しの条件をr - l > 2として、終了後にrからlまでの最小値を答えれば良いようです。
おそらく、3分する点がlと重複しない間は探索を繰り返すものと思います。

探索範囲の最大値

$t\geq \frac{A}{B}$ なら $f(t) \geq f(0)$ となるので解は $\frac{A}{B}$ 以下となる、ということらしいです。詳細は公式解説参照。

下に凸であることの判定

上に凸，下に凸な関数と二階微分 | 高校数学の美しい物語
上記サイトによれば、二階微分が非負整数なら下に凸と判定できるそうです。

ざっくりとした理由をメモしておきます。

まず、一階微分は接線の傾きであり、下に凸の場合単調非減少となる必要があるそうです。確かに、下に凸の二次関数などを例に考えれば、最小値より前は傾きが負で、最小値に近づくにつれてだんだん傾きは小さくなり(0に近づき)、最小値で0になります。そして、その後は傾きは正になり、傾きは大きくなっていくことが想像できます。
そして、傾きが単調非減少になるためには、傾きの変化量は常に非負である必要があるので、二階微分が非負になるということが理解できます。

高校数学から大分遠ざかっていたので、微分を思い出しながら実際にやってみます。

$f(x) = Bx+\frac{A}{\sqrt{x+1}}$

• 一階微分
$Bx$ の項は $B$ になります。

次に $A$ を含む項です。

合成関数の微分を思い出すと、

$u = x+1,\ f(u) = \sqrt{u}$

のとき、

$\{f(u)\}' = f'(u)u'$

です。
$A$ を含む項は、

$\frac{A}{\sqrt{x+1}}=A(x+1)^{-\frac{1}{2}}$

ですから、その微分は、

$A\cdot -\frac{1}{2}\cdot (x+1)^{-\frac{3}{2}}\cdot 1$
$= -\frac{1}{2} A (x+1)^{-\frac{3}{2}}$

よって、

$f'(x)=B-\frac{1}{2} A (x+1)^{-\frac{3}{2}}$

です。

• 二階微分
同様に合成関数の微分を使うことで、

$f''(x) = -\frac{1}{2} A \cdot -\frac{3}{2}(x+1)^{-\frac{5}{2}}$
$= \frac{3}{4} A (x+1)^{-\frac{5}{2}}$

となります。 $x\geq 0$ において、 $f''(x)\geq 0$ が成り立つので、下に凸であることが示されました。

提出コード: Submission #36819682 - TOYOTA SYSTEMS Programming Contest 2022(AtCoder Beginner Contest 279)

E - Cheating Amidakuji

このユーザ解説と同じ方法でした。

実装: Submission #36848977 - TOYOTA SYSTEMS Programming Contest 2022(AtCoder Beginner Contest 279)

F - BOX

公式解説と同じ方法でした。

実装: Submission #36835935 - TOYOTA SYSTEMS Programming Contest 2022(AtCoder Beginner Contest 279)

2022-11-25

AtCoder Beginner Contest 278 備忘録

ABC ゲーム巡回セールスマン問題ビットDP 二次元累積和後退解析

コンテストページ:AtCoder Beginner Contest 278 - AtCoder
コンテスト中AC:A〜D
E,Fはコンテスト後に自力AC

E - Grid Filling
F - Shiritori

E - Grid Filling

このユーザ解説と同じ方法で解きました。
想定解法は二次元累積和だったようです。
実装:Editorial - AtCoder Beginner Contest 278

二次元累積和の構造体を作って解いてみました。
実装:Submission #36758941 - AtCoder Beginner Contest 278

F - Shiritori

後退解析+bitDP(巡回セールスマン問題)の考え方で解けます。

問題を有向グラフに言い換えておきます。

$S_i$ を頂点 $i$ とする。
$S_i$ を言った後に $S_j$ を言える場合、頂点 $i$ から頂点 $j$ へ向かう有向辺があるとする。
有向グラフ上を交互に移動することを繰り返し、移動できなくなった方が負け

制約上、bitDPが疑われるので、その要領で考えてみます。

$dp[S][i]:=$ これまでに訪問した頂点集合が $S$ で頂点 $i$ で自分のターンを終えたとき、勝てるなら1、負けるなら0

まず、"次のターンでこれ以上移動できる頂点がない"となった時点で勝ちが確定します。そこで、訪問した頂点数が多い順から勝敗を確定していけそうです。
これが後退解析にあたります(おそらく)。

では、勝敗の確定条件を考えます。
自分が頂点 $u$ で移動を終え、 $u$ から移動可能であって、かつ未訪問の頂点が $v_1,\ v_2,\ \cdots ,\ v_k$ であるとします。

このうち、いずれか1つでも勝ちとなる頂点が存在する場合、相手はその頂点に移動すれば勝てるので、自分は負けとなります。逆に負けの頂点しかなければ、勝てます。
また、訪問可能な頂点がない場合も自分が勝ちとなる条件となります。

後はこれに従って、bitDPを逆に回していきます。
最終的に"頂点が1つだけ訪問済みである"という状態のDP値(例えば、N=3ならdp[001][0], dp[010][1], dp[100][2]。なお、1つ目のインデックスはbit列)について、頂点 $1,\ 2,\ \cdots ,\ N$ のうち、ただ1つでも勝ちがあれば太郎くんが勝ちます。

実装: Submission #36721268 - AtCoder Beginner Contest 278

余談で、DPの別の言い方を示しておきます。

$dp[S][i]:=$ これまでに訪問した頂点集合が $S$ で頂点 $i$ で自分のターンが回ってきた時、勝てるなら0、負けるなら1

この場合、移動できなくなったら負けるので、訪問可能な頂点がなければ負けです。また、相手のターンになったときに負けとなる頂点が1つでもあれば自分は勝てます。

最終的に"頂点が1つだけ訪問済みである"という状態のDP値について、頂点 $1,\ 2,\ \cdots ,\ N$ のうち、ただ1つでも負けがあれば、太郎くんが勝ちます(1つだけ訪問済みの状態で順番がくるのは次郎くんであるため)。
実装:Submission #36708784 - AtCoder Beginner Contest 278

2022-11-15

AtCoder Beginner Contest 277 備忘録

ABC ダイクストラ Union-Find 拡張ダイクストラ

コンテスト中AC:A〜E

D - Takahashi's Solitaire
E - Crystal Switches

D - Takahashi's Solitaire

コンテスト後に考え直したので、メモしておきます。

一旦modを無視します。
以下の問題を解けばこの問題に答えられます。

$A$ から要素を順に選び、 $B=\{B_1,\ B_2,\ \cdots ,\ B_m\}$ とする。但し、 $B$ は以下の条件を満たさなければならない。

$1\leq i\leq m-1$ について、 $B_{i+1} - B_i \leq 1$
要素の和が最大となる $B$ を求めよ。

ここで、 $A$ を昇順ソートしておくと、 $B$ は $A$ の連続部分列となります。

また、和を最大化したいので、連続部分列は条件を満たす限り伸長させた方が良いです。そのため、各要素は2つ以上の連続部分列に属する必要がありません。

そこで、 $A$ の連続部分列を探索する際、例えば、 $A_i,\ A_{i+1},\ \cdots ,\ A_j$ が可能な限り伸長した連続部分列であるなら、次の連続部分列の探索は $A_{j+1}$ から再開すれば良いです。探索範囲を右に進めるだけとなるので、 $O(N)$ となります。

modの部分ですが、これは $A_1 = 0$ かつ $A_{N} = M-1$ の場合に、これらを含む連続部分列を繋げるようにすれば解決になるわけですが、以下の2パターンで実装してみました。

解決方法1
配列が円環となることが想定される場合の常套手段ですが、 $A$ を昇順ソートしたものを2つ繋げます。これに対して連続部分列を探索すれば、modを考慮した場合と同様の結果が得られます。
但し、 $A$ に $0,\ 1,\ \cdots ,\ M-1$ の全てが含まれる場合は、 $A$ の要素の和を超えてしまうので注意が必要です。
実装例:Submission #36484745 - Daiwa Securities Co. Ltd. Programming Contest 2022 Autumn (AtCoder Beginner Contest 277)

解決方法2
Union-Findを用いた解法です。0-indexedとします。
$A$ を昇順ソートし、 $0\leq i \leq N-1$ について、 $A_i = A_{(i+1)\ mod\ N}$ または、 $(A_i +1) \ mod M = A_{(i+1)\ mod\ N}\ mod M$ が成り立つなら、Union-Findで同一連結成分とします。

Union-Findにおける連結成分の和を計算していけば、答えを得ることができます。

実装例:Submission #36488298 - Daiwa Securities Co. Ltd. Programming Contest 2022 Autumn (AtCoder Beginner Contest 277)

E - Crystal Switches

解法はこちらの公式解説とほぼ同じなので、省略します。
実装では、 $dist[i][j]$ を、頂点 $i$ でスイッチの状態が $j$ の時の移動回数の最小値、としました。
また、スイッチを押す操作もダイクストラ法で頂点 $u$ から $v$ に移動する際に考慮されるようにしました。

提出コード:Submission #36446787 - Daiwa Securities Co. Ltd. Programming Contest 2022 Autumn (AtCoder Beginner Contest 277)
スイッチの状態の表現が公式解説と逆なので、ご注意ください。

geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。