kichi2004's BLOG

競技プログラミングの参加記とか日常とか。(※Google Analyticsを使用しています)

競プロ

「AtCoder Grand Contest 033」に参加しました

投稿日:2019年5月5日 更新日:

コンテストページはこちら

結果

2完 [A(300), B(600)] 139:48 ペナルティ: 7 (139:48 -> 174:48)
・順位: 817位 (Rated)
・パフォーマンス: 1482
・Rating変化: 1246 -> 1272 (+26) [Rating最高値]

各問題の解法

A問題 (300点)

提出詳細
計算量 O(HW)
初期の黒いマスから隣接する4マスにBFSの要領で、距離を埋めていく。
2手以降前の黒マスは既に埋められているため、見る必要がない(対象のリストから消す)

int H, W;
bool InMap(const int h, const int w)
{
  return h >= 0 && w >= 0 && h < H && w < W;
}
int main()
{
  int dx[4] = { -1, 0, 0, 1 }, dy[4] = { 0, -1, 1, 0 };
  const int INF = 1000000010;
  cin >> H >> W;
  vector<pair<int, int>> black;
  black.reserve(H * W);
  //INF = 初期の黒からの最短距離がまだ不明なマス
  vector<vector<int>> value(H, vector<int>(W, INF));
  for (int i = 0; i < H; i++)
  {
    string s;
    cin >> s;
    for (int j = 0; j < W; j++)
    {
      if (s[j] != '#')continue;
      black.emplace_back(i, j);
      //初期値で黒マスのところは0にする
      value[i][j] = 0;
    }
  }
  int black_count = black.size(), cur = 1;
  //すべてが黒のマスになる(距離が計算される)まで繰り返す
  while(black_count < H * W) {
    vector<pair<int, int>> next_black;
    for(auto& b : black) {
      int nowH = b.first, nowW = b.second;
      for(int i = 0; i < 4; i++) {
        //みるマス
        int nextH = nowH + dy[i], nextW = nowW + dx[i];
        //範囲外なら無視
        if (!InMap(nextH, nextW)) continue;
        //未計算のマスだったら、黒のマスのカウントを増やす
        //次の計算に使うため、nextにマスを追加する
        if(value[nextH][nextW] == INF) {
          black_count++;
          next_black.emplace_back(nextH, nextW);;
          value[nextH][nextW] = cur;
        }
      }
    }
    //今回計算に使った黒マスは、次以降は必要ないので、blackをnextにする
    black.swap(next_black);
    //手数を増やす
    cur++;
  }
  cout << cur - 1 << endl;
}

B問題 (600点)

提出詳細
計算量 O(N)
上、下、左、右、それぞれ独立して計算を行う、
高橋くんの手番では、それぞれのカウントを1増やす。
青木くんの手番では、高橋くんの逆(上なら下、右なら左)のカウントを1減らす。ただし、その操作を行うことによって盤面から落ちる可能性があるときは、操作を行わない。
高橋くんの操作の直後、上下左右でいずれかが盤面から落とせる場合はNO、そうでない場合はYESを出力。

int H, W, N, sr, sc;
string S, T;
cin >> H >> W >> N >> sr >> sc >> S >> T;
bool flag = true;
int l = 0, r = 0, u = 0, d = 0,
  l_ok = sc, r_ok = W - sc + 1,
  u_ok = sr, d_ok = H - sr + 1;
for (int i = 0; i < N; i++) {
  //各方向へのカウントを増やす
  if (S[i] == 'R') r++;
  else if (S[i] == 'L') l++;
  else if (S[i] == 'U') u++;
  else if (S[i] == 'D') d++;
  if (r >= r_ok || l >= l_ok || u >= u_ok || d >= d_ok) {
    flag = false;
    break;
  }
  //逆方向に引き戻す(ただし盤面から出ない範囲で)
  if (T[i] == 'R' && (l > 0 || abs(l + 1) < r_ok)) l--;
  else if (T[i] == 'L' && (r > 0 || abs(r) + 1 < l_ok)) r--;
  else if (T[i] == 'U' && (d > 0 || abs(d) + 1 < u_ok)) d--;
  else if (T[i] == 'D' && (u > 0 || abs(u) + 1 < d_ok)) u--;
}
cout << (flag ? "YES" : "NO") << endl;

感想

AGCでは過去最高のパフォーマンス、過去問を含めて初めて600点に正解しました。
最初の1回(0完、パフォ29で24→44)を除いて、初めてAGCでレートを上げました。
600は嘘解法が通るみたいで、想定しているより通している人が多く、結果として(想定より)パフォが500程度低かったのかなーと思います。まあ仕方ないですね。
おそらく私の解き方は嘘解法ではないので、実力的にはperf2000程度でしょうか…?
次回のAGCでも冷やさないようにがんばります。

-競プロ

執筆者:


comment

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA


関連記事

no image

「Tenka1 Programmer Beginner Contest 2019」に参加しました

コンテストページはこちら 結果 3完 [A(100), B(200), C(300)] 11:53 ペナルティ: 0 ・順位: 8位 ・パフォーマンス: 1600 (Inner: 2556) ・Rat …

no image

JOI 2020 / 2021 二次予選 参加記

はじめに おひさしぶりです.kichi2004 です.競プロ関係の記事は今年の 3 月以来 9 か月ぶりなので,まずはそれについて簡単にお話します.今年の 2 月に,JOI に二次予選落ちしたことや …

no image

「AtCoder Beginner Contest 145」A~E問題解説 / 参加記

コンテストページはこちら 結果 5完 [A(100), B(200), C(300), D(400), E(500)] 53:22 ペナルティ: 1 (-> 58:22) ・順位: 321位 (Rat …

no image

「AtCoder Grand Contest 034」に参加しました

コンテストページはこちら 結果 2完 [A(400), B(600)] 49:18 ペナルティ: 3 (-> 64:18) ・順位: 736位 (Rated) ・パフォーマンス: 1552 ・Rati …

no image

「M-SOLUTIONS プロコンオープン」に参加しました

コンテストページはこちら 結果 3完 [A(100), B(200), D(500)] 68:17 ペナルティ: 0 ・順位: 725位 (Rated) ・パフォーマンス: 1498 ・Rating変 …