162.1

一昨日のSRM362の結果が無効化されたので、カッとなってやった。

250

長方形の紙の二辺と、長方形の箱の二辺が与えられるので、紙を折りたたんで箱の中に入れる時に必要な折りたたみ回数を答えよという問題。ただし8回よりも多い場合には-1を返すこと。

折りたたむという問題なので、紙の各辺の長さを折るたびに半分にしていくのだけれど、精度とかを考えるとすると、箱の大きさの方を倍にしていく方が安全かも。8回なのでどちらからやっても同じではあるけれど。どちらの方向にも折れる回数は高々8回なので、64通り折ってみて、入る一番小さいのを答える、というのが正解。

頭の悪い解法は、短い方の辺と長い方の辺を比較して、入るならそれまでの回数を返す。短い方の辺が入る場合は長い方の辺を入れないといけないので、長い方の辺を折る。(実際には箱の長い方の辺の長さを倍だと思うことにする。)短い方の辺が入らない場合には、箱の短い方の辺の長さを倍だと思うことにする。かなりややこしいことをやってるけれど、多分問題のない方式であることは、ちょっと考えれば分かるかなぁ...。オーダーがNなので、ちょっと嬉しい状況があるかも知れないけれど、多分ない。

500

円筒の半径と箱の周囲の長さが与えられるので、その箱の中に円筒はいくつ詰め込めるかを答えよという問題。ただし各列に複数本入る場合にはちょっとだけゆとりをもたせること、という注釈がついている。

入れ方は長方形に入れるか、六角形状に入れるか。ただし六角形の場合には各層の長さが同じものと、1違いが交互に出るものとがあるので、実質3通りを考えれば良い。横の長さを計算して縦に詰め込んでいくのを、横の長さを増やしつつやって、横方向に入りきらなくなったらおしまい。横には3000本も入らないので、TLEの心配はないけれど、思ったよりも実行時間は長かったかも。(実装が悪い。)

各列に複数本...というくだりを真面目に実装すると、1本だけの部分がうまくいかなくて、ルーチンを分岐させてやらないといけないなぁと思うのだけれど、少なくとも1本は入る、という注釈もあったので、返す値の最小値を1から始めれば問題ないというなんともな問題。

1000

大きい整数が入力として与えられるので、それよりも小さい整数のうち、0以外の数字を同じ数だけ含むものはいくつあるか答えよという問題。

問題の定義はもっとPermutationについて語っているので、Permutationを真面目に考える問題であることは明らか。先頭の桁を現在の値よりも小さいものにセットした場合のPermutationを数え上げる、というので順次先頭の桁を決定していけばおしまい。Permutationの計算時に、桁数によってはlongから溢れる(多分)ので、そこだけ注意する問題。JavaだとBigInteger使えばそこまで。これってどう見ても500点問題じゃないかなぁ、今だと。