「今週のお題：最速の脱出手順」問題解答 ( CodeIQ )

はじめに

CodeIQという所で週次で出題される ( 最近再開された ) 「今週のお題」シリーズに解答しましたので、ネタバレです。

codeiq.jp

問題

既に問題は公開終了していますから、概要を。

• 入力値 ( nとします ) に対して、n段の階段と、そこに1人 or 複数の人 ( 同じ段には重複しない ) がいる場面を考えます。
• 1回の移動で、直下の段が空いている段の人は1段降り、そうでない人は留まります。一番下の段の人は ( 降り切ったということで ) いなくなります。
• そうして、何回の移動で全員が階段を降りることができるかを考え、「n段の階段でありうる人の配置」全てに対する回数の和を求めます。

例えばですが、4段で ○×○○ という配置 ( 右の方が低、○が人のいる段を表す ) の場合、
○×○○→×○○×→×○×○→××○×→×××○**→××××
で5回という数え方になります。

解答

以下が提出版のgolf解、Ruby(64)です。

m=[a=0];(2**gets.to_i).times{|i|a+=m[i]||=1+m[i&i*2|~i&i/2]};p a

まあ、(2**gets.to_i).times とある通り、計算量はΟ(2ⁿ)ですが、iteration毎の処理は高速なのでTLEにはなっていません。

解説

方針

まず前提として、n段の階段での人の配置は 2ⁿ-1通りです。なので、その配置毎の回数を調べて合計を計算するという方針が思い浮かびます。
ここで、人がいる段を 1、いない段を 0 としてbit表現すれば ( 低い段の方が低位の bit )、配置情報を 1～2ⁿ-1 の整数と1対1に対応づけることができます。例えば、先ほど出てきた ○×○○ という配置なら 1011(2) で、10進数の11 という事に。
後は、「ある配置から1回経った後の配置での回数」の関係を調べられれば、順々に各配置での回数が判明する、という寸法です。 すなわち、整数値 x に対応した配置での回数 f(x) に関して、1回後の配置に対応する整数値が y ならば、f(x)=1+f(y) という事です。必ず x＞y となることにも注意。○×○○ の配置の例を、対応する整数値も併記して再掲します。
○×○○ (11)→×○○×(6)→×○×○(5)→××○×(2)→×××○(1)→××××(0)
便宜上 f(0)=0 と置くことで、f(1)=1+f(0)=1, f(2)=1+f(1)=2, f(5)=1+f(2)=3, f(6)=1+f(5)=4, f(11)=1+f(6)=5 となります。

実装

という所で、提出版のコードを見易くしたのが次のコードです。

n=gets.to_i
ans=0
memo=[0]
1.upto(2**n-1){|i|
  step=1+memo[i&(i<<1)|~i&(i>>1)]
  ans+=step
  memo[i]=step
}
puts ans

残る問題は、「1回後の配置がどうなるか」です。
そこを step=1+memo[i&(i<<1)|~i&(i>>1)] としている、つまり1回後の配置に対応する数値が i&(i<<1)|~i&(i>>1) という計算で賄えるのがミソとなります。

1回後の配置の考え方

1回後の配置ですが、全体を一気に考えると混乱するかも知れません。しかしながら、実は各段については隣接する段の状況を考えるだけで良いのです。

• 元から人がいる段の場合
  直上の段から人が降りてくることは無いので、元いる人が降りるかどうか、つまり直下の段に人がいるかどうかが焦点になります。
  • 直下に人がいる ( ？(○)○ ) → 降りれないので残留 ( ？(○)× )
  • 直下に人がいない ( ？(○)× ) → 降りられるためいなくなる ( ？(×)○ )
• 元から人がいない段の場合
  直上の段から人が降りてくるかどうかが焦点であり、直下の段の影響は無くなります。
  • 直上に人がいる ( ○(×)？ ) → 新たに人が降りてくる ( ×(○)× )
  • 直上に人がいない ( ×(×)？ ) → 降りてくる人がいない ( ？(×)× )

着目している段、直上・直下の段の人の有無 ( 1,0 ) を、C,U,D とすると、次の表のような状態になります。

C	U	D	1回後のC	~C	C&D	~C&U
1	?	1	1	0	1	0
1	?	0	0	0	0	0
0	1	?	1	1	0	1
0	0	?	0	1	0	0

?の所は任意 ( don't care ) です。こうして整理すると、1回後のCのbitは、C&D|~C&U であることが分かります。
それで、このUは1つ上位のbitですから、配置に対応した数値 i からは、i>>1 と右シフトすることで、逆にDは i<<1 と左シフトすることで求めることができます。 各桁についての計算方法は同じになりますから、全ての桁の分をまとめてしまうことができ、結局元の数値 i に対し、i&(i<<1)|~i&(i>>1) が1回後の配置に対応した数値となる訳です。

最後に

という訳で、配置を扱うのにbit演算を用いることで高速な処理を可能にした訳ですが、計算量自体は全然削れていません。
f(2n)=1+f(n) とか、f(4n+1)=f(4n) 等の性質も活用して、なんとか多項式オーダーにできないかと思ったのですが…。ここら辺、上手い方法があれば是非知りたいところです。