ぬりえ [yukicoder 883]

https://yukicoder.me/problems/no/883

解説

https://yukicoder.me/submissions/379423

構築問題は色々な方針があるが、今回は最適方針があり、それで構築する方針を取ろう。
頑張れば全部の行と列でK個配置することができる。
つまり、Mを固定したときにMK個配置することが可能である。条件の制約的にこれが最適であることは自明である。
M<Kのときは、M²個が上限なので、上限一杯に置いて、削ればいい。
そうでないときも上限一杯に置いて、削ればいいが、どのようにして置けば最適だろうか。

###.  
.###  
#.##  
##.#  

こんな感じに置けばいい。
Mについては、10³くらいまで試せばいいから、全探索すればいい。
上限がK以上となったら、そのMを採用して、構築を進めていく。

int N, K;
int M;
string ans[1010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;

    rep(m, 1, 1010) {
        if(m < K and N <= m * m) {
            M = m;
            break;
        }
        if(K <= m and N <= K * m) {
            M = m;
            break;
        }
    }

    rep(y, 0, M) rep(x, 0, M) ans[y] += ".";
    rep(y, 0, M) rep(dx, 0, K) ans[y][(y + dx) % M] = '#';

    int cnt = 0;
    rep(y, 0, M) rep(x, 0, M) if(ans[y][x] == '#') {
        if(cnt == N)
            ans[y][x] = '.';
        else
            cnt++;
    }
    
    printf("%d\n", M);
    rep(y, 0, M) printf("%s\n", ans[y].c_str());
}