284.1

微妙なセット...。スタイル作るのが恐ろしく面倒だということが分かったので、フォントを無視するようにIEの設定をいじってみた。(他の人にやさしくないなぁ。)

250

3辺の長さが整数の三角形のうち、すべての辺がA以上B以下であるものの数を答えよ、という問題。1G個以上なら打ち切る。

短い方の二辺の長さを決めると長い方の辺がその二辺の和よりも短ければ問題ないので、2乗ループを回せば良い。1G個で打ち切る制約のために、O(N^2)のアルゴリズムでも十分間に合うらしい。微妙。

500

アルファベットからなる部分を取り出して、出現回数の多いものから順番にエンコードすることを考える。同じ回数のものは先に出てきたものを優先する。エンコードは、先頭からN文字取り出すことで行い、すでにエンコード先の文字列が利用済みならばNを随時大きくしていく。Nが自身の長さを超えた場合は、先頭から循環して後ろに付ける。このとき、どれくらい文字数を圧縮できるか、という問題。

実装系。文字列と出現回数と出現位置の三つ組を持っておいて、ソートして、エンコード済み文字列を覚えておいて...、みたいにやればいつかできる。

800

区間[0,1]のうち、三分の一の真ん中を除く。残った領域すべてについて同様に三分の一の真ん中を除く。このような処理を何回繰り返せば、指定された小数値を取り除くことができるか答えよ、という問題。打ち切りは1M回。

実際に三分の一をしていくと精度が明らかに足りないので、指定された値の方を3倍することを考える。これで1以上2以下になれば除去し、そうでなければ延々と繰り返す。BigIntegerを使えば、実装は楽。