166.1

250

数字の配列が与えられるので、2進数にした時に1の数が少ないものが前にくる、という条件を足した上で小さい順にソートせよという問題。

Comparatorをちゃんと使えれば早いんだろうなぁと思いつつ、いずれにせよクラスを実装しないといけないので、実はバブルソートで書くのが実装速度上は一番早いのかなぁという感じの問題。

650

セルオートマトンの周期を答えよという問題。ただし循環しているので、ローテーションして同一のものは同一とみなす。また、反転して同一のものも同一のものとみなす。

問題をよくよく見てみると、最後の方に16383ステップが上限と書いてある...。セルオートマトンのサイズは30文字で、文字は2種類しかないので、60通りのパターンのうち、辞書順で一番小さいものを毎回計算しても60回。1M回くらい文字列演算をやって、それを履歴テーブルにでも積んでおけばおしまい。履歴テーブルはハッシュテーブルにしてみた。

思ったよりも実行時間が長くなったのはStringクラスでガリガリ計算したせいだけれど、TLEはしない程度なので問題なし。ステップ数がもうちょっとあって、別アプローチにならざるを得ない問題なら650点でもいいけれど、これは500点問題止まりじゃないかなぁ？

900

無限数列2つの和からできる無限数列のN桁目の数字を求めよという問題。正整数を小さい順に並べたものと、正整数の2乗を小さい順に並べたものが無限数列。

各数列のN桁目から数桁(繰り上がり用)のために求めて、それらを加算すればおしまい。ただしN桁目を求めるためには、N桁の数がいくつあって...、というようにしてlogのオーダーで計算しないとダメだよ、という問題。2条の数がいくつずつあるかは、10のN乗の平方根を切り上げたりすると求まるので、特に実装が面倒という以外に問題はなさそう。