第一回日本最強プログラマー学生選手権決勝 A - Equal Weight
問題概要
個のシャリと
個のネタがある。それぞれには重さ(それぞれ
)が割り振られており、シャリ1つとネタ1つで握りが1つ完成する。重さが同じ2つの握りを構成する方法があるなら示し、無いなら-1を出力する。
解法
最初に十分な要素数を確保したpair型の配列を用意しておき、(-1,-1)等配列のindexとして存在しえない数値で埋めておく。
次に、2重ループを回し、それぞれのシャリとネタの和のindexの要素を見て、初期値で無ければ既に今見ているシャリとネタの和と同じ重さの握りが存在することになるから適切に出力して終了。初期値だったら和のindexにシャリとネタのindexを格納する。最後まで見つからなければ-1で終了。
一見に見えるが、実際は
回の計算で終了する。
より、あり得るシャリとネタの和の範囲
は
(なので最初に述べた十分な配列のサイズというのは
くらいが望ましい)。それぞれの和の候補について、上記のアルゴリズムでは高々1回しかアクセスしないため、最悪ケースでも
回しか見ないことになる。
よって、上記を実装して、AC。
