📝

ARC 107 B - Quadruple の解説の解説

2022/12/10に公開

Python

AtCoder

tech

解説

下の解説の解説で理解した上でも、茶色500レベルのおれには理解できないぞ

よく分かった解説を更に噛み砕く

毎度お世話になっております
方針は理解したのだけれども、vとか記号が多いと理解できない箇所も多いぞ
腹落ちするまで噛み砕くぞ!

問題文の変形

$a+b-c-d =a+b-(a+b)$ と考えられる
$a+b$ の箇所はどう考えれば良いのか考える

まずは簡略化

$1<a,b<N , a+b=x$ で $x$ となる個数を数えてみる
サイコロで考えると直感的に理解しやすく、 $N=6、x=2\sim12$ までとなることがわかる
個数は $x=2$ が1つ、…、 $x=7$ が6つ、…、 $x=12$ が1つだね
$N+1$ までは $a+b-1$ 個、 $2N$ までは $2N-(a+b)+1$ 個
つまり、 $\min(a+b-1,2N-(a+b)+1)$ 個の組み合わせがある

問題文に戻す

$a+b$ の組み合わせの個数の配列を $P[a+b]$ とする
今回求めたいのは、 $a+b-(a+b)=K$ となる組み合わせの数
式を言い換えると、前の $a+b$ と後ろの $a+b$ の差が $K$ となる組み合わせの数
差が $K$ ということは、後ろの $a+b$ が $K$ 小さいと言い換えられるので、
$P[a+b]$ と $P[a+b-K]$ の組み合わせの数を求めよ という問題と言い換えられる

kが負の場合を考える

前の $a+b$ の方が $K$ 小さいと $K$ は負になる
$K$ だけ小さいのだから、前の $a+b$ は $a+b-K$ 、後ろは $a+b$ となる
求めるのは $P[a+b-K]$ と $P[a+b]$ の組み合わせの数 となるため $K$ が正のとき変化はない
従って、 $K$ は絶対値として扱って大丈夫

実装する

上記考察は大変だったのにコードにするとすごく簡潔になるなぁ

n, k = map(int,input().split())
# a+b=v時の個数の配列を作る
# a,bの最小値は1なので、vは2から始まるため埋めておく
p = [0, 0]
for v in range(2, 2 * n + 1):
    tmp = min(v - 1, 2 * n - v + 1)
    p.append(tmp)

res = 0
# Kが正だと p[v]とp[v-k]の組み合わせ
# Kが負だと p[v-k]とp[v]の組み合わせ
# 組み合わせは積なので計算順序は無視していいので、Kは絶対値にする
k = abs(k)
# c+dがa+bより、k小さい組み合わせを数える
for v in range(k, 2 * n + 1):
    res += p[v] * p[v - k]
print(res)

チラシの裏

どうすれば解けたのか

式の変形に気づく $a+b-c-d =a+b-(a+b)$
$a+b$ の解毎の個数をがわかれば、 $P[a+b] \times P[a+b-k]$ の総和が解になると気づく
$a+b$ を関数化できる $\min (a+b-1,2N-(a+b)+1)$
等式→配列同士の組み合わせ計算に変わるので、途中で混乱せずに何やってるのか把握する力

これでDiff600クラスで茶色の中間なのだと思うと、世界の広さを実感できるね!

学び

組み合わさっているだけかもしれないのでバラせないか考える
何通り→組み合わせを考える→個数の列挙と考えてみる
問題文が理解できない場合は、身近なもので例えたり手を動かすこと!
組み合わせだとトランプとかサイコロは脳みそが直感的に処理しやすいっぽいぞ
頭足りてない分は手を動かしてカバーするしか無いのだ!
等式から配列の組み合わせに世界が代わり、こんなのもあるのか!!と謎の感動
1問で色々考えられるので競技プログラミングはいいコンテンツだなぁ

解説

よく分かった解説を更に噛み砕く

問題文の変形

まずは簡略化

問題文に戻す

kが負の場合を考える

実装する

チラシの裏

どうすれば解けたのか

学び

Discussion