170.1

250

漸化式が与えられるので、N番目の項を求めよという問題。ただし10で割った余りを答える。計算機では負の数の割り算の余りは負になるが、正になるように補正する。

普通に計算すればおしまいだけれど、最初の方の項は規則に従わなかったりするので、そこを例外処理する必要がある。

550

N都市を連結する際に、各都市は上下左右の4方向に道を伸ばし、どこかの都市または道と連結したら、その相手の都市が連結しているすべての都市と連結したとみなす。各都市は一定時間に4方向それぞれに一定距離しか道を伸ばせない。すべての都市が連結するまでに必要な時間を答えよ、という問題。

取り敢えず2都市間の道が完成するまでの時間を求めて、それを利用して別の都市を経由した場合に時間が短縮されるものがあれば短縮していく。これを収束するまでやる。Warshall-Floydを使うのが一番実装が楽かなぁ、という感じ。

1000

f(y)=g(x)なる式と、y及びxの範囲が与えられるので、等式を満たすxとyの組のうち格子点上にあるものはいくつあるか答えよという問題。

xとyはいずれも1M程度の範囲に収まるので、単純に実装すると2M回だけ式を計算すれば終わる。BigIntegerを使って実装したところTLEしたので、f(y)=g(x)が完全に式として一致する場合を例外処理して、それ以外の場合に、増加分の多い方を1増やした時に他方がどれくらい増えるのかというのを大体覚えておいて加速してやらないとダメそう。

でも、y^9=x^9+1みたいな式を地道に計算すると結局同じ理由でTLEしそう。本質的に何かが間違っているんだろうなぁ...。