naoya_t@hatenablog

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

Google Code Jam 2022 Round 2

Google Code Jam Programming Contest

codingcompetitions.withgoogle.com
2022/5/14 23:00-25:30JST

779位（終了時781位）で初のRound 3進出＆TシャツGET！！

A. Spiraling Into Control (3, 4, 13pts)

愚直に（超めんどくさいけど）シミュレーションするよ
→AC(3+4) 0:47:15

(..略..)

int dx[4] = { 1, 0, -1, 0 }, dy[4] = { 0, 1, 0, -1 };

void solve(int N, int K) {
    vvi z(N, vi(N));
    vvi dp(N, vi(N, INT_MAX));
    vvii from(N, vii(N));
    int H = N/2;

    int numero = 0;
    for (int s=H; s>=1; --s) {
        for (int x=H-s, y=H-s; x<=H+s-1; ++x) z[x][y] = ++numero;
        for (int y=H-s, x=H+s; y<=H+s-1; ++y) z[x][y] = ++numero;
        for (int x=H+s, y=H+s; x>=H-s+1; --x) z[x][y] = ++numero;
        for (int y=H+s, x=H-s; y>=H-s+1; --y) z[x][y] = ++numero;
    }
    z[H][H] = N*N;

    dp[H][H] = 0;
    auto spread = [&](int x, int y) {
        int centre = dp[x][y];
        rep(d,4) {
            int xx = x + dx[d], yy = y + dy[d];
            if (IN(xx, 0, N-1) && IN(yy, 0, N-1)) {
                if (z[xx][yy] > z[x][y]) continue;
                if (dp[xx][yy] > centre+1) {
                    dp[xx][yy] = centre + 1;
                    from[xx][yy] = ii(x, y);
                }
            }
        }
    };

    spread(H, H);

    for (int s=1; s<=H; ++s) {
        for (int y=H-s+1; y<=H+s; ++y) spread(H-s, y);
        for (int x=H-s+1; x<=H+s; ++x) spread(x, H+s);
        for (int y=H+s-1; y>=H-s; --y) spread(H+s, y);
        for (int x=H+s-1; x>=H-s; --x) spread(x, H-s);
    }
    if (K < dp[0][0] || K%2 != dp[0][0]%2) {
        printf("IMPOSSIBLE\n");
        return;
    }

    int rest = K;
    ii fnd(H, H);
    for (int s=H; s>=1; --s) {
        for (int x=H-s, y=H-s; x<=H+s-1; ++x) {
            if (dp[x][y] == rest) {
                fnd = ii(x, y); goto out;
            }
            --rest;
        }
        for (int y=H-s, x=H+s; y<=H+s-1; ++y) {
            if (dp[x][y] == rest) {
                fnd = ii(x, y); goto out;
            }
            --rest;
        }
        for (int x=H+s, y=H+s; x>=H-s+1; --x) {
            if (dp[x][y] == rest) {
                fnd = ii(x, y); goto out;
            }
            --rest;
        }
        for (int y=H+s, x=H-s; y>=H-s+1; --y) {
            if (dp[x][y] == rest) {
                fnd = ii(x, y); goto out;
            }
            --rest;
        }
    }
 out:
    vii route;
    auto [fx, fy] = fnd;
    while (true) {
        if (fx == H && fy == H) break;
        auto [rx,ry] = from[fx][fy];
        int zn = z[fx][fy], zr = z[rx][ry];
        assert(zn < zr);
        if (zn+1 < zr) {
            route.eb(zn, zr);
        }
        fx = rx; fy = ry;
    }
    printf("%d\n", (int)route.size());
    for (ii& p: route) {
        printf("%d %d\n", p.first, p.second);
    }
}

int main() {
    int T; cin >> T;
    rep1(t,T){
        printf("Case #%d: ", t);
        int N, K; cin >> N >> K;
        solve(N, K);
    }
    return 0;
}

実装面倒かった
O(TN^2)でLargeは多分TLEだろう
次へ

Bから戻って
ショートカットでステップ数がいくつ減るか考える→ (14,12,10,8),(6,4,2,0) みたいな
減らすべきステップ数 D = (N^2-1) - K

  • このDを(14,12,10,8,6,4,2,0) 的な数の和で表現できるか→Dが偶数なら可能
  • 同じ周回の同じ辺＝ステップ数差分が同じ、なので多分好きなところを使っていい（連続で使うことを考えると最初から真ん中のどこか）
  • 大きいやつからgreedyに使っていいか？
    • 内側のレーンに入った時に入った場所より前の位置ではショートカットできないという制約があるけど、
    • D=18として 18 = 14+4（1周目#1, 2周目#2 なのでOK) = 12+6(1周目#2, 2周目#1なのでNG）
    • 大きい方から取っていけば必ずなんとかなるのでは

