GCJ 2008 Round 1B

Round 1A の問題が比較的ぬるめに設定されていて、ボーダーがおおよそ分かっていたので、小さい入力だけ全部力技で通せばいいや、という感じでスタート。40点で148位という結構微妙なスコア...。

A

N本の木の座標が与えられる。木は格子点上にある。任意の3本の木の中心の座標のうち、格子点上に乗る組み合わせはいくつあるか答えよ、という問題。

取り敢えず木の本数が少ないうちはN^3探索。で、木の本数が多くなってきたら、x座標とy座標の3で割った余りから、9種類に分類する。分類の選択は9^3通りで、各分類から何本取り出すか、というのを考えればうまくいく。

B

AからBまでの数のうち、P以上の素数で割り切れるものを同じグループにするという処理をした後で、グループはいくつできるか、という問題。

全然分からない。

C

N番目のカードがNのとき、そのカードを取り除く、という処理を行う。カードの残数が少ない時は、途中で先頭に戻って数える。1,2,...,kという順番でカードを取り除けるようなカードの並びの、特定のインデックスにあるカードを答えよ、という問題。

任意の位置への挿入がO(1)でできるデータ構造があれば一瞬ですが、残念ながらそんな便利なものはありませんでしたよ、という問題。