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

(o_o)

ブログ。

KUPC2013

Cの原案とEとHを担当していました.
C
基本的に左上の頂点と右上の頂点が0flip,左辺と上辺と右辺が1flip,その他が2flipで,各行につき好きなマスをさらに+1flipできる.O(NM).

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int a[128][128];

int main(void)
{
  int h, w;
  cin >> h >> w;
  for (int i = 0; i < h; i++)
    for (int j = 0; j < w; j++)
      cin >> a[i][j];
  for (int i = 0; i < h; i++)
    for (int j = 0; j < w; j++) {
      if (i == 0) a[i][j] = 1 - a[i][j];
      if (j == 0) a[i][j] = 1 - a[i][j];
      if (j == w-1) a[i][j] = 1 - a[i][j];
    }
  int res = 0;
  for (int i = 0; i < h; i++) {
    int num = 0;
    for (int j = 0; j < w; j++)
      num += a[i][j];
    if (num == w) num--; else num++;
    res += num;
  }
  cout << res << endl;
  return 0;
}

E
最短経路を求めて,その経路に従って進んでいくと,300*6=1800クエリくらいでゴールできる.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;

int dist[512][512];
int dest[512][8][2];

int main(){
  int m, s, d;
  cin >> m;
  vector<int> a(6), n(m);
  for (int i = 0; i < 6; i++) cin >> a[i];
  cin >> s >> d;
  s--; d--;
  for (int i = 0; i < m; i++) cin >> n[i];
  for (int i = 0; i < 512; i++) {
    for (int j = 0; j < 512; j++) {
      dist[i][j] = (i == j) ? 0 : 1000000000;
    }
  }
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < 6; j++) {
      for (int k = 0; k < 2; k++) {
        dest[i][j][k] = i + (2 * k - 1) * a[j];
        if (dest[i][j][k] >= 0 && dest[i][j][k] < m) {
          dest[i][j][k] += n[dest[i][j][k]];
          if (dist[i][dest[i][j][k]] > 0)
            dist[i][dest[i][j][k]] = 1;
        }
        else {
          dest[i][j][k] = i;
        }
      }
    }
  }
  for (int k = 0; k < m; k++)
    for (int i = 0; i < m; i++)
      for (int j = 0; j < m; j++)
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

  while (s != d) {
    int dice;
    cin >> dice;
    dice--;
    int stay = dist[s][d];
    int advance = dist[dest[s][dice][1]][d];
    int back = dist[dest[s][dice][0]][d];
    int res;
    if (stay <= advance && stay <= back) res = 0;
    else if (advance < stay && advance < back) res = 1;
    else res = -1;
    cout << res << endl;
    if (res != 0) s = dest[s][dice][(res + 1) / 2];
    fflush(stdout);
  }
  return 0;
}

H
二分探索.O((logN)^2)で1.5secくらい.

#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
  int c;
  long long n, k;
  scanf("%d", &c);
  while (c--) {
    scanf("%lld %lld", &n, &k);
    if (k * 2 - 1 > n) { printf("-1\n"); continue;}
    long long low = 1, up = n+3;
    while (up - low > 1) {
      long long med = (low + up) / 2, num = 0;
      for (long long a=med, m=n; m > 0; a=(a+1)/2,m/=3)
  num += max(min(a/2, (m+1)/2) - (m/3+1)/2, 0LL);
      if (num >= k) up = med; else low = med;
    }
    printf("%lld\n", low);
  }
  return 0;
}

ほんとはO(logN)の解答を用意していて,TLE1.0secの900点問題として出したかったが,諸事情によって×.0.4secくらい.
(1/2)^3>(1/3)^2であることを利用すれば,二分探索の中のループが高々3回で良いことがわかる.

#include <cstdio>
#include <algorithm>

using namespace std;

int main(){
  int c, piv;
  long long n, k;
  long long r[64], l[64], two[64], three[64], nthree[64];
  scanf("%d", &c);
  two[0] = 1; three[0] = 1;
  for (int i = 0; i < 63; i++) two[i+1]=two[i]*2, three[i+1]=three[i]*3;

  while (c--) {
    scanf("%lld%lld",&n,&k);
    n=(n+1)/2*2-1;
    if (k * 2 - 1 > n) { printf("-1\n"); continue; }
    if (k >= n/3+1) { printf("%lld\n", 2*k-1); continue; }
    piv = 0; nthree[0] = (n+1)/2;
    for (piv=0; n>0; n=(n/3+1)/2*2-1, piv++) {
      nthree[piv+1] = (nthree[piv]+1) / 3;
      r[piv] = (n+1)/2; l[piv] = n * two[piv];
      if (piv > 0) r[piv] += max(min((l[piv]+two[piv-1])/two[piv]  , nthree[piv-1]) - nthree[piv], (long long)0);
      if (piv > 1) r[piv] += max(min((l[piv]+two[piv-2])/two[piv-1], nthree[piv-2]) - nthree[piv-1], (long long)0);
      if (k > r[piv]) break;
    }

    long long low = min(l[piv-1]-1,l[piv]), up = l[piv-1];
    while(up - low > 1){
      long long med = (low + up) / 2, num = nthree[piv];
      for(int i = max(0, piv-3); i < piv; i++)
  num += max(min((med+two[i])/two[i+1], nthree[i]) - nthree[i+1], (long long)0);
      if(num >= k) up = med; else low = med;
    }
    printf("%lld\n", low+1);
  }
  return 0;
}