→WA 1:42:03

(..略..)

bool solve(int N, int K) {
    if (K % 2 != 0) return false;
    int herasitai = (N*N - 1) - K;
    int hble = (N*2) * (N*2+1);
    if (hble < herasitai) return false;

    int H = N/2;
    auto dp = [&](int x, int y) -> int {
        return ABS(H - x) + ABS(H - y);
    };

    vii route;
    int ofs = 1;
    for (int s=H; s>=1; --s) {
        for (int i=0,d=s*8-2; i<4; ++i,d-=2) {
            if (herasitai == 0) break;
            if (d == 0) continue;
            if (herasitai >= d) {
                int from = ofs + s*2*i + s;
                int to = from + d + 1;
                route.eb(from, to);
                herasitai -= d;
            }
        }
        ofs += s*8;
    }

    printf("%d\n", (int)route.size());
    for (ii& p: route) {
        printf("%d %d\n", p.first, p.second);
    }
    return true;
}

int main() {
    int T; cin >> T;
    rep1(t,T){
        printf("Case #%d: ", t);
        int N, K; cin >> N >> K;
        if (!solve(N, K)) {
            printf("IMPOSSIBLE\n");
        }
    }
    return 0;
}

ならんのか
「内側のレーンに入った時に入った場所より前の位置ではショートカットできないという制約」やっぱ入れないと駄目か
入れたら
→AC(3+4+13) 1:51:42

(..略..)

bool solve(int N, int K) {
    if (K % 2 != 0) return false;
    int herasitai = (N*N - 1) - K;

    int H = N/2;
    auto dp = [&](int x, int y) -> int {
        return ABS(H - x) + ABS(H - y);
    };

    vii route;
    int ofs = 1;
    int lasti = 0;
    for (int s=H; s>=1; --s) {
        bool used = false;
        for (int i=lasti,d=s*8-2; i<4; ++i,d-=2) {
            if (herasitai == 0) break;
            if (d == 0) break;
            if (herasitai >= d) {
                int from = ofs + s*2*i + s;
                int to = from + d + 1;
                route.eb(from, to);
                herasitai -= d;
                lasti = i; used = true; break;
            }
        }
        if (!used) lasti = 0;
        ofs += s*8;
    }
    if (herasitai > 0) return false;

    printf("%d\n", (int)route.size());
    for (ii& p: route) {
        printf("%d %d\n", p.first, p.second);
    }
    return true;
}

(..略..)

Cへ

B. Pixelated Circle (5, 16pts)

R=1000ぐらいまでで実験してみたけどぱっと分かるような性質は見えなかったので、愚直なシミュレーションでsmallをいただくことだけを考えます
→AC(5) 1:10:41

(..略..)
#define WMAX 101

int mem[WMAX*2+1][WMAX*2+1];

void cls(int R) {
  mset(mem, 0);
}
ll count(int R){
  ll c = 0;
  for (int x=-R; x<=R; ++x) {
    for (int y=-R; y<=R; ++y) {
      c += mem[WMAX+x][WMAX+y];
    }
  }
  return c;
}
void pset(int x, int y){
  mem[WMAX+x][WMAX+y] = 1;
}

void show(int R){
  for (int x=-R; x<=R; ++x) {
    for (int y=-R; y<=R; ++y) {
      char ch = mem[WMAX+x][WMAX+y] ? '*' : '.';
      putchar(ch);
    }
    putchar('\n');
  }
}

ll solve(int R) {
  if (R > WMAX) return INT_MAX;

  cls(R);
  for (int r=0; r<=R; ++r){
    for (ll x=-r; x<=r; ++x){
      ll y = (int)round(sqrt(r*r - x*x));
      pset(x,y); pset(x,-y);
      pset(y,x); pset(-y,x);
    }
  }
  ll c_wrong = count(R);

  cls(R);
  for (ll x=-R; x<=R; ++x){
    for (ll y=-R; y<=R; ++y){
      if (round(sqrt(x*x + y*y)) <= R) pset(x,y);
    }
  }
  ll c_right = count(R);

  return c_right - c_wrong;
}

