TopCoder SRM 507
……orz
Easy CubeStickers
問題
n枚のステッカーがあり、それぞれの色が与えられる。
このとき、ステッカーを立方体の各面に1枚ずつ貼り、
立方体を隣り合う面にあるステッカーの色は全て相異なるようにすることができるかを求めよ。
試行錯誤
同じ色のステッカーが三枚以上あっても、三枚使うことは出来ないので意味なし。
- 6色のステッカーがあるとき、
- 5色のステッカーがあるとき（2枚ある色が1色）
- 4色のステッカーがあるとき (2枚ある色が2色)
- 3色のステッカーがあるとき (2枚ある色が3色)
のときに条件を満たせるはず。
書いた。よく見直して送信。
Medium CubePacking
問題概要
Ns個の1x1x1の立方体およびNb個のLxLxLの立方体がある。
これらを直方体に、立方体の辺が直方体の辺に平行になるようにつめる。
（すきまがあっても良い）
このとき、全ての立方体を詰められる直方体のうち、最小のものの体積を求めよ。
試行錯誤
大きい直方体を一列に積み上げて、その上に小さい直方体を積めばいいんじゃないだろうか。
……それだと通らないサンプルがあってダメ。
底面がL〜2L x L〜2Lの直方体だけ考えればいいんじゃないの？
と思ったらNs=78, Nb=8, L=3という反例を見つける。
これ、みんなどんどん提出してるけどそんなに簡単な問題じゃないだろ……
直方体の体積Vを（Ns+Nb*L^3以上で）決める＞
その体積をもつ直方体にLxLxLの立方体が全部入る
という判定問題にはできる。
最悪でも一列に積み上げる場合で抑えられるので、調べるVはNs+Nb*L^3+100までに抑えられる。
だけど体積決めたときに直方体を全列挙なんて出来るだろうか。
Vは20億くらい。a≦b≦cとして、(20億)^(1/3) * (20億)^(1/2) * 100通りくらい調べないとだめ。
全然まにあわなくない……？
b,cの値を二分探索とかできるだろうか。できるわけない。
などと考えているうちに終了。
Hard
あけてない。
Challenge Phase
500の反例で落とせる奴いっぱいありそうだったのでソース見ていると、
次々と誰かに落とされていく。
一個も落とせないまま部屋で5〜6個の500が落ちた。酷い。
250でおかしそうなのに突撃して2ミス。酷い。
System Test
250は通った。けどねえ。。。
