解説は三進法でやってたけど、二進法でもできた

問題概要

次をすべて満たすようなマス目を構成せよ。

マス目の各マスは白か黒で塗られている
マス目の縦横の長さをそれぞれ N,M としたとき、N,M は 1 以上 100 以下である

一番左上のマスから一番右下のマスまで、白く塗られたマスだけを通って右または下に 1 マス進むことを繰り返して辿り着く方法はちょうど K 通りある

制約

$0 \le K \le 10^{18}$

考えたこと

まずは、 $a$ と $b$ が作れたら、 $a + b$ も作れることは比較的すぐにわかる。

そのことを利用できる方法としてパッと思いつくのが

二進法で考える
三進法で考える
二項係数の和として表す

あたりのところ。二進法で作るのは実は割と難しくて、縦横 200 以内なら簡単に作れるけど、100 以内に収めるのが難しかった。

そして整数の二進法展開にもいくつかやり方があることを想起しておくと、いいんだろうなと。。。

例えば 74 を二進法展開する方法として

大きいやつから Greedy

74 を超えない最大の二冪は 64 なので

74 = 64 + 10

次に 10 を超えない最大の二冪は 8 なので

10 = 8 + 2

よってまとめて

74 = 64 + 8 + 2

という感じ。

二で割っていく

74 = 37 × 2
37 = 18 × 2 + 1
18 = 9 × 2
9 = 4 × 2 + 1
4 = 2 × 2
2 = 1 × 2

これらのやり方を念頭に置くと構成の選択肢が広がる気がする。僕は前者の方法ではどうしても縦横 100 以内に収められなかったけど (三進法ならこの方向性でもいけるみたい)、後者の方法を工夫すると 100 以内に収められた。

#include <iostream>
using namespace std;

const int MAX = 100;
int val[MAX + 10][MAX + 10];

int main () {
    long long K; cin >> K;
    int curdir = 0;
    int x = 0, y = 0;
    
    while (K > 0) {
        val[x][y] = K;
        if (K % 2 == 0) {
            val[x+1][y] = K/2;
            val[x][y+1] = K/2;
            val[x+1][y+1] = K/2;
            ++x, ++y;
        }
        else {
            if (curdir == 0) {
                val[x+1][y] = K/2+1;
                val[x][y+1] = K/2;
                val[x+1][y+1] = K/2;
                for (int i = x+2; i < MAX; ++i) val[i][y] = 1;
                val[x+1][y+2] = K/2;
                ++x, y += 2;
            }
            else {
                val[x][y+1] = K/2+1;
                val[x+1][y] = K/2;
                val[x+1][y+1] = K/2;
                for (int i = y+2; i < MAX; ++i) val[x][i] = 1;
                val[x+2][y+1] = K/2;
                x += 2, ++y;
            }
            curdir = 1 - curdir;
        }
        K /= 2;
    }
    val[MAX-1][MAX-1] = 1;
    for (int i = 0; i < MAX; ++i) {
        val[MAX-1][i] = 1;
        val[i][MAX-1] = 1;
    }

    cout << MAX << " " << MAX << endl;
    for (int i = 0; i < MAX; ++i) {
        for (int j = 0; j < MAX; ++j) {
            cout << (val[MAX-1-i][MAX-1-j] ? '.' : '#');
        }
        cout << endl;
    }
}