365.1

300

原点を中心とする円の半径が与えられるので、円周上の点のうち格子点のものの数を答えよという問題。ただし、半径の2乗の約数のうち、4で割った余りが1のものの数から、4で割った余りが3のものの数を引いた値を4倍すると求めることができる。

注釈に従わずに計算すると、32bitでは足りないらしいのでTLEするはず。基本的には約数の数を計算するわけだけれど、偶数のものは考慮しなくていいので、奇数にしてから計算。

素因数分解した結果があれば、約数の総数は求まるけれど、mod4で計算して1と3というグループに分けないといけないので、分けた状態で同様に計算する。3*3=1に注意する必要があるので、4で割った余りが3の素数については、やや煩雑。(実際には計算していくと何も影響がないという結論になるらしい。)

500

数列が与えられる。等差数列のうち、その上限値と下限値の間にある要素の中で、与えられた数列に含まれるものの割合のうち、最大のものを答えよという問題。ただし、与えられた数列の要素のうち少なくとも三つがその等差数列上になければならない。

少なくとも三つの要素が入るかどうか、という条件は、少なくとも三つの要素が与えられた数列にあるかどうか、と等しい。要素が三つあれば、1差の等差数列が存在することから、少なくとも答えが存在することは分かる。

与えられた数列から三つの要素を選び、それらを乗せた等差数列について、全体として包含する割合の最大となるものを答えれば良い。等差数列の作り方は、三つの要素のそれぞれの間隔の最大公約数。全通り試せば十分というのは、もしより細かい粒度にある要素を取るようにする方がいいのなら、最初に選ぶ三つの要素にそれが含まれるようなもので同じ結果になるものがあることから。

1000

有効グラフの辺が与えられるので、DAGを形成した時に親よりも子が大きい一意のIDを持つようにIDを振るとき、元の点集合に対して辞書順で一番最初に可能となるIDの割り当てを答えよという問題。

制約下で一番小さいIDを最初の点から順に割り振っていけば良い、という以前あった問題の類題じゃないかなぁと。制約が大分煩雑なので、実装しようとすると大変。うまいこと実装すると実はさっくり書ける模様。詳細は追えず...。