CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第89回「一筆書きの交点」

CodeIQというサイトで問題に挑戦した記録です。

問題を要約すると以下の通り、

• 円周上に等間隔にn個の点がある。
• 任意の点から一筆書きで最初の点へ戻るルートを考えた時、交差する回数の総計を解答する。
• nの最大値は9

方針

今回は規則性を見つける事ができず、全探索を行うしかなかった。
当初、時間制限に間に合わないのを確認しながらRubyで提出、TLEだったので、
C++でほぼ同じコードを書き直し再提出。正解した。
(順列の生成に、Rubyでは Array#permutation を使用。C++では自前で実装。
ちなみにn=9の場合で、RubyではTLE、C++では表示0.0秒。事前の「実行くん」では0.02秒)

なお、組み合わせにより式を導いた@angel_p_57さんの解説はこちら、

t.co

素晴らしい。

実装

C++ (gcc 4.9.3)

では、


Sponsored Link