読者です 読者をやめる 読者になる 読者になる

naoya_t@hatenablog

いわゆるチラシノウラであります

SRM593

駄目ぽよ

Easy (250): HexagonalBoard

  • 高々3色
  • 最大クリークサイズか、
  • サイズ2のクリークを繋いでぐるっと回ってきたら3色要る場合があるよね
  • (要するに二部グラフにできるかどうか)
  • 126.39点→WA

提出コード:

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>

using namespace std;
#define sz(a)  int((a).size())
#define rep(var,n)  for(int var=0;var<(n);++var)

class UnionFind {
  vector<int> data;
 public:
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) { return root(x) == root(y); }
  int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
  int size(int x) { return -data[root(x)]; }
};

class HexagonalBoard {
 public:
  int minColors(vector<string> board) {
    int N=sz(board), ans=0;

    rep(i,N)rep(j,N){
      if (board[i][j]=='X') ans=max(ans,1);
    }

    UnionFind uf(N*N);
    rep(i,N-1)rep(j,N-1){
      bool a = (board[i][j]=='X'),
          b = (board[i+1][j]=='X'),
          c = (board[i][j+1]=='X'),
          d = (board[i+1][j+1]=='X');
      if (a&&b) uf.unionSet(i*N+j, (i+1)*N+j);
      if (a&&c) uf.unionSet(i*N+j, i*N+(j+1));
      if (b&&c) uf.unionSet((i+1)*N+j, i*N+(j+1));
      if (b&&d) uf.unionSet((i+1)*N+j, (i+1)*N+(j+1));
      if (c&&d) uf.unionSet(i*N+(j+1), (i+1)*N+(j+1));
      if ((a && b) || (a && c) || (b && c) || (b && d) || (c && d)) ans=max(ans,2);
      if ((a && b && c) || (b && c && d)) ans=max(ans,3);
    }

    set<int> rs;
    if (ans==2) {
      rep(i,N)rep(j,N){
        if(board[i][j]=='X') {
          int r = uf.root(i*N+j);
          if (rs.find(r) == rs.end()) {
            vector<vector<int> > mk(N,vector<int>(N,-1));
            queue<pair<int,int> > q; q.push(make_pair(r,0));
            while (!q.empty()) {
              int r=q.front().first, c=q.front().second; q.pop();
              int y=r/N, x=r%N;
              if (board[x][y]!='X') continue;
              if (mk[x][y]==c) continue;
              if (mk[x][y]!=-1 && mk[x][y]!=c) { ans=3; break; }
              mk[x][y] = c;
              if (x<N-1 && board[x+1][y]=='X') q.push(make_pair(r+1,1-c));
              if (x>0 && board[x-1][y]=='X') q.push(make_pair(r-1,1-c));
              if (y<N-1 && board[x][y+1]=='X') q.push(make_pair(r+N,1-c));
              if (y>0 && board[x][y-1]=='X') q.push(make_pair(r-N,1-c));
              if (x<N-1 && y>0 && board[x+1][y-1]=='X') q.push(make_pair(r+1-N,1-c));
              if (y<N-1 && x>0 && board[x-1][y+1]=='X') q.push(make_pair(r-1+N,1-c));
            }
          }
          rs.insert(r);
          if (ans == 3) break;
        }
        if (ans == 3) break;
      }
    }

    return ans;
  }
};

Medium (450): MayTheBestPetWin

  • A合計, B合計を出す
  • 一方のチームのA合計B合計からもう一方のチームのA合計B合計は出せるので、そこからmaxdiffは求められる
    • (全体のA合計) - (チーム1のA合計) = (チーム2のA合計)
    • (全体のB合計) - (チーム1のB合計) = (チーム2のB合計)
    • maxdiff = max(チーム2のB合計 - チーム1のA合計, チーム1のB合計 - チーム2のA合計)
    • = max((全体のB合計) - (チーム1のB合計) - チーム1のA合計, (全体のA合計) - (チーム1のA合計) - チーム2のA合計)
    • = max(全体のB合計 - チーム1のAB合計, 全体のA合計 - チーム1のAB合計)
    • これが最小になるのはいつ? チーム1のAB合計が、全体のA合計と全体のB合計の中間値に最も近い時。
  • チーム1のAB合計としてありうる値は高々50x10000=50万種類。DPでできるっしょ
  • 298.79点→WA
  • 最後max()してるつもりでmin()と書いてた(コーディング前のメモにもはっきりmaxって書いてる!)
  • そういう信じられないミスを避けるためにはassertとテストケース増設あるのみ
  • 編集距離で言うと2

提出コード:

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>

using namespace std;
#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);++var)
#define all(c)  (c).begin(),(c).end()
#define found(s,e)  ((s).find(e)!=(s).end())

class MayTheBestPetWin {
 public:
  int calc(vector <int> A, vector <int> B) {
    int N = sz(A);
    int asum = 0, bsum = 0, md = 0, tot = 0;
    vector<int> c(N);
    rep(i,N) {
      asum += A[i]; bsum += B[i];
      c[i] = A[i] + B[i];
      tot += c[i];
    }
    md = (asum + bsum)/2;

    vector<vector<bool> > dp(2,vector<bool>(tot+1, false));
    dp[0][0] = true;
    int maxt=0;
    rep(i,N){
      int ci = c[i];
      int i0=i%2, i1=1-i0;
      rep(j,tot+1) dp[i1][j] = false;
      rep(j,maxt+1) {
        if (dp[i0][j]) {
          dp[i1][j] = dp[i1][j+ci] = true;
        }
      }
      maxt += ci;
    }
    int best=999999999, bestarg=-1;
    rep(j,maxt+1) {
      if(dp[N%2][j]) {
        int diff = abs(j-md);
        if (diff < best) {
          best = diff;
          bestarg = j;
        }
      }
    }
    return min(abs(asum-bestarg), abs(bsum-bestarg)); // ←minをmaxにすれば通る
  }
};

Hard (1000): WolfDelaymasterHard

  • あと15分
  • 開いた
  • 愚直なコードを書きながら、これってDPで行けるような気がしてきて
  • 時間切れ

Challenge phase

  • 250を落としまくってる人がいた
  • 250も450も落とされなかった
  • 部屋3位だった

System Test

  • 101位まで上がったと思ったら2問ともWAで393位に転落
  • 1396 → 1361

総評

  • レーティングも落ちるところまで落ちた感があるので、次はのびのびやろう
  • とにかくassertとかテストケースとか追加しよう。