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

yukicoder yukicoder no.349/350/351/352

3問目が分からなかった。つらい。最近競プロ出来てないからな…

No.349 干支の置き物

問題概要

干支の置物N個を1列に並べるときに、同じ干支が隣り合わないように並べることが出来るか判定せよ。

No.349 干支の置き物 - yukicoder

解説

例えば、干支#について、他のものをXとすると、#X#Xや#X#X#がギリギリOKなライン。一番多い干支の個数が半分より多ければ不可、そうでないなら可。

http://yukicoder.me/submissions/80975

No.350 d=vt

0<v<1の速度でt秒間等速直線運動をした。総移動距離を求めよ。ただし、小数点以下切り捨てで答えること。

No.350 d=vt - yukicoder

解説

floor(vt)で終わりと思いきや、誤差が出る問題でした。Pythonでもダメだったので、vが小数4桁までしかないことを利用し、vを文字列で受け取って、10000倍した整数に変換しました。

http://yukicoder.me/submissions/81078

Pythonのfloatは多倍長には自然にならないみたいです。JavaのBigIntegerで殴れば良かったかもな…(Eclipse開くのが面倒だった)

No.351 市松スライドパズル

問題概要

白黒の市松模様の縦1列を1要素ずつ下にスライドしたり、横1列を1要素ずつ左にスライドしたりする。最終的に1番左上にある色は何色か。

No.351 市松スライドパズル - yukicoder

解説

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が生じる)

No.352 カード並べ - yukicoder

解説

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枚目のカードを置くことによって生じるコストは、  \displaystyle{\frac{2}{N}+\frac{2\sum_{i=1}^{N-2}\frac{(N+i)(N-i-1)}{2}i}{N(N-1)}}となります。都合上、左右入れ替えて同じものは合わせて2で括ったうえで計算しています。

http://yukicoder.me/submissions/81255

余談ですが、この問題で最短実行時間を狙おうとして埋め込みましたが、むしろ遅くなりました。変数の宣言だけで遅くなるんですね…

感想

やられた…

来年度は受験になるから、余計実力落ちるんだよな…