問題リンク Fermat's Last Theorem 概要 整数zが与えられる。z^3を超えないx^3+y^3を見つけ、z^3-(x^3+y^3)を計算せよ。xとyは0より大きい整数とする。 1 解法 iを1, jをzとします。 i^3+j^3がzを超えたならjを1つ減らし、そうでないならばiを1つ増やします…

問題リンク A Long Ride on a Railway 概要 N個の駅とM個の路線がある。路線には長さがある。路線の最長パスの長さとその経路を答えよ。 経路は辞書順比較で一番小さいものを答えよ。 1 1 解法 グラフにおける最長パスを求めるのは普通は困難ですが、グラフ…

問題リンク Spiral Footrace 概要 座標(0, 0)に北を向いて立っている。N個の点が与えられる。N個の点を順番に辿り、最後の点についた時の総距離を答えよ。 点を辿る順番は、向いている方向とその点のある方向との角度が一番小さいものとする。 1 0 解法 幾何…

問題リンク Factorization of Quadratic Formula 概要 2次方程式の整数係数a, b, cが与えられる。これを因数分解し、(px+q)(rx+s)としたときのp, q, r, sを答えよ。 但し、p, q, r, sは全て整数であること。また、0 解法 まず、2次方程式の解の公式の判別式D…

問題リンク Unable Count 概要 3つの整数N, a, bが与えられる。1〜Nの整数の中で、a*i+b*jの形で表現できるもの(i, jは非負整数)の個数を答えよ。 N, a, b 解法 DPです。整数xはx-a, x-bのいずれかが表現できれば表現できることになります。 ソース

問題リンク Where's Your Robot? 概要 H*Wの大きさのボードがある。ロボットが北を向いて(1, 1)にいる。 コマンドを与えられるので、それを実行した後ロボットのいる座標を答えよ。 コマンド実行中、ボードを超えてしまうようなときは、ロボットはそのボード…

問題リンク Planning Rolling Blackouts 解法 メモ化再帰で解きました。 ある分割で[i, j]*[k, l]の区画が作られたとします(左上の座標が(i, j)、右下の座標を(k, l)とする長方形と思ってください)。この区画における最大分割数と最大予備電力は、この区画を…

問題リンク And Then. How Many Are There? 解法 円盤は最大で24枚あります。なので円盤全体の状態は2^24で表すことができます。円盤N枚の初期状態は(2^N)-1です。 状態Xから円盤i, jの2枚を選んで取り除けるかを探索していきます。 iとjが同じ円盤だったり…

問題リンク Identically Colored Panels Connection 解法 色を変えるやり方を全て試します。6色の変更を5回行うので6^5通りになります。ただ、最後の1色はターゲットの色にしないと意味がないので、実質6^4になります。 あとは深さ優先探索で連結成分のもろ…

問題リンク The Balance of the World 解法 再帰で解きました。 左から文章を見ていって閉じ括弧が見つかればfalseです。 開き括弧ならば、対応する閉じ括弧との間の文章はバランスしているはずなので再帰します。 間の文章がバランスしてなければfalse。間…

問題リンク Chebyshev's Theorem 解法 123456*2の大きさのエラトステネスの篩を作ります。それと累積和の配列を作れば勝ちです。 ソース

問題リンク Gap 概要 Gapというカードゲームをやる。これをクリアするまでにかかる最短の手数を答えよ。 Gapは4*8のボードを使い、1〜4の柄それぞれについて1〜7の数が1枚ずつある。ボードには常に4か所の空欄がある。 1手につき、空欄にカードを移動するこ…