JOI 春合宿 2010 day1-1 JOI Poster (難易度 5)

めっちゃフラクタルな問題だ！

• ジャッジページへのリンク
• 問題文へのリンク

類題とか

drken1215.hatenablog.com

問題概要

JOI のロゴは、下図のようになっている (問題文より)。

• レベル のロゴは 1 × 1 のグリッドで "J" のみからなる
• レベル のロゴは、 のグリッドであり、以下のように構成される
  • 左上の については "J"
  • 右上の については "O"
  • 左下の については "I"
  • 右下の については、レベル のグリッド

整数 が与えられる。レベル のロゴの、 行目の 文字を出力せよ。

制約

• 
• 

考えたこと

こういうフラクタル構造をもつ問題は、再帰関数に丸投げしてしまう方法が一つある。つまり、次のような再帰関数を考えるのだ。ただし は 0-indexed で考えることにする。

// レベル n のロゴの k 行目 (0-indexed) を求める
string rec(int n, int k) {
    int mid = (2 の n - 1 乗);
    if (k < mid) {
          return (J が mid 個) + (O が mid 個);
    } else {
          return (I が mid 個) + rec(n - 1, k - mid);
    }
}

あとはこの再帰関数の詳細をちゃんと詰めれば OK。計算量は となる。

コード

#include <bits/stdc++.h>
using namespace std;

string rec(int N, int K) {
    if (N == 0) return "J";
    int mid = 1<<(N-1);
    if (K < mid) return string(mid, 'J') + string(mid, 'O');
    else return string(mid, 'I') + rec(N-1, K-mid);
}

int main() {
    int N, K;
    cin >> N >> K;
    cout << rec(N, K-1) << endl;
}