ferinの競プロ帳

競プロについてのメモ

AGC021 C - Tiling

AtCoder 競技プログラミング

問題ページ

考えたこと

  • HとWが偶数だと考えやすそう
  • Wが奇数だったら1列分どう頑張っても1種類目のタイルを置けない
  • なので1列分2種類目のタイルを敷き詰めてしまってよさそう
  • Hが奇数のケースも同様に1行分1種類目のタイルを敷き詰めてよさそう
  • これでHとWが両方とも偶数に置き換えられそう
  • 2×2マスの矩形にはどちらの種類のタイルも2枚敷ける
  • floor(a/2)*2 + floor(b/2)*2 枚のタイルはきれいに敷き詰められそう
  • 盤面の大きさとタイルの大きさを比較して置けないならNO、置けるならタイルを置く
  • 残っているタイルを残りのマスに置けるかどうか判定したい
  • 1種類目と2種類目どちらか1枚しかなければ2×2マスの矩形があるかどうかで判定できる
  • 両方1枚ずつある場合、普通に考えると2×3マスの矩形があるかどうかで判定できそう
  • HとWが両方奇数の場合、端のマスに敷き詰めたとしても1マス絶対に残る
  • この1マス + 2×2マスの矩形でタイル両方を置ける
  • この辺の判定を頑張って書くと通った

バグらせてつらい

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long int;
// #define int ll
using PII = pair<int, int>;
 
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
 
template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const int MOD = 1000000007;

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int h, w, a, b;
  cin >> h >> w >> a >> b;

  int empty = h*w;
  vector<string> ans(h, string(w, '.'));
  if(w%2) {
    int tmp = min(b, h/2);
    REP(i, tmp) {
      ans[2*i+(h%2)][w-1] = '^';
      ans[2*i+1+(h%2)][w-1] = 'v';
      empty -= 2;
    }
    b -= tmp;
    w--;
  }
  if(h%2) {
    int tmp = min(a, w/2);
    for(int i=0; i<tmp; ++i) {
      ans[h-1][2*i] = '<';
      ans[h-1][2*i+1] = '>';
      empty -= 2;
    }
    a -= tmp;
    h--;
  } 

  if(h*w < 2*(a+b)) {
    cout << "NO" << endl;
    return 0;
  }

  // REP(i, ans.size()) cout << ans[i] << endl;

  // h * w マスにタイルを敷き詰める
  int y = h-2, x = 0;
  REP(i, a/2) {
    ans[y][x] = '<';
    ans[y][x+1] = '>';
    ans[y+1][x] = '<';
    ans[y+1][x+1] = '>';
    empty -= 4;

    y -= 2;
    if(y < 0) {
      y = h-2;
      x += 2;
    }
  }
  REP(i, b/2) {
    ans[y][x] = '^';
    ans[y][x+1] = '^';
    ans[y+1][x] = 'v';
    ans[y+1][x+1] = 'v';
    empty -= 4;

    y -= 2;
    if(y < 0) {
      y = h-2;
      x += 2;
    }
  }
  a = a%2;
  b = b%2;

  // REP(i, ans.size()) cout << ans[i] << endl;

  if(a%2 && b%2 && empty >= 5) {
    if(empty == 5) {
      ans[0][w-2] = '^';
      ans[1][w-2] = 'v';
      ans[0][w-1] = '<';
      ans[0][w] = '>';
      a--, b--;
    } else {
      ans[y][x] = '^';
      ans[y+1][x] = 'v';

      y -= 2;
      if(y < 0) {
        y = h-2;
        x += 2;
      }

      ans[y][x] = '<';
      ans[y][x+1] = '>';
      a--, b--;
    }
  }
  else if(a%2 && empty >= 4) {
    ans[0][w-2] = '<';
    ans[0][w-1] = '>';
    a--;
  }
  else if(b%2 && empty >= 4) {
    ans[0][w-2] = '^';
    ans[1][w-2] = 'v';
    b--;
  }

  if(a || b) {
    cout << "NO" << endl;
    return 0;
  }

  cout << "YES" << endl;
  REP(i, ans.size()) cout << ans[i] << endl;

  return 0;
}