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

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

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

ABC#011

ABC

- A問題「来月は何月?」

(http://abc011.contest.atcoder.jp/tasks/abc011_1)

問題概要:
頭が悪いので今月が何月かはわかるけど来月が何月かわかりません(困惑)

解法:
%12して1を足すだけです。
入力が12のときは剰余で0になってから1加算されます。

ソースコード:
http://abc011.contest.atcoder.jp/submissions/344371
デバッグなしで提出したら何度かWAになった残念な問題です。

- B問題「名前の確認」

(http://abc011.contest.atcoder.jp/tasks/abc011_2)

問題概要:
アルファベットのフォーマットをします。
仕事ということはこれだけでお金がもらえるのでしょうか。

解法:
一般的な文字コードでは'a'~'z','A'~'Z'が連続した配置になっているため、大文字と小文字の文字コードの差は常に等しいことを利用します。
差をXとすると、1文字目が小文字ならXを足し、2文字目以降の小文字でない文字からXを引くだけです。

ソースコード:
http://abc011.contest.atcoder.jp/submissions/344368


- C問題「123引き算」

(http://abc011.contest.atcoder.jp/tasks/abc011_3)

問題概要:
爆発までのカウントを減らして相手に渡す爆弾ゲームに似ている気がします。

解法:
DFSの展開方法にグリーディーを用います。
DFS要素はほとんど0に近いです。
入力でNが与えられ、rest=100とすると
3引いた数がNGでないなら3減らし、restを1減らします。
3がだめなら2を、それでもだめなら1をという感じです。

ソースコード:
http://abc011.contest.atcoder.jp/submissions/343944


- D問題「大ジャンプ」

(http://abc001.contest.atcoder.jp/tasks/abc011_4)

問題概要:
ランダムで四方に一定距離ジャンプをします。ちょうどN回のジャンプで目的地に着きたい。

解法:
まず全探索について考えます。
目的地へのマンハッタン距離が一回のジャンプの距離Dの倍数でないときは絶対たどり着けないです。
よって座標をまずDで割って圧縮しましょう。以下座標をDで割った座標平面での議論です。
N回目のジャンプをしたとき、あるマス(i,j)にたどり着く確率は
N-1回目のジャンプをしたときの( (i,j)の四方のマスにたどり着く確率) * \frac{1}{4}です。
これを1...N回目のジャンプまで全て求めれば解が求められるのですが、O(N^3)となり計算量が大きすぎます。
そこで、まず座標(X/D,Y/D)(x,y)とします。
(x,y)にN回のジャンプでたどり着ける確率は(|x|,|y|)にN回のジャンプでたどり着ける確率と同じです。
したがってx=|X/D|,y=|Y/D|として目的座標を(x,y)とします。
このとき、x座標の正方向に進む回数をxp,逆方向をxmとし、同様にy座標の正方向をyp,逆方向をymとします。
するとx=xp-xm,y=yp-ymとなり,xp+xm+yp+ym=Nであるので、連立させると
N=2xp+2yp-x-yとなり、はこの方程式は2変数です。xpを決めるとypも自動で決定するので、xpについて0からNまでループさせましょう。
あるxp=xiを決めたとき、yp=\frac{N+X+Y+2xi}{2}が整数で0 \le yp\le Nが成り立つものを加算すればOKです。
,,,なのですが、このままでは確率の計算が少々面倒です。
ある二つのものから一つのものを選ぶという動作をN回繰り返すとき、ある一方が計R回選ばれる確率は\frac{{}_N C _R}{2^N}です。
\frac{{}_N C _R}{2^N} = \frac{\frac{{}_{N-1} C _{R-1}}{2^{N-1}}+\frac{{}_{N-1} C _R}{2^{N-1}}}{2},
すなわち、T(N,R)=\frac{{}_N C _R}{2^N}=(T(N-1,R)+T(N-1,R-1))/2で求められるため、動的計画法で事前に簡単に求められます。
これを使って、まずN回のジャンプのうち上下方向にジャンプする回数がV回で左右方向にジャンプする回数がN-Vだったとすると、その確率はT(N,V)で、事前に求めていればO(1)です。
また、yp+ym=V,yp=\frac{V+y}{2}となるため、Vが決まればypが一意に決まります。ここで、V+yが偶数でない,ypがNを超えるときは成り立たないことに注意が必要です。
V回中yp回を正方向のジャンプをする回数はT(V,yp)ですので事前に求めておけばO(1)です。
したがって、Vについて0からNまでループを行い、求められた確率の合計が解となります。
したがって、組み合わせを事前に求める回数と繰り返しの合計が計算量となりますのでO(N^2)で求められます。

ソースコード:
http://abc011.contest.atcoder.jp/submissions/343937