競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

ABC#006

更新が遅れたのは主にこの回のB問題のせいです。

- A問題「世界のFizzBuzz

(http://abc006.contest.atcoder.jp/tasks/abc006_1)

問題概要:
FizzBuzzの定義は
3で割り切れる数字のとき「Fizz」,5で割り切れる数字のとき「Buzz」,
両者で割り切れる数字のとき「FizzBuzz」と発言し、
それ以外の数字の時はそのまま数字を発言するというルール。
プログラマのテストとして使われた事例もあるようなので2分ぐらいで書けるようにしとくといいかもしれないです。

解法:
3で割り切れる時と3が含まれるときにはアホになってyesと出力しましょう。
といっても入力が1から9なので前者の条件のみでいいです。

ソースコード:
http://abc006.contest.atcoder.jp/submissions/342860


- B問題「トリボナッチ数列」

(http://abc006.contest.atcoder.jp/tasks/abc006_2)

問題概要:
この問題を見た瞬間TDPCのT問題を思い出して闇に落ちました。
A_k=A_{k-1}+A_{k-2}+A_{k-3},A_1=0,A_2=0,A_3=1
という漸化式で定義されるトリボナッチ数列を解く問題です。

解法:
MODをとる問題なのですがオーバーフローに注意
MODをとるときには以下の計算方法を使用しましょう。
リンク:あとで
[解法1]
動的計画法の典型的な例です。A_iをiの小さい順に解くことでO(K)=10^6で解くことができます。
これで十分間に合います。
[解法2]
コンパニオン行列を用いた解き方です。
A_k = \begin{bmatrix} 1 & 1 & 1 \end{bmatrix} \begin{bmatrix} A_{k-1} \\ A_{k-2} \\ A_{k-3} \end{bmatrix}
と行列の式で表すことができます。

ここで、B_k=\begin{bmatrix}A_{k-1}\\ A_{k-2}\\ A_{k-3}\end{bmatrix}とすると、
A_k=\begin{bmatrix}1& 1& 1\end{bmatrix}*B_kとなります。ここまでは整理しただけです。

ここで、N=\begin{bmatrix}1& 1& 1 \\ 1& 0& 0 \\ 0& 1& 0\end{bmatrix}という形の3*3行列を使って、
B_{k+1}=N*B_kというように表せます。このNをこの数列のコンパニオン行列といいます。
すると、B_{k+2}=N*B_{k+1}= N * N * B_k=N^2 * B_kというように表せるので、
B_{k+4}=N^k *B_4というように表せ、B_4=\begin{bmatrix}A_3 \\ A_2 \\ A_1\end{bmatrix}は初項なので、A_{k+4}が初項*係数の形で表せるようになります。
ここで、N^kについてkを2進数展開すると、
k=B_{maxbit}B_{maxbit-1}B_{maxbit-2}...B_{2}B_{1}B_{0}
=\sum^{maxbit}_{i=0} 2^iB_i
N^k=N^{ \sum^{maxbit}_{i=0}2^i *Bi}\\
 =N^{2^0*B_0}*N^{2^1*B_1}*...N^{2^{maxbit} *B_{maxbit}} \\
=\prod_{i=0}^{maxbit}N^{2^i*B_i}
というように展開できます。
面倒な計算が続きましたが、
N^1,N^2,N^4...が事前に求まっていればA_kが求められるということです。
N^4=(N^2)^2,N^8=(N^4)^2というように求められるのでこれらは\log nで全て計算できます。
行列の乗算にm^3必要なので、O(m^3\log n)で求められ、
この問題ではm=3,n=10^6なので3^3\log 10^6\le2000ぐらいの計算で済みます。

[解法3]
きたまさ法と呼ばれる手法でコンパニオン行列で行う計算を行列を用いずにO(m^2\log n)で解く方法です。
定数係数で表されるm項間漸化式においてとても有効な方法なので覚えておいて損はないと思います。
この方法もあとでまとめ...ました。

m項間漸化式の高速なアルゴリズム - 競技プログラミングをするんだよ


ソースコード:
通常DPhttp://abc006.contest.atcoder.jp/submissions/340277
コンパニオン行列http://abc006.contest.atcoder.jp/submissions/340433
きたまさ法http://abc006.contest.atcoder.jp/submissions/342478


- C問題「スフィンクスのなぞなぞ」

(http://abc006.contest.atcoder.jp/tasks/abc006_3)

問題概要:
2本、3本、4本の足を持った人をN人組み合わせて足の合計本数をM本にするというもの。これを解くだけで留年が回避できるならおいしいです。

解法:
組み合わせの総当たりをしようとすると計算量がO(3^N)とかになってNの最大が10^5なので間に合わなくなります。
解を一つだけ出せばよいので解を限定します。
1.Mが奇数の場合、3本の足を持つ老人が奇数人である必要があります。
2.老人が2人以上いる場合、老人二人=大人一人+赤ちゃん一人=2人で6本の足という結果が同等です。
1、2から、Nが奇数のとき、老人の人数は1,Nが偶数のとき老人の人数は0と決め打ちして、変数を大人と赤ちゃんの二つに減らすことができます。
以上から、N'=N-1(Mが奇数),N(Mが偶数),M'=M-3(Mが奇数),M(Mが偶数)とすると、
大人の人数をa,赤ちゃんの人数をN'-aとしたとき
2*a+4*(N'-a)=M'という等式が成り立ちます。
これを変形すると。a=2N-M/2となるので大人と赤ちゃんの人数が決定できます。
よってO(1)で出力が可能です。
ソースコード:
http://abc006.contest.atcoder.jp/submissions/340272



- D問題「トランプ挿入ソート」

(http://abc006.contest.atcoder.jp/tasks/abc006_4)

問題概要:
大富豪とかでよく手札並べるあれです。初期状態からソート状態にするのに必要な移動回数の最小値を求めよ。

解法:
最長部分増加列を抽出して、それ以外の部分のみ移動させるのが最小です。
つまりもともとソートされてる部分は動かさなければいいのです。
したがって、カード枚数N-最長部分増加列の長さが答え。
最長部分増加列の長さは動的計画法で求められます。
[シンプルな実装方法]
カードがa_0,,,a_i,,,a_{N-1}として与えられたとき
dp[k]=「kを最大値とする部分増加列」の最大の長さとして定義。
すると,dp[ a_i ]=max(dp[j)+1),(0\le j < a_i)としてO(N)で各要素が求められる。
よってdp[ a_0 ]からdp[ a_{N-1} ]まで順に求めるとO(N^2)で求められる。
[もう少し高速化]
最長部分増加列の長さはもっと高速に求められる。
dp[k]を「長さがkである部分増加列」の最終項の最小値と定義すると配列dpは常にソートされた状態となる。
a_iを追加するとき、dp[l-1] < a_i < dp[l]となるような最小のlを求めてdp[l]=a_iとすればよい。
dpが既にソートされているのでこのlを見つける動作は二分探索を用いてO(\log n)でできる。
C++STLのalgorithmにはこの動作を行うlower_boundという関数が用意されているのでこれを使うと楽です。
この結果計算量はO(n\log n)で解を出力できます。

ソースコード:
http://abc006.contest.atcoder.jp/submissions/340256