yukicoder yukicoder no.349/350/351/352
3問目が分からなかった。つらい。最近競プロ出来てないからな…
No.349 干支の置き物
問題概要
干支の置物N個を1列に並べるときに、同じ干支が隣り合わないように並べることが出来るか判定せよ。
解説
例えば、干支#について、他のものをXとすると、#X#Xや#X#X#がギリギリOKなライン。一番多い干支の個数が半分より多ければ不可、そうでないなら可。
http://yukicoder.me/submissions/80975
No.350 d=vt
0<v<1の速度でt秒間等速直線運動をした。総移動距離を求めよ。ただし、小数点以下切り捨てで答えること。
解説
floor(vt)で終わりと思いきや、誤差が出る問題でした。Pythonでもダメだったので、vが小数4桁までしかないことを利用し、vを文字列で受け取って、10000倍した整数に変換しました。
http://yukicoder.me/submissions/81078
Pythonのfloatは多倍長には自然にならないみたいです。JavaのBigIntegerで殴れば良かったかもな…(Eclipse開くのが面倒だった)
No.351 市松スライドパズル
問題概要
白黒の市松模様の縦1列を1要素ずつ下にスライドしたり、横1列を1要素ずつ左にスライドしたりする。最終的に1番左上にある色は何色か。
解説
H,W≦10000で何かいいデータ構造無いか考えてたけれども、N≦100万でスライドをO(1)で処理しないと間に合わない…思いつきませんでした。
処理する順番を逆向きにして、最終的に1番左上にあるものはスタートはどこにあったかを探せばよいらしいです。
http://yukicoder.me/submissions/81302
No.352 カード並べ
問題概要
1〜Nの書かれたN枚のカードを数字の小さい順に机に置いて行く。机にM枚のカードが置いてある時、新しいカードは各カードの両端、もしくは間のM+1通りの置き方があり、カードを置くコストは両端なら1,カードの間なら両側のカードの積である。N枚のカードを置き終えた時のコストの期待値を求めよ。（1枚目のカードを置くときにもコスト1が生じる）
解説
N枚目を置くことを考えます。N-1枚のカードが机の上に置いてあり、その並び方は(N-1)!通りです。
両端に置くときはコストは2なので、全並び方で合計2*(N-1)!。
カードの間に置くとき、両側のカードの組み合わせは(N-1)C2=(N-1)(N-2)/2通り。これらの各積についてカードの位置は2枚のカードを1枚とみなして(N-2)通り、その他のカードの並び方が(N-3)!通りあるので、(1,2)の間にNを入れる通り数は全部で(N-2)!通り。他の組み合わせも同様です。
これらの和は2*(N-1)!+(1*2+1*3+...+1*(N-1)+2*1+2*3+......+(N-1)*(N-3)+(N-1)*(N-2))*(N-2)*(N-3)!です。
カードの並べ方が(N-1)!通り、新しくカードを置く置き方がN通りあるので、N!でこれを割ってあげればN枚目を置くことによって生じるコストの期待値が出せます。(因みに右側の積の部分を全て1に変えると、確率になり、その合計は1になるはずです）
そうすると、N枚目のカードを置くことによって生じるコストは、
となります。都合上、左右入れ替えて同じものは合わせて2で括ったうえで計算しています。
http://yukicoder.me/submissions/81255
余談ですが、この問題で最短実行時間を狙おうとして埋め込みましたが、むしろ遅くなりました。変数の宣言だけで遅くなるんですね…
感想
やられた…
来年度は受験になるから、余計実力落ちるんだよな…
