Baekjoon Online Judge N0.14556 Balance - Senの競技プログラミング備忘録

www.acmicpc.net

概要

問題文はハングルオンリーなので、僕は機械翻訳で読んだ。

$2^1, 2^2, ..., 2^N$ グラムの重りそれぞれ1つずつある。あなたはこれらを一度に1つずつ、天秤に載せる。
天秤には左と右、両方の皿が存在する。載せる際、常に左の皿の重さが右の皿の重さ以上である必要がある。
このような天秤への載せ方は何通り存在するのか？ $10^9+9$ (普段とは違う！)で割ったあまりを答えよ。

ただし、異なる載せ方というのは、2通りの載せ方において、

重りを載せる順番が違う場合
順番が同じでも、1つ以上の重りにおいて載せた皿の左右が異なる場合

この2つのうち1つでも満たせば異なる載せ方とする。

制約：　1 <= N <= 10^5

ACするまで

1. 最初に載せるべき皿は左固定なので、何を載せるかを固定してから考える。->しかし、嘘解法と判明
2. 重りにおいて、基本的に重ければ重いほど選択の余地はなくなる。(これは2冪の重さなので、下位の重りをすべて足しても上位より軽いので、貪欲によく使われる性質)
3. 重りを置く順番の数列を考えて、重い順番から当てはめていく。
4. 手元で実験をしてみると、関係性が見える->AC!

考察

嘘解法

最初には、1回目に載せる重りを固定して、それで数えようと考えた。
1回目に重り $2^k$ を載せるのなら、それ以降

$2^{k+1}$ 以上の重さならば、左
そうでないのなら、左右任意

に載せてよいので、N-1回の重りの選択順番も考えて、 $(N-1)!2^{k-1}$ 通りになる。よって、1回目に載せる重りをすべて集計すると、 $(N-1)!(2^n-1)$ 通りになる。

これは嘘解法である。次のような場合を数え上げられない。
{2, 4, 8}の重りで

左に2g
左に8g
右に4g

嘘解法だと、左に2gを載せたら、右には4gを載せられないが、上のようにすれば載せられる。

解法

数え上げの数多くの典型アプローチで当たってみると、選択する順番の列ごとに何通りあるのか？を数え上げる、という選択肢がある。

Point
数列の数え上げは、ある順番(小さい順etc)に数を挿入していくという手法がある。(挿入DP)選びづらい要素から順に挿入していく。

重りについては、重ければ重いほど選択の余地が少ないということがわかる。なので、重い重りから挿入して、順番の列を作るとする。

よって、新しく挿入する重りは、今まで操作列に挿入したどれよりも軽い、ということである。

具体例としては、次のようになる。

f:id:Sen_comp:20200305170031j:plain

f:id:Sen_comp:20200305170054j:plain

これらから、

一番前に挿入すると、左に置くの1択敷かないので、もともとの場合の数と同じになる。
それ以外の場所では、挿入した時点では(左)-(右)の重さの差は、(証明1)より、これから挿入するものより大きいので、左においても右においても問題はない。よって、場合の数を2倍することに相当する。

(証明1)

重い順にk個の重りをすでに置いたとする。この時、左右の重さの差の最小値は、現時点での重さはすべて $2^{n-k+1}$ の倍数であることから、 $2^{n-k+1}$ である。しかし、これから挿入する重りの重さは $2^{n-k}$ で、これより小さいので、左右どちらに載せても問題はない。(完)

よって、このことから、すでにk個の重りを挿入し終えて、k+1個目(に小さいもの)を入れるとき、場合の数は $1+2(k-1)$ 倍される。

このkを1からNまでその倍率をひたすらかければ、答えが求まる。

ACソースコード：

#include<iostream>

using namespace std;

typedef long long ll;

const ll MOD = 1000000009;

int main(){
	ll N;
	cin >> N;
	ll ans = 1;
	for(int i = 1; i < N; i++){
		ans *= (1 + 2 * i);
		ans %= MOD;
	}
	cout << ans << endl;
	return 0;
}

一言

BOJ、システムが教育的じゃなさすぎるだろ。

Special Thanks

KKT89(@_KKT89), hotman(@hotmanww)との討論がこの記事を産みました。お二方に深く感謝します。