鈴木林檎農園

問題リンク

https://atcoder.jp/contests/abc365/tasks/abc365_g

公式解説1の考え方

公式解説に倣い、$i$番目の高橋くんがオフィスの中にいた時間の区間の集合を$S_i$とする。 クエリの組$(A, B)$について、下記パターンI, Ⅱに分けて考える。

パターンI： 愚直にイベントソートして処理。 高橋くんそれぞれのイベントを予め分けておく。 クエリの組$(A, B)$のイベントをマージ→重複している時間を求める。 クエリ1回あたり$O(C_{})$かかる(イベントは入力でソート済みなのでlogはかからない)。 クエリ$Q$回全部$C$以下があり得るので、クエリ全体で$O(QC)$かかる。

パターンⅡ： クエリの組$(A, B)$は、 ・$C$より大きい高橋くんが$\frac{M}{C}$ ・任意の高橋くんが$N$ この2種から1つずつ選ぶので$O(\frac{NM}{C})$個のクエリがパターンⅡに当てはまり得る。 これらクエリを予め計算してキャッシュし、クエリに答えるようにする。

$S_i$が$C$を超える高橋くんを$i$、任意の高橋くんを$x$として、クエリの組$(i, x)$をまとめて前計算する。 前計算1回あたり、イベント全走査して$x$を全通りキャッシュするので、時間計算量$O(N+M)$、空間計算量$O(N)$かかる。

$i$のあり得る個数は$O(\frac{M}{C})$ (イベント個数$M$から閾値$C$が何個取れるか)により、 キャッシュ計算全体で時間計算量$O(\frac{(N+M)M}{C})$ 空間計算量$O(\frac{NM}{C})$

$C=O(\sqrt{\frac{NM}{Q}})$ とすることで、 全体$O(\sqrt{NMQ}+M\sqrt{\frac{MQ}{N}})$で解ける。

提出コード https://atcoder.jp/contests/abc365/submissions/56695169

平方分割の考え方1

可能ならクエリの答えをすべて予め計算してキャッシュしたいが時間が掛かりすぎるため、 何個キャッシュを持っておくべきか？ →$\sqrt{N}$くらいキャッシュする キャッシュで持ちきれない分は都度愚直計算する。 都度愚直計算する負担が少ないものはどういう性質がある？ →$S$が小さいもの

平方分割の考え方2

クエリ全部を都度愚直計算で答えるとする。 愚直で答え切れるクエリ1回あたりの限界は？ →$S$が$\sqrt{M}$くらい 範囲外のものは予め計算しておいてキャッシュから答える。

公式解説2の考え方

合計が$M$のとき、$Q$個の相異なるペアについて小さい方の和は$O(M\sqrt{Q})$で抑えられる。 クエリ１つ捌くところで計算量を「ペアの小さい方log(ペアの大きい方)」になるように書けば間に合うイメージ。

$O(M√Q)$で抑えられる抑えられる理由のイメージは、 ペア$(A, B)$について、$A$も$B$も$M$への寄与分が同じときが一番きつい。 ペアに登場する要素の種類数が$x$のとき、その全組み合わせは${}_xC_2=O(x^2)$なので 要素の種類数を$\sqrt{Q}$個にして、$M$を$\sqrt{Q}$に均等に割り振るのが最悪ケース。 このとき要素一つあたり$O(\frac{M}{\sqrt{Q}})$、 クエリ$Q$個飛んでくるので$O(\frac{M}{\sqrt{Q}}*Q)=O(M\sqrt{Q})$。

クエリ１つ捌くところで計算量を「ペアの小さい方log(ペアの大きい方)」にするパートは ABC305D-Sleep Logと同じ。

クエリは相異なるペアである必要があるので、同じクエリが来たときようにキャッシュが必要な点に注意。

提出コード https://atcoder.jp/contests/abc365/submissions/56669241

問題リンク

https://atcoder.jp/contests/abc353/tasks/abc353_g

考察(セグ木)

