2012年5月17日木曜日

GCJ2012 Round 1C Problem A. 解き方

Google Code Jam 2012 Round 1C
Problem A. Diamond Inheritance 解き方

実践したソースは このあたり再帰版) にあります。
問題紹介は こちら です。

以下ネタバレ

再帰で親クラスを辿っていくのが一番簡単な気がします(考えやすいという意味で)。
  1. まず各クラスを継承しているクラスがないか調べます。
  2. 継承しているクラスがない場合(サブクラスの末端の場合)、各親クラスを順に辿ってルートクラスを見つけます(ここで再帰を使う)。
  3. 複数の異なる経路で同じルートクラスに辿り着いたら Diamond Inheritance があります。

再帰を使わない場合はループで同じように調べることができます。
処理を高速化するため、1つでも Diamond Inheritance を見つけたら再帰を大域脱出して "Yes" を出力してしまうという手もあります。お行儀はよくないですが…
※Pythonの場合はLargeで RuntimeError: maximum recursion depth exceeded になる恐れがあります。
  これは sys.setrecursionlimit(1100) をすれば回避できます。(N ≤ 1,000 なので 1000 以上で少し余裕を見て)

ルートクラスまで辿らなくても、途中で同じクラスを見つけたらその時点で Diamond Inheritance になっているので “Yes” と返すことができます。スーパークラスを辿っていく途中で見つけたクラスを重複チェックしながらリストに入れていき、そのリストのクラスを順次チェックすることで再帰せず高速に祖先リストを作ることができます。

この方法は、あらかじめ各クラスのサブクラスをリストしておき、ルートクラスからその派生クラス(子孫クラス)を見ていく方が考えやすいかもしれません。

各クラスのルートクラスや派生クラスをキャッシュすることで高速化できますが、今でも十分速いのでそこまでは必要ないかな、、という感じです。

0 件のコメント:

コメントを投稿