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; }