公式解説(https://atcoder.jp/contests/abc353/editorial/9953)の解き方。

インラインDPを考えて、$dp[x]$を町$x$にいるときの所持金最大値とすると $i$番目の市場に参加したときの$dp[T[i]]$の更新は下記の通り。 (市場に参加するときのみ移動すると考える) $dp[T[i]]=P[i] + \max_{0\geq j<N}​ {dp[j]−C∣j−T[i]∣}$

$\max_{0\geq j<N}​ {dp[j]−C∣j−T[i]∣}$ を求めるところで、 公差$-C$の等差数列を足した上でのmaxが知りたいので、区間等差数列add区間maxが欲しくなる。

こういうときは、要素に予め $ -C*i, C*i$ を足した値をそれぞれ区間maxセグ木に乗せておく。 市場参加時のmaxを求めるときに、セグ木にクエリして得られた最大値に $C*T[i], -C*T[i]$ を足してずれを補正する。 セグ木の値を更新するときも、 $-C*i, C*i$ を足した値で更新するのを忘れずに。

提出コード https://atcoder.jp/contests/abc353/submissions/53402297

考察(Li Chao tree)

KumaTachiRenさんのユーザ解説(https://atcoder.jp/contests/abc353/editorial/9984)の解き方。

区間等差数列add区間min/maxはCHTの上位互換なので、区間等差数列add区間min/maxが欲しくなったときはまずCHTを疑う。

考察(セグ木)のときとは違って、$dp[x]$の更新を ・町$x$にいた状態で$i$番目の市場をスルーしてして、町$x$に居続ける ・$i$番目の市場に参加して、町$T[i]$から町$x$に移動してくる の最大値で書き換えと考える。 (市場参加後に各町に移動するところまでやるイメージ)

絶対値がついている場合は、正負の場合分けで絶対値を外すと考えやすいので $0\geq j<N$の$x$それぞれに対して、 $dp[x]$ $=\max(dp[x], P[i] + dp[T[i]] − C∣x-T[i]∣)$ $=\max(dp[x], Cx + P[i] + dp[T[i]] - CT[i]) (x<T[i])$ $ \max(dp[x], −Cx + P[i] + dp[T[i]] + CT[i]) (T[i]\geq x)$

maxの第2引数がxの一次関数になっているので線分追加のLi Chao treeで解ける。

提出コード https://atcoder.jp/contests/abc353/submissions/53404160

考察(区間等差数列add区間min)

区間等差数列add区間maxが欲しいので、そのまま実装する。 定数倍重いのでC++でしか通せない気がする。

考え方

食塩水候補をいくつか選んで混ぜたときにできる新食塩水の濃度の最大値は？のような問題。 基本は濃度$x\%$が達成できるか？の判定問題に落としてにぶたん。

食塩の重さを$A$, (食塩+水)の重さを$B$とすると ソート基準は $(\frac{A}{B}-x) * B$ もしくは $A - x * B$ で降順ソートして貪欲に選べばよい。 濃度$x\%$に必要な食塩と比較してどれだけプラスかを計算するイメージ。

ABC034D - 食塩水

https://atcoder.jp/contests/abc034/tasks/abc034_d

$A - x * B$でソート。 提出コード：https://atcoder.jp/contests/abc034/submissions/46661824

ABC294F - Sugar Water 2

https://atcoder.jp/contests/abc294/tasks/abc294_f

$A - x * B$でソート。 濃度$x\%$以上の砂糖水がK個以上作れるか？の判定問題。 提出コード：https://atcoder.jp/contests/abc294/submissions/46662307

ABC324F - Beautiful Path

https://atcoder.jp/contests/abc324/tasks/abc324_f

・濃度=食塩/(食塩+水), ・ABC324Fの求める値=美しさ/コスト で式が同じなので、 ・食塩=美しさ ・(食塩+水)=コスト で言い換えられる。 $A - x * B$でソート。 DAGなので普通に前からDPできる。 提出コード：https://atcoder.jp/contests/abc324/submissions/46661282

(おまけ)ABC236E - Average and Median

https://atcoder.jp/contests/abc236/tasks/abc236_e

・平均値最大化： $a_0, …, a_n$の平均値が$K$以上 $\Leftrightarrow (a_0-K)+ … +(a_n-K) \geq 0$ なので、 $b_i=a_i-K$とおいて、($b$から選んだ要素の総和)$\geq0$か判定

問題リンク

https://atcoder.jp/contests/abc314/tasks/abc314_e

考察

普通の期待値DP。 遷移に自分自身へのループがあるところの処理はEDPC J - Sushi と同じ。 https://atcoder.jp/contests/dp/tasks/dp_j

解説の 「$i$ 番目のルーレットが出しうる目 $P_i$​ 個のうち $Z_i$​ 個が 0 であるとき、このルーレットの代わりに $C_i​\frac{P_i}{P_i-Z_i}$ 円払ってもとのルーレットから 0 の目を取り除いたようなルーレットを用いることにしても結果は変わりません。」 の部分がよく分からなかったのでメモ。

これを一般化して、下記を考える。 ルーレットの出しうる目$A$個のうち、あたりが$A-t$個、はずれが$t$個ある。 ルーレットであたりが出るまで回し続けるとき、回す回数の期待値は？

期待値を求める式は、

$\frac{A-t}{A} + 2\frac{t}{A}\frac{A-t}{A} + 3(\frac{t}{A})^{2}\frac{A-t}{A} + \cdots$

$=\frac{A-t}{A} (1 + 2\frac{t}{A}+ 3(\frac{t}{A})^{2} + \cdots)$

$=\frac{A-t}{A} \lim_{n \to \infty} \sum_{k=0}^{n} {(k+1) * (\frac{t}{A})^k}$

$=\frac{A-t}{A} \lim_{n \to \infty} \frac{A^2 + (n+1)t^2(\frac{t}{A})^2 - A(n+2)t(\frac{t}{A})^n}{(A-t)^2}$

$=\frac{A-t}{A} \frac{A^2}{(A-t)^2} $

$=\frac{A}{A-t}$

となり、解説の式に一致する。

問題リンク

https://atcoder.jp/contests/abc310/tasks/abc310_f

考察

シンプルにdp[index][選んだサイコロの目の総和]で考えるとうまくいかない。

vector<vector<Modint>> dp(N + 1, vector<Modint>(11)); dp[0][0] = 1; rep(i, N) rep(j, 11) { repeq(k, min(10LL, A[i])) { ll nextj = j + k; if (nextj <= 10) dp[i + 1][nextj] += dp[i][j]; } dp[i + 1][j] += dp[i][j] * A[i]; } Modint ans = dp.back()[10]; rep(i, N) ans /= A[i]; cout << ans << '\n';

入力が 2 10 10 で、1つ目のサイコロ、2つ目のサイコロともに10が出たとする。 上のコードだと ・1つ目のサイコロを選んで2つ目のサイコロを捨てる ・1つ目のサイコロを捨てて2つ目のサイコロを選ぶ が別事象として扱われて2通りとしてカウントされる。 ただ、今回の問題では「10, 10が出た」という1通りの現象としてカウントを求められているので、これでは解けない。

DPは同一視したい状態をまとめて管理するのが鍵なので、 「出た目を使って総和に加算」「出た目を使わず総和そのまま」を1通りとして表現できるような状態設計が必要。

そこでdp[index][作成可能な総和を立てたbit]のbitDPを考える。 こうすることで、「出目kを使って総和に加算」「出目kを使わず総和そのまま」が

ll nextj = j | j << k;

でまとめて表現できる。

問題リンク

https://atcoder.jp/contests/arc137/tasks/arc137_b

考察

獲得可能なスコアの最小値〜最大値は全て達成できるので、取り得るスコアの最小値・最大値を求めればよい。 各始点でflipしたときのスコアの増加量、減少量を区間add区間maxの遅延セグ木で管理する。 解けるには解けるが遅延セグ木を持ち出す重厚感ある解法。

提出コード https://atcoder.jp/contests/arc137/submissions/43493156

考察+α

問題を少し言い換える。 ・数列$B$を$b_i = a_i == 0 ? 1 : -1$と定義する。 連続する区間を一つ選び、その総和をスコアとする。 取り得るスコアの最小値・最大値は？ 数列$B$はflipしたときのスコアの増加量を表している。

区間の終点をrに固定したとする。 スコアを最小化したいとき、始点lはその時点でのスコアが最も高いところを選びたい。 スコアを最大化したいとき、始点lはその時点でのスコアが最も低いところを選びたい。 (どちらも落差が一番大きいところを選びたいので)

累積和、および過去の累積和のうちの最小値・最大値を管理しておけば解ける。

問題リンク

https://atcoder.jp/contests/arc164/tasks/arc164_d

考察

括弧列の(と)を組み合わせるように+と-を組み合わせて、そのペア間の距離の総和を求めればよい。 $dp[index][c]$ := indexまで見て?に+をc個当てはめた時の総和・場合の数をそれぞれ管理する。

各電荷の寄与を考えるときに、累積和のような考え方を使う。 ペア間の距離を求めたい。 つまり、ペアの一方のインデックスがl, もう一方がrのときのr-lを足し合わせたい。 しかし、?の割り当て次第で誰がペアになるか分からない。

今のインデックスの文字が+であったときを考える。 (1)今のインデックスまでの電荷の総和が正であれば、さらに+を積むことになり、ペアの区間が新たに開始することになる。 (2)今のインデックスまでの電荷の総和が負であれば、余っている-と今の+でペアが完成し、ペアの区間が終了することになる。

(1)の区間開始時は-indexを、(2)の区間終了時は+indexを総和に加算することで、 r-lを足し合わせることに相当するので答えが求まる。

提出コード https://atcoder.jp/contests/arc164/submissions/43483636

考察+α

総和と場合の数をそれぞれ管理するDPでは二重数が便利らしい。 二重数は $\epsilon^2 = 0$ なる$\epsilon$を定義し、数を$a + b\epsilon$と表現する。

$dp, newdp = a + b\epsilon$の$a$で場合の数(kosu)を、$b$で総和(value)を管理するとして、

newvalue += value; newvalue += kosu * t; newkosu += kosu;

の3行が

newdp += dp * dual(1, t);

の1行で計算できる。

総和と場合の数をそれぞれ管理するとき、場合の数は単純に足し合わせるだけなので * dual(1, t); の1は常に固定でtだけ問題に応じて考えればよさそう。

提出コード https://atcoder.jp/contests/arc164/submissions/43484317

参考

累積和は今後もよく使いそうな気がするので思考の整理。

問題リンク

https://atcoder.jp/contests/abc256/tasks/abc256_f

寄与回数を考える

累積和を複数回取ったとき、数列各項の寄与回数の係数に注目する 例：累積和3回(問題文中でいう数列$D$) の3項目 $D_3= 10A_0 + 6A_1 + 3A_2 + 1A_3$ -> $1, 3, 6, 10, ...$

累積和1回：$1, 1, 1, 1, 1, 1, ...$ -> 1 累積和2回：$1, 2, 3, 4, 5, 6, ...$ -> $n$ 累積和3回：$1, 3, 6, 10, 15, 21, ...$ -> $\frac{n(n+1)}{2}$ 累積和4回：$1, 4, 10, 20, 35, 56, ...$ -> $\frac{n(n+1)(n+2)}{6}$ 累積和5回：$1, 5, 15, 35, 70, 126, ...$ -> $\frac{n(n+1)(n+2)(n+3)}{24}$

累積和$k$回のときの一般項は$({{n+k-2} \atop {k-1}})$になりそう

累積和3回の係数の数列を$x$と置いて これを問題で問われている$D$について考えると、 $D_i$ $=\sum_{n=0}^{i} {x_{i-n} A_n}$ $=\frac{1}{2} \sum_{n=0}^{i} (i-n+1)(i-n+2) A_n$ $=\frac{1}{2} \sum_{n=0}^{i} (i^2 -in +2i -ni +n^2 -2n +i -n +2) A_n$ $=\frac{1}{2} \sum_{n=0}^{i} (n^2 -in-in-2n-n + i^2+i+2i+2) A_n$ $=\frac{1}{2} \sum_{n=0}^{i} (n^2 + (-2i-3)n + i^2+3i+2) A_n$

$\sum_{n=0}^{i} n^2A_n, \sum_{n=0}^{i} n A_n, \sum_{n=0}^{i} A_n$ をそれぞれ管理すれば解ける！

suisenさん解法を紐解く

https://atcoder.jp/contests/abc256/editorial/4152

母関数に$\frac{1}{1-x}$をかけると累積和が取れる。 数列$D$は累積和3回なので、$\frac{1}{(1-x)^3}$をかける。

負の二項定理を考える。 $\frac{1}{(1-x)^{d+1}} = \sum_{n=0}^{\infty}{({{n+d} \atop {d}})x^n}$ 累積和3回は$\frac{1}{(1-x)^3}$をかけるので、$d=2$を代入するとちょうどよさそう

一般項$D_k$を求めたい=$x^k$の係数を求めたいので、シグマの範囲は$k$で打ち切る。 「寄与回数を考える」で書いたように、数列$A$と累積和の係数は逆順でかけ合わせている ($D_3$について、$A_3$と累積和係数第一項の$1$をかけている) ので、負の二項係数の部分は $n=i-k$を代入して逆にして$A$の母関数をかける $\sum_{i=0}^{k}{({{k-i+d} \atop {d}})x^i}$

$D_k$ $=\sum_{i=0}^{k}{A_i({{k-i+2} \atop {2}})}$ 二項係数を普通に展開して、 $=\sum_{i=0}^{k}{A_i\frac{(k-i+2)(k-i+1)}{2*1}}$ $=\frac{1}{2}\sum_{i=0}^{k}{A_i(i^2 + (-2k-3)i + k^2+3k+2)}$ で導出できる。

典型テクっぽいので記事に書いて思考の整理。 自分の考えをまとめるために書いているので、数学的に正確でない表現があることをご容赦ください...

問題リンク

https://atcoder.jp/contests/abc288/tasks/abc288_d

問題概要

操作「長さ$K$の区間に$c$を一様加算する」を好きな回数行ってよいとき、数列Aの区間$[l,r)$の項をすべて$0$にできるか？

leaf1415さん解説

https://atcoder.jp/contests/abc288/editorial/5660

$[l, r)$の範囲で階差数列$B_i = A_{i+1} - A_i$を考える。 ただしクエリ両端はクエリに含まれない分を除くので $B_l += A_{l-1}, B_r -= A_r$ としておく。 $mod K$ごとの階差数列Bの総和$T_{i} = \sum {B_{index mod K == i}}$ として、 $T_{0} = T_{1} = ... = T_{K-1} = 0$であるかで判定する解法。

操作「範囲$[l,r)$・長さ$K$の区間に$c$を一様加算する」は、 階差数列を考えると 操作「$B_{l-1}$に$+c$, $B_r$に$-c$」もしくは 操作「$B_{l-1}$に$+c$, $B_{l-1+K}$に$-c$」 に言い換えられる。

これは$mod K$ごとの階差数列Bの総和を変化させない条件下で、各項の値を自由に分配できる。

良い数列は全項$0$ = 階差数列も全項$0$ 操作によって階差数列を全項$0$にできるか？の判定は、$T_{0} = T_{1} = ... = T_{K-1} = 0$に言い換えられる。

提出コード https://atcoder.jp/contests/abc288/submissions/38756410

nok0さん解説

https://atcoder.jp/contests/abc288/editorial/5664 $[l, r)$の範囲での$mod K$ごとの元の数列$A$の総和$S_{i} = \sum {A_{index mod K == i}}$ として、 $S_{0} = S_{1} = ... = S_{K-1}$であるかで判定する解法。

操作「長さ$K$の区間に$c$を一様加算する」を行うときの不変量は何か？　を考える。 どの区間を選んでも $index mod K$ は $0, 1, ..., K-1$ がそれぞれ1回ずつ選ばれる →操作で $S_{0}, S_{1}, ..., S_{K-1}$ はそれぞれ$c$だけ加算される →それぞれの総和の差は操作前後で変わらない →総和の差：$S_{1}-S_{0} = S_{2}-S_{0} = ... S_{K-1} - S_{0} = const$(一定)　これが不変量！

良い数列は全項$0$ →$S_{0} = S_{1} = ... = S_{K-1} = 0$ →$S_{1} - S_{0} = S_{2}-S_{0} = ... = S_{K-1} - S_{0} = const$(一定) に代入すると $const$ = 0 である必要がある →$S_{1} - S_{0} = S_{2}-S_{0} = ... = S_{K-1} - S_{0} = 0$ なのでそれぞれ移項して $S_{0} = S_{1} = ... = S_{K-1}$　が出てくる！

提出コード https://atcoder.jp/contests/abc288/submissions/38755866

maspyさん解説

https://atcoder.jp/contests/abc288/editorial/5682 十分大きい素数$p$を決め、以下$mod p$で考える。 $x_{0}, x_{1}, ... , x_{K-1}$を $x_{1}, ... , x{K-1}$ を一様ランダムに, $x{0} = -(x_{1} + ... + x{K-1})$と定める $B_i = A_i * x_{i mod K} mod p$ とする $[l, r)$の範囲での$mod K$ごとの総和$S_{i} = \sum {B_{index mod K == i}}$ として、 $S_{0} = S_{1} = ... = S_{K-1} = 0$であるかで判定する解法。

$S_{0} = S_{1} = ... = S_{K-1}$ かどうかを判定したい 数列$x$について、$x{0} + x_{1} + ... + x_{K-1} = 0$

$A_l * x_{l mod K} + A_{l+1} * x_{l+1 mod K} + ... + A_{r-1} * x_{r-1 mod K}$ $=S_{0} * x{0} + S_{1} * x_{1} + ... + S_{K-1} * x_{K-1}$

$S_{0} = S_{1} = ... = S_{K-1}$ の場合$S_{i}$はすべてくくれて $= S_{0} * (x{0} + x_{1} + ... + x_{K-1})$

$x{0} + x_{1} + ... + x_{K-1} = 0$ なので $= 0$

ただし、 $S_{0} * x{0} + S_{1} * x_{1} + ... + S_{K-1} * x_{K-1}$ が $S_{0} = S_{1} = ... = S_{K-1}$ でない場合でも偶然0になってしまう場合が有り得る $mod p$ で考えているので、偶然0になってしまうのは確率は$\frac{1}{p}$で十分小さい

忘れるのでメモ。都度追記予定。

カレントディレクトリ以下のファイルの中身からテキスト検索

find ./ -type f -print0 | xargs -0 grep 'search-word' find ./ -type f -exec grep "search-word" {} +

カレントディレクトリ以下のcppファイルの中身をbefore→afterにテキスト置換

find . -name *.cpp | xargs sed -i '' -e ':a' -e 'N' -e '$!ba' -e 's/before/after/g'

カレントディレクトリ以下にある名前末尾が「.dSYM」のディレクトリを全削除

find . -name "*.dSYM" -type d -exec rm -rf {} +

リダイレクト先のファイルが存在してもNO_CLOBBERを無視して上書き

./a.out >| output.txt

ファイルを空にする

: >| output.txt

直前のコマンドをsudoで実行

sudo !!

sshでログアウトしてもコマンドを実行し続ける

nohup (コマンド) &

nohupし忘れた

Ctrl+Zでコマンドの中断 jobsでジョブの確認 bgでバックグラウンドに回す disownでログアウトしても実行されるようにする

(何かコマンド) # Ctrl+Zで中断 jobs bg %1 disown %1

右上に時計を出す

while sleep 1;do tput sc;tput cup 0 $(($(tput cols)-29));date;tput rc;done &

(ruby)gemのインストールパス指定

bundle config set --local path vendor/bundle

git reset

--soft：HEADの位置のみ --mixed(指定なし)：HEADの位置・ステージ --hard：HEADの位置・ステージ・作業ディレクトリ

直前コミットの取り消し

git reset --soft HEAD^

git addの取り消し

git reset HEAD

git commit順入れ替え

git rebase -i HEAD~10

してエディタで順番を編集

競プロメモ

C++17用テンプレ https://gist.github.com/suzukiapple/e1cb32546f8c3e6f83bce8a6ab7954e6 https://t.co/e86sFPAr2n

vscode snippet https://gist.github.com/suzukiapple/0a4b8a7853e77d87672af5aaa8b86878 https://t.co/c85f6rpaAm

参考

黄色到達から記事公開まで時間が空いてしまいましたが "Done is better than perfect" なのでなんとか書き上げました！ ABC197で黄色になることができました。 競プロを始めてちょうど2年、青色になって1年弱くらいです。 青→黄は本当に長かった... 青色期間中にやったことを振り返ります。

精進状況

青→黄で500ACくらいです。思ったより少ない...

こどふぉの状況です。 深夜帯コンテストへの出場が体力的に辛くなってきてなかなかratedに参加できない... あと青になってこどふぉも解くようになったんですが思ったよりも草が少ないですね...

アルゴリズム習得・ライブラリ整備

青色期間中に覚えたアルゴリズムや作ったライブラリを書き並べました。 ・形式的冪級数 ・燃やす埋める ・牛ゲー ・eerTree ・KMP法 ・eerTree ・Aho-Corasick ・Mo's algorithm ・フロイドの循環検出 ・GCD, LCM畳み込み

けどこれらを使って本番でACできたことがない気がする... こどふぉの過去問解いてたときに、 https://codeforces.com/problemset/problem/1452/D が形式的冪級数で解ける！と自力で気づけたくらい。 レートには直接結びついてないですね...

黄色になるためには、難しいアルゴリズムを勉強するというよりも もっと基礎的な知識の完成度を上げる方が重要な気がします。

DP集中練習

青なりたての時はDPが全然分かってなくて添字ガチャをしたり四苦八苦してました。 これを克服するためにEDPC, TDPCを全部埋めました。 TDPCは特に難しい...解説ブログを見ながらなんとか解いた感じなので改めて解き直ししたいです。

あとJOIもいくつか解きました。 JOIは綺麗なDP問題が多いので、DP練習にとても良いと思います。

対DP問題用テンプレートも作成して、今は「DPならなんとか解けるかも」と思えるくらい自信がついてきました。 ABC195-EF, ABC197-E とコンテスト本番でDP問題を通せることが増えてきてレート増加に繋げられました。

AtCoderFriends

青の色変記事でも書きましたが改めて。 ・問題ページからサンプル取得 ・入力コードの自動生成 ・サンプル合わせ ・コード提出 が自動で出来る便利ツールです。 詳細はこちら https://github.com/nejiko96/at_coder_friends

ずっとこのツールと一緒に戦い続けていて私の右腕みたいな感じです。 ほんのわずかですがContributeもさせていただきました。 本当にありがとうございます！

これから

自分の家庭の方が忙しくなってきて、4月から競プロの時間がなかなか確保できなくなってきました。 現在はABC出場とその復習だけで精一杯の状態です。 黄色達成まで来たので次の橙を目指したいところですが、家庭を崩壊させるわけにもいかないのと青→黄以上に長い長い道のりになるので、焦らず自分のペースで競プロを続けていきたいです。

あとGCJでRound2突破＋Tシャツ獲得したい！ FHCの方はTシャツ2枚獲得できているのでGCJでも良い結果を残したいところです。 忙しくてもGCJ, FHCは出場します！

問題リンク

https://atcoder.jp/contests/abc207/tasks/abc207_e

考え方

遷移先の前計算は思いついていたが、下記の図上半分のように、現時点の倍数の区切り候補全てに遷移させていた。 この場合計算量がO(N^3)になってしまってTLEしてしまう。

よく考えると (3の倍数)+(3の倍数)=(3の倍数)なので、 一番近い3の倍数の区切り候補にのみ遷移して ・3の倍数を続行 ・4の倍数に移行 の2パターンのみ考えればよい。

「3の倍数を続行して、3の倍数の区切り確定タイミングを遅らせることができる」のがこの問題の肝。

「期待値の線形性」 名前はよく聞くけどなかなか使いこなせない。

問題リンク

https://atcoder.jp/contests/arc114/tasks/arc114_e

考え方

期待値といえば、「一連の操作が起こる確率 * 操作終了時の得点」を全パターン計算して足すと求まる。 これは一連の操作に注目したときの考え方。

もうひとつの考え方として、一連の操作を細かく分解して「点数を得られる１操作」の方に注目して、 「１操作についての期待値への寄与」を全操作分足す求め方がある。

１操作単位で見て寄与を足し合わせてもOKというのが「期待値の線形性」。

問題文の操作は、ランダムに線を１本選んで、黒を選んだら終了、黒以外なら紙を切り離して続行。 期待値の線形性を考えると、図の橙黄青緑線の一本一本が期待値にどれだけ寄与するかをそれぞれ求めたい。

例として、図の３番目の青線（以下「青３」）に注目してみる。 青３が期待値に寄与「しない」パターンは次のA, Bのどちらか。 A：青３を選ぶ前に黒５本のどれかを選んで操作終了した B：青３を選ぶ前に青１or青２を選んで紙から切り離された

ということは、青３に注目した場合、黒・青１・青２だけ考えればよくて、他の線のことは無視できる。 青３が期待値に寄与「する」パターンは、黒５本・青３本を並び替えたときに青３が一番先頭に来るとき。 なので、青３の期待値への寄与$=\frac{1}{5+3}=\frac{1}{8}$と求まる。

同様に橙黄青緑線の一本一本それぞれ計算して総和を求めればよい。 最後に黒を選んで操作終了する＋１を忘れずに。

提出コード： https://atcoder.jp/contests/arc114/submissions/20983904

類題

牛ゲー完全に理解した

問題リンク

https://atcoder.jp/contests/arc105/tasks/arc105_c

考え方

ある始点から頂点$v$までの最短距離を$f(v)$とする。 頂点$i$→$j$, コスト$w$の辺があったとき、$f(i)+w \geq f(j)$がいえる。 (始点から$j$へ行く最短経路の候補として、始点→$i$→$j$へ移動する方法があるため)

二点間$i,j$とその間の距離について制約を満たした上での$start,goal$間の最大値が知りたいとき、 制約を $f(i)+w \geq f(j)$ の形に式変形して頂点$i$→$j$, コスト$w$の辺を張る。 このグラフ上についての$f(goal)-f(start)$の最小値が$start,goal$間の最大値に一致する。 $start, goal$間の最小値が知りたいときは符号反転させることで同じ考え方が使える。

まとめると、

$start, goal$間の最大値が知りたい ⇔制約 $f(i)+w \geq f(j)$ のとき、頂点$i$→$j$, コスト$w$の辺を張る 　構築したグラフでの$f(goal)-f(start)$の最小値 　$start→goal$の最短経路問題を解く

$start, goal$間の最小値が知りたい ⇔制約 $f(i)+w \geq f(j)$ のとき、頂点$i$→$j$, コスト$w$の辺を張る 　構築したグラフでの$-(f(goal)-f(start)) = f(start)-f(goal)$の最小値 　$goal→start$の最短経路問題を解く

今回の問題でいうと、 ラクダ$i$, ラクダ$i+1$の順に並んでいる ⇔ $f(i) + 0 \leq f(i+1)$ 移項して $f(i+1) + 0 \geq f(i)$ ⇔ 頂点$i+1$→$i$, コスト$0$の辺を張る

ラクダ$i$, ラクダ$j$は$x$以上の距離を空ける必要がある ⇔ $f(i) + x \leq f(j)$ 移項して $f(j) - x \geq f(i)$ ⇔ 頂点$j$→$i$, コスト$-x$の辺を張る

先頭のラクダと末尾のラクダの距離の最小値が知りたいので、$goal→start$の最短経路問題を解けばよい。

グラフに負辺がなければダイクストラ、あるときはベルマンフォードを使う。 閉路がないグラフ（=DAG）であればDPでも解ける。

提出コード

死ぬほどハマったのでメモ。

症状

homebrewでインストールしたgccを使ってC++コードをコンパイルしようとしたときに下記エラーが出る。 自分の場合は Big Sur 11.0.1 → 11.1 のアップデート後に発症した。 アップデート前は特に問題なくコンパイルできていた。

C++コード

#include <iostream> int main() { std::cout << 123 << std::endl; return 0; }

コンパイル

$ g++-10 test.cpp In file included from /usr/local/Cellar/gcc/10.2.0/include/c++/10.2.0/bits/postypes.h:40, from /usr/local/Cellar/gcc/10.2.0/include/c++/10.2.0/iosfwd:40, from /usr/local/Cellar/gcc/10.2.0/include/c++/10.2.0/ios:38, from /usr/local/Cellar/gcc/10.2.0/include/c++/10.2.0/ostream:38, from /usr/local/Cellar/gcc/10.2.0/include/c++/10.2.0/iostream:39, from test.cpp:1: /usr/local/Cellar/gcc/10.2.0/include/c++/10.2.0/cwchar:44:10: fatal error: wchar.h: No such file or directory 44 | #include <wchar.h> | ^~~~~~~~~ compilation terminated.

C++コード

#include <bits/stdc++.h> int main() { std::cout << 123 << std::endl; return 0; }

コンパイル

$ g++-10 test.cpp In file included from /usr/local/Cellar/gcc/10.2.0/include/c++/10.2.0/x86_64-apple-darwin20/bits/stdc++.h:33, from test.cpp:1: /usr/local/Cellar/gcc/10.2.0/include/c++/10.2.0/cassert:44:10: fatal error: assert.h: No such file or directory 44 | #include <assert.h> | ^~~~~~~~~~ compilation terminated.

解決方法

Command Line Toolsの削除+再インストール、gccの再インストールを行う。

$ sudo rm -rf /Library/Developer/CommandLineTools $ xcode-select --install $ brew reinstall gcc

その後、下記コマンドを打ってからコンパイルすればOK。

$ export SDKROOT="$(xcrun --show-sdk-path)"

XcodeでビルドするときとかにSDKROOTのパスが参照されるみたいだが、 homebrewからインストールしたgccもこのパスを見ているらしい。 症状が治れば.bachrcとか.zshrcとか普段使っているやつに追記すると便利。

(追記) コンパイル時のオプションで指定する方法もあるみたい。 お好みでどうぞ。

$ g++-10 --sysroot=$(xcrun --show-sdk-path) test.cpp

問題リンク

https://atcoder.jp/contests/arc110/tasks/arc110_d

考え方

唐突ですが、ここで問題です。 Q1：りんご、みかん、ぶどうが無限個売られています。 　合計がちょうど10個になるように買う方法は何通りありますか？

A1：ボール10個、仕切り2個の並べ替えを考える。 　並べた結果を下記の通り意味付けすると題意を満たす。 　したがって答えは $ {}_{12}C_{10} = 66 $通り。

Q2：りんご、みかん、ぶどうが無限個売られています。 　合計が10個以下になるように買う方法は何通りありますか？

A2：ボール10個、仕切り3個の並べ替えを考える。 　並べた結果を下記の通り意味付けすると題意を満たす。 　したがって答えは ${}_{13}C_{10} = 286$ 通り。

Q3：りんご、みかん、ぶどうが無限個売られています。 　りんご $x$ 個、みかん $y$ 個、ぶどう $z$ 個を買うときの嬉しさを $xyz$ と定義します。 　合計が10個以下になるように買う方法全通りの嬉しさの総和はいくつですか？

A3：ボール13個のうち、6個を青く塗る塗り方を考える。 　左から偶数個目の青ボールを仕切りとして考え、 　各仕切りの間をりんごゾーン、みかんゾーン、ぶどうゾーン、買わないゾーンとする。 　りんごゾーン、みかんゾーン、ぶどうゾーンのうち、1個のボールを青に塗ると考える。 　このとき、各ゾーンの青の塗り方が、りんご、みかん、ぶどうを買う嬉しさに一致する。 　したがって答えは ${}_{13}C_{6}=1716$。

Q1は組み合わせ問題でよくあるやつ。

Q2は合計が0個のとき、1個のとき...と全パターン計算してもよいですが大変。 Q1に仕切りを1つ追加して買わないゾーンを作ると、合計が0〜10個の全パターンが表現できる。

Q3は嬉しさの値をボールの塗り分けに埋め込む。 青いボールに嬉しさの表現と仕切りとでふたつの意味を持たせている。 上記塗り分けの場合、ある果物を0個買う状態が表現できないが、その場合は嬉しさが0なのでカウントする必要がない。

これを今回の問題にも当てはめる。 サンプル1のB=1,3,1のパターンを表したのが下の図。 8個のボールのうち7個のボールを青く塗る塗り方を考えて意味付けしてみる。

8 = Bの総和の最大M=5 + 仕切りN=3 7 = Aの総和S + 仕切りN=3 を意味している。

青いボールに ${}{B{i}}C_{A_{i}}$ と仕切りとでふたつの意味を持たせている。

これを一般化すると、配列Aの総和をSとして、${}_{N+M}C_{N+S}$ が答え。

もっと多くの方々に競技プログラミングの楽しさを知ってもらって競プロ沼へはめるために、 競技プログラミング初心者向けにどう始めればよいか、何を勉強すればよいかまとめてみました。

競技プログラミングとは

与えられた問題に対して、題意を満たすプログラムをいかに早く正確に書くかを競います。 出題される問題は、アルゴリズム、数学、パズルなど幅広い分野が出題されます。

競技プログラミングで有名なサイトとしてAtCoder(https://atcoder.jp/)があります。 AtCoderではほぼ毎週末にコンテスト（大会のようなもの）が開催され、１万人ほどの参加者が実力を競い合っています。

年１回開催される大規模な大会としては、Google Code Jam(https://codingcompetitions.withgoogle.com/codejam), Facebook Hacker Cup(https://www.facebook.com/hackercup/)などがあり、優勝賞金は100万円超えです。 また、競技プログラミングの大会の慣習（？）として、上位者には記念Tシャツが贈られるというものがあり、上位1000位くらいに入るともらえます。

「なんか面白そう」「プログラミングをやってみたい」「パズルが好きで解いてみたい」くらいの軽い気持ちで参加してみましょう！

プログラミング言語を選ぶ

まず、問題を解くためのプログラミング言語に何を使うか決めましょう。 なんですが、自分の好きな言語、使い慣れた言語でよいと思います。

まず競プロってどんなものか触ってみるのが大事で、面白味を感じてきたら自分の好きな言語で極めるのもよし、別の言語に切り替えてみるもよしです。

競プロにおすすめの言語は C++ か Python です。 それぞれのメリット・デメリットを下記にまとめました。

言語 メリット デメリット C++ ・競プロで一番使われているので情報が得やすい ・AtCoderLibrary(AtCoder公式ライブラリ)はC++のみ提供されている ・プログラムの実行速度が速い ・競プロ以外でC++を活かせるシーンがあまりない Python ・文法がシンプルでとっつきやすい ・競プロ以外でも使えるシーンが多い（機械学習など） ・プログラムの実行速度が遅い

競プロにガチで打ち込みたいならC++, 勉強した言語を他のことにも活かしたいならPythonでしょうか。 でもどっち選んでも大丈夫です。

過去問を解く

過去問演習ではAtCoderProblems(https://kenkoooo.com/atcoder/)をぜひ活用しましょう。 過去にAtCoderで出題された問題を一覧で確認することができます。

競プロが初めてであれば、まずはA問題で感覚をつかむところからやっていきましょう。 競プロに慣れてきて実力をより上げたいときは、Difficulty（≒問題の文字色）が自分の色の一つ上のものを重点的に解いていくとよいです。

１色上の問題だと考えても手も足も出ないことが多発すると思います。 そういうときは解説を見て、問題への考え方・アプローチの方法を学ぶのがよいです。

解説に自分の知らないアルゴリズム、データ構造が出てきたときは成長のチャンスです。 そのキーワードでぐぐる、書籍で確認するなどして、次に類題を見たときに確実に解けるよう身につけておきましょう。

頻出分野を学ぶ

競プロでの基礎的な考え方、アルゴリズムなどはコンテストでよく出題されます。 私の思う頻出分野と解説記事を重要度順にざっくり書き並べてみました（上のものほど重要）。 上から順でも見ていくのもよいし、気になるものがあればそこから始めてもOKです。

参考URLがけんちょんさんの記事ばっかりになってしまった... でもとても分かりやすいのでおすすめです！

分野 参考URL 計算量の考え方 https://qiita.com/drken/items/872ebc3a2b5caaa4a0d0 https://atcoder.jp/contests/apg4b/tasks/APG4b_w 二分探索（にぶたん） https://qiita.com/drken/items/97e37dd6143e33a64c8c 累積和 https://qiita.com/drken/items/56a6b68edef8fc605821 全探索（再帰関数、bit全探索、next_permutation） https://drken1215.hatenablog.com/entry/2020/05/04/190252 https://qiita.com/drken/items/7c6ff2aa4d8fce1c9361 https://atcoder.jp/contests/apg4b/tasks/APG4b_ad?lang=ja https://blog.foresta.me/posts/enumerate_all_pattern/ 深さ/幅優先探索（DFS/BFS） https://qiita.com/drken/items/4a7869c5e304883f539b https://qiita.com/drken/items/a803d4fc4a727e02f7ba https://qiita.com/drken/items/996d80bcae64649a6580 動的計画法（DP） https://qiita.com/drken/items/dc53c683d6de8aeacf5a 最短経路問題（ダイクストラ法など） https://hfuji.hatenablog.jp/entry/2015/12/12/165413 素数列挙、素因数分解、約数など https://qiita.com/drken/items/a14e9af0ca2d857dad23 剰余の考え方 https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a

書籍を読む

競プロの本として下記が有名です。 難易度順に並んでいます（下に行くほど難しい）。

俗称 URL チーター本 https://books.google.co.jp/books?id=7jJyUOw49PQC&printsec=frontcover 螺旋本 https://books.google.co.jp/books?id=1We3DwAAQBAJ&printsec=frontcover 蟻本 https://books.google.co.jp/books?id=s40pvgbtOZ8C&printsec=frontcover

ただ、読んで内容をすべて理解するのはとても難しいです。 ざっと目を通しておいて、コンテスト中に「これ本に書いてあったかも」と気付けたらじっくり読み込む、コードを書き写すとかもありだと思います。

おわりに