GCJ 2013 Qualification Round

その他 参加ログ

4問中ABCが解けて170pt、636位。

A. Tic-Tac-Toe-Tomek

4x4ボードにX,O,Tがあって、Tはワイルドカード的なものとして、どっちが勝ってるか、引き分けか、勝負中(決着してなくてまだおける状態)か。


やるだけ。
縦横ななめについて、Oがそろっているか、Xがそろっているかを確認。
そろっていたら、どちらかの勝ち。
どちらも勝っていなくて、空いてるマスがあれば、勝負中。
それ以外は引き分け。

B. Lawnmower

NxMのフィールドが100mmの草ボーボー状態。それぞれのマスについて目的の高さが与えられるので、直線的に進める草刈り機を使って草を刈る。この草刈り機は何度もフィールド外で高さ設定でき、h以上の草とであったらhまで刈り取る。すべてのマスを目的の高さにすることができるか否か。


考えてみると、以下の条件が見つかる。
あるマス(i,j)をhにするためには、前後方向でその高さに刈り取れるor左右方向でその高さに刈り取れる、ことが必要がある。
ある方向で、(i,j)をhで刈り取るためには、その方向の他のマスの高さがh以下であればよい。

C. Fair and Square

1以上の整数で、その数が回文数でかつその数のルートも整数で回文数、となるような数をFairでSquareである数という。A〜Bの中でそのような数がいくつあるか答える。
1<=A<=B<=10^100


条件がやばい。多倍長必須とか。。。
10^14までは、列挙できるので実験して法則性を見てみる。
整数aとa*aを出力してみると、10以上でaは0,1,2のみしか出てこないことがわかる。
それでもaの候補の3^50は多すぎる。
さらに見てみると、あるFairでSquareな数「a*a」について、aはFairでSquareな数「b*b」のbを拡張してできていることがわかる。
拡張とは、b*bが奇数の時は、例えばnnnmmのnの部分をreverseしてmmの代わりにいれたもの、b*bが偶数の時は、例えばnnnmmmのnとmの間に0,1,2をいれてみたもの。
FairでSquareな数はFairでSquareな数から生成されるならかなり少なくなるので、生成できそう。(ちゃんと証明できない、、、)
小さい時であっているようなので、これをあらかじめ列挙しておいて、2分探索でN以下の個数を出せるようにすれば解ける。


D. Treasure

未読。

反省

Cの証明できてない。
Cの2分探索のとき、頭働いてなくて、適当な2分探索してからその前後をいくつか確認してN以下になる個数を計算してて、ひどい。