📝

ARC 107 B - Quadruple の解説の解説

2022/12/10に公開約1,800字

https://atcoder.jp/contests/arc107/tasks/arc107_b

解説

https://atcoder.jp/contests/arc107/editorial/262
下の解説の解説で理解した上でも、茶色500レベルのおれには理解できないぞ

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

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

問題文の変形

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

まずは簡略化

  • 1<a,b<N , a+b=xxとなる個数を数えてみる
  • サイコロで考えると直感的に理解しやすく、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+bK小さいと言い換えられるので、
    P[a+b]P[a+b-K]の組み合わせの数を求めよ という問題と言い換えられる

kが負の場合を考える

  • 前のa+bの方がK小さいとKは負になる
  • Kだけ小さいのだから、前のa+ba+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)

チラシの裏

どうすれば解けたのか

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

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

学び

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

Discussion

ログインするとコメントできます