JOI Poster(JOI ポスター) - joi2010-day1 解説

筆者: qnighy

再帰的に構成されたJOIロゴの特定行を出力する問題である。

O(4^N)解法

最もシンプルなのは、2^N × 2^N の配列を用意し、再帰的に代入してから、K行目を出力する方法である。

しかしこの方法だと、O(4^N)のメモリと時間を要するので、50点しか取れない。

O(2^N)解法

そこで、K行目だけに限定して処理を行う方法を考える。

Kと2^(N-1)との大小関係によって、出力する行の前半が決定でき、続く後半は再帰的に決定できることを利用すれば、あとは簡単に実装できるだろう。

また、ビット演算を上手に利用すれば、再帰除去も行える。

どちらにせよ、境界条件やK=2^Nの場合には注意しないといけないだろう。