けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

JOI JOI春合宿 AtCoder 再帰的構造に着目する 0と1と2の問題 二次元グリッド フラクタル構造 K番目を求める JOI難易度5

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

類題とか

drken1215.hatenablog.com

問題概要

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

f:id:drken1215:20201219162658p:plain

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

整数 N, K が与えられる。レベル N のロゴの、 K 行目の 2^{N} 文字を出力せよ。

制約

  • 0 \le N \le 20
  • 1 \le K \le 2^{N}

考えたこと

こういうフラクタル構造をもつ問題は、再帰関数に丸投げしてしまう方法が一つある。つまり、次のような再帰関数を考えるのだ。ただし k は 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。計算量は O(2^{N}) となる。

コード

#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;
}