int main() {
  int T; cin >> T;
  rep1(t,T){
    int N; cin >> N;
    printf("Case #%d: %lld\n", t, solve(N));
  }
  return 0;
}

Cに行く前にA-Largeちゃんと考えたくなったので戻る

C. Saving the Jelly (10, 18pts)

生徒10人を呼ぶ順番をnext_permutationして
最寄りキャンディー（先生のやつを除く）を取るをしたときに先生のやつの方が近かったらアウト
→TLE 2:22:01

(..略..)
using Double = long double;
using P = pair<Double, int>;

bool same(Double x, Double y) {
  return ABS(x - y) <= 1e-9;
}

bool solve(int N, vi& x, vi& y) {
  if (N > 10) return false;

  auto d = vec(N, vec(N+1, (Double)INT_MAX));
  rep(i,N){
    rep(j,N+1){
      d[i][j] = hypotl(x[i] - x[N+j], y[i] - y[N+j]);
    }
  }

  vi iot(N); rep(i,N) iot[i] = i;
  vii goo(N);
  int used[N+1];
  vector<P> ps(N+1);
  do {
    mset(used, 0);
    rep(ix,N){
      int i = iot[ix];
      rep(j,N+1){
        if (used[j]) {
          ps[j] = P(LLONG_MAX, j);
        } else {
          ps[j] = P(d[i][j], j);
        }
      }
      sort(ALL(ps));
      Double d0 = ps[0].first; int cho = ps[0].second;
      if (cho == 0) {
        if (!same(ps[1].first, d0)) goto bad;
        else cho = ps[1].second;
      }
      goo[ix] = ii(1+i, 1+cho);
      used[cho] = 1;
    }
    if (used[0] == 0) {
      printf("POSSIBLE\n");
      for (auto [x, y]: goo) {
        printf("%d %d\n", x, y);
      }
      return true;
    }
    bad:;
  } while (next_permutation(ALL(iot)));
  return false;
}

int main() {
  int T; cin >> T;
  rep1(t,T){
    printf("Case #%d: ", t);
    int N; cin >> N;
    vi x(N*2+1), y(N*2+1);
    rep(i,N*2+1) {
      cin >> x[i] >> y[i];
    }
    if (!solve(N,x,y)){
      printf("IMPOSSIBLE\n");
    }
  }
  return 0;
}

最寄りキャンディーを知るためにソートしてた
最小値だけ分かればいいんだからこのソートは削れるじゃんね
→AC(10) 2:26:38

(..略..)

using Double = long double;
using P = pair<Double, int>;

bool same(Double x, Double y) {
  return ABS(x - y) <= 1e-9;
}

bool solve(int N, vi& x, vi& y) {
  if (N > 10) return false;

  auto d = vec(N, vec(N+1, (Double)INT_MAX));
  rep(i,N){
    rep(j,N+1){
      d[i][j] = hypotl(x[i] - x[N+j], y[i] - y[N+j]);
    }
  }

  vi iot(N); rep(i,N) iot[i] = i;
  vii goo(N);
  int used[N+1];
  vector<P> ps(N+1);
  do {
    mset(used, 0);
    rep(ix,N){
      int i = iot[ix];

      Double bes = LLONG_MAX; int bes_at = -1;

      rep(j,N+1){
        if (used[j] || j == 0) {
          continue;
        } else {
          if (d[i][j] < bes) {
            bes = d[i][j]; bes_at = j;
          }
        }
      }
      int cho = bes_at; Double d0 = bes;
      if (d[i][0] < bes) {
        goto bad;
      }
      goo[ix] = ii(1+i, 1+cho);
      used[cho] = 1;
    }
    if (used[0] == 0) {
      printf("POSSIBLE\n");
      for (auto [x, y]: goo) {
        printf("%d %d\n", x, y);
      }
      return true;
    }
    bad:;
  } while (next_permutation(ALL(iot)));
  return false;
}

(..略..)

間に合った！900番台に入ってる！

D. I, O Bot (11, 20pts)

Cが通ったのを確認してから残り２分弱で開いた（けど読まずに諦めて試合終了）
結果待ち

B-Large, C-Largeが軒並み落ちる事が分かっている（＆A-Largeが落ちる可能性だってある）のであとは皆さん次第

結果

781位とな

Round 2初勝利！Tシャツ！！！（Round 3進出は割とどうでもいい説）

オフィシャル通知 (5/17未明)