読者です 読者をやめる 読者になる 読者になる

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

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

ABC#008

A問題はそろそろ割愛してもいい気がだいぶするんですが一応、、、
はてなtex記法が使えるらしいので見づらい数式の部分を順次直していこうと思います。

- A問題「アルバム」

(http://abc008.contest.atcoder.jp/tasks/abc008_1)

問題概要:
S以上T以下の数字の個数をこたえる問題です(ざっくり)

解法:
T-S+1を出力するだけです。

ソースコード:



- B問題「投票」

(http://abc008.contest.atcoder.jp/tasks/abc008_2)

問題概要:
構成員の名前ごとに投票された票数をカウントしていき一番票数の多い人の名前を出力する問題です。
コンピュータで集計する以上明らかに数字を構成員に割り当てて番号で投票するようにしたほうがいいですね。

解法:
stringのvector(可変長配列)を使って投票された文字を検索、なかったらvectorに追加、という手法で間に合います。
今回はあえて練習もかねてSTLのmapを使って実装してみました。
mapでは添え字演算子[]を使ってそのキー(ここではstring)を持つ要素にO(logn)でアクセスできるのですが、仕様としてそのキーを持つ要素がなかったときは新たに0の値をもつ要素を作成してくれます。そのため非常に楽な実装ができました。

ソースコード:



- C問題「コイン」

(http://abc008.contest.atcoder.jp/tasks/abc008_3)

問題概要:
期待値計算をする問題です。期待値計算はAtcoderでは割と多めに出ている気がするので練習が必要かも。

解法:
コインが100枚存在するので並べ方は100!通り、この時点で全探索は切り捨てます。
そこでコイン1枚1枚に着目し、各コインが表である確率を求めます。
i番目に大きいコインをc_{i}とします。
c_{i}が表である確率をp(c_{i})とすると、
表のコインの合計枚数の期待値は\sum_{i=1}^{N} p(c_{i})と求められます。
p(c_{i})について考えます。
適当にコインを並べます。すると、c_{i}のコインはそれよりも左にあるc_{i}以下のコインによって表裏が変化します。
よって、c_{i}のコインが表である確率はその約数の個数によって決定します。
d=c_{i}の約数のコインの枚数(自身を除く)とすると、
p(c_{i})=\frac{\frac{d}{2}+1}{d}と求められます(d個のコインのどの間にコインが入るかという組み合わせの問題)
これでp(c_{i}が求められました。これで解を出力できます。
計算量はそれぞれの約数のコインの個数を調べるのにO(N),それをN枚のコインに対して行うのでO(N^2)



ソースコード:

やはりtexは数式が書きやすくていいですね。


- D問題「金銭ゲーム」

(http://abc008.contest.atcoder.jp/tasks/abc008_4)

問題概要:
長方形の全てのマスに金塊が埋まったマップがあります。
N個のクレーンが配置されておりそのクレーンは十字方向の連続した金塊を取得することができます。
クレーンを動かす順番を適切なものにしてとれる金塊の量を最大にしたい。

解法:
領域分割の問題で,ABC#005と同じようにDPもどきを使います。
dp[i][j][w][h]を(i,j)から(w,h)で囲まれる長方形の区間での最適解とすると、(i,w行とj,h行は含まないとする)
(i,j)から(w,h)内にあるクレーンの座標を(s,t)としたとき
dp[i][j][w][h]=
max((s,t)のクレーンを使ってとれる金塊の量+dp[i][j][s][t]+dp[s][j][w][t]+dp[i][t][s][h]+dp[s][t][w][h])
という漸化式で求められますので、メモ化再帰を用いることで高速に計算できます。
(s,t)のクレーンでとれる金塊の量はよくよく考えると(w-i+1)+(h-j+1)-1で求められるため領域内であればクレーンの座標に依存しません。
メモ化再帰の方法は、dp[i][j][w][h]の初期値を-1として、
dp[i][j][w][h]にアクセスしたときに値が-1なら未計算なので再帰呼び出しをして値を書き換えます。
dp[i][j][w][h]が計算済みなら-1以外の値を持っているはずなので計算せずに配列から値をもってきます。

時間計算量はここまでの流れでO(N^4)なので間に合うのですが、空間計算量はO(WH^2)WH\le 10^{12}なのでだいぶアウトです。
そこで座標圧縮という手法を使います。k番目のクレーンの座標を[tex{x_k,y_k}]とすると、
dp[i][j][w][h]においてi,wはx_kのとる値、j,hはy_kのとる値しか種類が存在しません。従って最大でN種類すなわち30種類以下の値しかとりません。
そのためそんなに配列は必要なく、例えば
1,10,100,1000というx座標の値が順番に並んでいたとしたら
1,2,3,4という風に圧縮し、A[1]=1,A[2]=10というように圧縮前の座標を配列で管理してやればよいのです。これを使えば空間計算量はO(N^4)となって30^4=810kbyteぐらいで抑えられるのでめでたしめでたし。
ソースコード: