Problem A. Diamond Inheritance 解き方
実践したソースは このあたり(再帰版) にあります。
問題紹介は こちら です。
以下ネタバレ
再帰で親クラスを辿っていくのが一番簡単な気がします(考えやすいという意味で)。
再帰を使わない場合はループで同じように調べることができます。
処理を高速化するため、1つでも Diamond Inheritance を見つけたら再帰を大域脱出して "Yes" を出力してしまうという手もあります。お行儀はよくないですが…
※Pythonの場合はLargeで RuntimeError: maximum recursion depth exceeded になる恐れがあります。
これは sys.setrecursionlimit(1100) をすれば回避できます。(N ≤ 1,000 なので 1000 以上で少し余裕を見て)
- まず各クラスを継承しているクラスがないか調べます。
- 継承しているクラスがない場合(サブクラスの末端の場合)、各親クラスを順に辿ってルートクラスを見つけます(ここで再帰を使う)。
- 複数の異なる経路で同じルートクラスに辿り着いたら Diamond Inheritance があります。
再帰を使わない場合はループで同じように調べることができます。
処理を高速化するため、1つでも Diamond Inheritance を見つけたら再帰を大域脱出して "Yes" を出力してしまうという手もあります。お行儀はよくないですが…
※Pythonの場合はLargeで RuntimeError: maximum recursion depth exceeded になる恐れがあります。
これは sys.setrecursionlimit(1100) をすれば回避できます。(N ≤ 1,000 なので 1000 以上で少し余裕を見て)
ルートクラスまで辿らなくても、途中で同じクラスを見つけたらその時点で Diamond Inheritance になっているので “Yes” と返すことができます。スーパークラスを辿っていく途中で見つけたクラスを重複チェックしながらリストに入れていき、そのリストのクラスを順次チェックすることで再帰せず高速に祖先リストを作ることができます。
この方法は、あらかじめ各クラスのサブクラスをリストしておき、ルートクラスからその派生クラス(子孫クラス)を見ていく方が考えやすいかもしれません。
各クラスのルートクラスや派生クラスをキャッシュすることで高速化できますが、今でも十分速いのでそこまでは必要ないかな、、という感じです。
0 件のコメント:
コメントを投稿