Google Code Jam 2008 Round1A "Numbers" (問題演習)

問題は「(3+√5)^nの100の位〜1の位を答えよ」、というものです。

この問題の解答例・解説は「プログラミングコンテストチャレンジブック」に載っていますが、私の解答はそれと若干違うものです。

私の解答は次のとおりです。

ACM-ICPC 2011 日本国内予選(演習)

参加資格はないのですが、ACM-ICPC2011日本国内予選の問題を時間を測って解いてみました。解けたのは3問です。

Aは似たような問題を昔自作して解いたことがあるので、あまり苦労しませんでした。その当時(数年前)は1個1個判定していましたが、今回はエラトステネスの篩で素数表を作りました。

BはUTPC2011(東京大学プログラミングコンテスト)で少々似たような問題を見たことがあるなと思いながら、スタックを作って解きました。Cでスタックを組むのが面倒だったので、スタック風の処理、という方が正確かも知れませんが。

Cはバックトラックで実装しました。日本国内予選ではセルを数える問題が結構多いような気がしますが、単なる偶然でしょうか？

問題はこちらです。