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

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

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

ABC#003

ABC

D問題の問題文を読み飛ばしていたせいで2時間か3時間ぐらい浪費しました。春休みでよかった、、、
#003は数学(?)の知識をそこそこ要求されたので疲れました。

- A問題「Atcoder社の給料」

(http://abc003.contest.atcoder.jp/tasks/abc003_1)

問題概要:
働いた分の給料を全てもらえない可能性が高い某社の給料の期待値を計算します。100面あるダイスとかほぼ球ですよね、、、

解法:
x面ダイスを振ってyが出た時、もらえる給料は(1/x)*y*10000です。これの平均値を求めると
(Σ i [1≤i≤x])*10000*(1/x)
となるので(Σ i) を(x*(x+1)/2)に変換して終わりです。
割り算するときに浮動小数点の計算となるように手を加えることを忘れないようにしましょう。

ソースコード:
http://abc003.contest.atcoder.jp/submissions/339084
#002でcoutでのWAを食らってから浮動小数点の出力はprintfを使うよう心がけています。本当はcoutのフォーマットいじったほうがいいんでしょうけども。


- B問題「Atcoderトランプ」

(http://abc003.contest.atcoder.jp/tasks/abc003_2)

問題概要:
アルファベットとジョーカー的な役割を持つ'@'があるトランプを使ったゲームです。与えられた二つの文字列の照合問題ですね。

解法:
二つの文字列を最初から走査していきます。二つの文字列をA,Bとして解きます
1.文字が同じ場合:次の文字へ
..ここで同じアルファベット同士はOK
2.文字が違う場合
2.1 A[i]が@ならば,A[i]とB[i]を入れ替える
..ここでどちらかが@ならB[i]が@になるように交換される
2.2 A[i]がatcoderのどれでもない、またはB[i]が@でない
..文字列の不一致が確定する。
このような手順で漏れなく照合できます。

ソースコード:
http://abc003.contest.atcoder.jp/submissions/339088


- C問題「Atcoderプログラミング」

(http://abc003.contest.atcoder.jp/tasks/abc003_3)

問題概要:
N個の動画からK個選び、どの順番で選べばレートがもっとも上がるかというスケジューリング問題です。
見るだけで成長したら苦労しないので解いていきます。

解法:
レートは0からスタートする。見る動画のレートをx1,x2,x3,,,xkとし、i個目の動画を見終えた時のレートをT[i]とすると、
T[i]=(xi+T[i-1])/2
これを展開すると、T[k]=Σ[1≤i≤k]xi/(2^(k-i+1))となる。
したがって直感的に分母が小さいものに大きいレートのものを順に当てはめていけばよい。

ソースコード:
http://abc003.contest.atcoder.jp/submissions/339093
余談ですがqsortよりもSTLのsortのほうが早いらしいです。オーダーは変わらないので競技プログラミングにはさほど影響しないと思いますが。


- D問題「Atcoder社の冬」

(http://abc003.contest.atcoder.jp/tasks/abc003_4)

問題概要:
部屋を区画に分ける問題。制約が結構多くてしっかり読まないと詰みます。(詰みました)
R行C列の部屋からX*Yの長方形を一つ決めてその中にデスクとサーバーを設置します。このときのデスクとサーバーの配置の組み合わせの総数を求めよという問題です。
注意事項として、長方形の4辺(壁)のそば(内側)には必ず何かが置いてなければならない。(これ読み飛ばして余計なことしてた)

解法:
1.R*Cの部屋にX*Yのスペースを一つ配置するパターンの数は(X-R+1)*(Y-C+1)で求められる。
2.X*Yのスペースを置く位置を決めたらその中に配置するデスクとサーバーラックの置き方の組み合わせの総数を求める。
3.このとき、壁のそばに必ず何かなければいけない

例)d:デスク l:ラック 。:何もない
X=Y=3のとき、
[OK]
。d 。
d 。。
。。 l
[NG]
d d 。
d 。 d
。 。 。
下の壁のそばに何もない

そこで以下のように漸化式を定義する。
T[n][m]:n*mの長方形で4辺のそばにdまたはlが存在するdとlの配置の組み合わせの総数
S[n][m]:n*mの長方形内にdをD個、lをL個配置する全ての組み合わせの総数
すると、
S[n][m]=Combination(nm,D)*Combination(nm-D,L)
=S[n-1][m-1]+S[n-1][m]
T[n][m]=S[n][m]-(Σ(n-i+1)*(m-j+1)*T[i][m]) [1≤i≤n ,1≤i≤m ,(i,j)!=(n,m)])
(nm)<(D+L)のときはT[n][m]=0
これをDP(メモ化再帰)を使って解く。T[X][Y]が解。
S[n][m]はあらかじめDPを使って全通り求めておく。
計算量はS[n][m]の計算にO(XY^2)=810000
T[n][m]の計算にO(((XY)^2))=810000(実際は20万程度)

ソースコード:
http://abc003.contest.atcoder.jp/submissions/339259
mod使う問題は苦手意識があったので通って本当に良かったです。