[CodeQUEEN 2024 予選 (ABC 358)]F - Easiest Maze

[Q] F - Easiest Maze
間に合いませんでした。40分くらい残して初全完がかかっていたのですが残念。
難しいけど、マイルール決めてお絵描きすればいいので、時間をかけて丁寧にやれば絶対できる問題だったなと思う。

考察
1. Noは2パターン
a. 最小マスは直下でNマス。K < Nの場合No
b. 最大を考える。ルートを変えることで消費マスが2増えるので、N + 2n消費できる。(K - N) % 2 == 1の場合No。
それ以外はYesなので、だいたいYes
2. N >= 2なので、1 3 3とかは考えなくていい。ありがたい。

1 3 3 は考えなくていい。
Yes
+++++S+
+o|o|o+
+++++G+

3. Nの偶奇で動きを分けられる。 N=偶数の場合が簡単。
左下右下にうねりながら移動すれば、Gにぴったり到達できる。

4 3 10
Yes
+++++S+
+o.o.o+
+.+-+-+
+o.o.o+
+-+-+.+
+o|o.o+
+-+.+-+
+o|o.o+
+++++G+

4. N=奇数の場合を考える。
a. 最後の4行になるまで左下右下…左下、で左右に蛇行移動する。
b. 最後の4行は下右上右…下、で上下に蛇行移動する。

3 4 11
Yes
+++++++S+
+o.o.o.o+
+.+-+-+-+
+o|o.o.o+
+.+.+-+.+
+o.o|o|o+
+++++++G+

5, 作りたい形を思い描けたので、実装方法を考える。
a. 'o' を移動可能マスと考える。
自分のスタート地点を(1,  M * 2 - 1)としてGまで移動する。
move(&y, &x, dir)を作ると管理しやすい。
b. 通過したマスを + -> . にしてGまでたどり着く
c. 偶数行をみて、 + -> | にする
d. 奇数行をみて、 + -> - にする

3 4 11

+++++++S+    +++++++S+    +++++++S+
+o+o+o+o+    +o.o.o.o+    +o.o.o.o+
+++++++++    +.+++++++    +.+-+-+-+
+o+o+o+o+ -> +o+o.o.o+ -> +o|o.o.o+
+++++++++    +.+.+++.+    +.+.+-+.+
+o+o+o+o+    +o.o+o+o+    +o.o|o|o+
+++++++G+    +++++++G+    +++++++G+

 
実装

int main()
{
  int N, M, K;
  cin >> N >> M >> K;

  // Noのパターン
  if (K < N || (K - N) % 2)
  {
    cout << "No" << endl;
    return 0;
  }

  cout << "Yes" << endl;
  vector<string> maze(2 * N + 1, string(2 * M + 1, '+'));
  rep(i, N) rep(j, M)
  {
    maze[1 + i * 2][1 + j * 2] = 'o';
  }

  auto move = [&](ll &y, ll &x, char d)
  {
    ll dir = "URDL"s.find(d);
    maze[y + dy[dir]][x + dx[dir]] = '.';
    y += dy[dir] * 2;
    x += dx[dir] * 2;
  };

  ll y = 1, x = M * 2 - 1;
  // こぶをいくつ減らすか。
  vector<ll> detour(N / 2, 0);
  ll k = K - N;
  k /= 2; // こぶのかず
  rep(n, N / 2)
  {
    ll sub = min(M - 1LL, k);
    detour[n] = sub;
    k -= sub;
    if (k == 0)
      break;
  }
  if (N % 2 == 0) // 偶数なら左下右下
  {
    rep(det, N / 2)
    {
      rep(i, detour[det])
      {
        move(y, x, 'L');
      }
      move(y, x, 'D');
      rep(i, detour[det])
      {
        move(y, x, 'R');
      }
      move(y, x, 'D');
    }
  }
  else
  {
    rep(det, N / 2)
    {
      rep(i, detour[det])
      {
        move(y, x, 'L');
      }
      move(y, x, 'D');
      if (det == N / 2 - 1) // 奇数なら、最後の2行だけ上下移動
        break;
      rep(i, detour[det])
      {
        move(y, x, 'R');
      }
      move(y, x, 'D');
    }
    while(x < M * 2 - 1)
    {
      if (k > 0)
      {
        move(y, x, 'D');
        move(y, x, 'R');
        move(y, x, 'U');
        --k;
      }
      move(y, x, 'R');
    }
    move(y, x, 'D');
  }
  // + -> |
  rep(i, N){
    rep(j, M - 1){
      if (maze[i * 2 + 1][j * 2 + 2] == '+')
        maze[i * 2 + 1][j * 2 + 2] = '|';
    }
  }
  // + -> -
  rep(i, N - 1){
    rep(j, M){
      if (maze[i * 2 + 2][j * 2 + 1] == '+')
        maze[i * 2 + 2][j * 2 + 1] = '-';
    }
  }

  maze[0][M * 2 - 1] = 'S';
  maze[N * 2][M * 2 - 1] = 'G';
  
  for (auto s : maze)
  {
    cout << s << endl;
  }
}

https://atcoder.jp/contests/abc358/submissions/54623737