https://code.google.com/codejam/contest/3264486/dashboard
問題
A. Oversized Pancake Flipper
＋と-から成る文字列Sがある。
連続する丁度K個の文字をひっくり返して全て+にする。
最小何回ひっくり返すと全て+になるか。
不可能ならIMPOSSIBLE
B. Tidy Numbers
N以下で最大のtidyな数を答えよ。
tidyな数 : 各桁毎で見ると狭義単調増加列である数
C. Bathroom Stalls
x=0, x=N+1に仕切りがしてある。
以下のルールでK個の仕切りを追加する。
- 左右の仕切りへの距離Ls,Rsのmin(Ls,Rs)が最大となるx座標に置く
- 複数個候補があるならば、その中でmax(Ls,Rs)が最大となるx座標に置く
- それでも、複数個候補がある場合は最も左に置く
K個目の仕切りを置いた時の、左右の距離の最大と最小を答えよ。
D. Fashion Show
N*NのグリッドにM個の'+','x','o'が置いてある。
'+'と'x'は1ポイント、'o'は2ポイント入る。
ポイントを最大化するが、以下のルールを守る必要がある。
- 左右上下の任意の二組のうち、どちらか1つが'+'
- 対角線上の任意の二組のうち、どちらか1つが'x'
以下の操作を行ってルールを守りつつポイントを最大化せよ。
- '+'と'x'を'o'にする
- 空の所に任意の記号を追加する
以下、解説
A. Oversized Pancake Flipper
string S; int K; int sol() { int N = S.length(); int ans = 0; rep(i, 0, N - K + 1) if (S[i] == '-') { rep(j, 0, K) { if (S[i + j] == '-') S[i + j] = '+'; else S[i + j] = '-'; } ans++; } rep(i, 0, N) if (S[i] == '-') return -1; return ans; } //----------------------------------------------------------------------------------- int main() { int T; cin >> T; rep(t, 1, T + 1) { cin >> S >> K; int ans = sol(); if(ans < 0) printf("Case #%d: IMPOSSIBLE\n", t); else printf("Case #%d: %d\n", t, ans); } }
貪欲法で解く。
先頭から順に-ならば反転させていく。
最後に全て+か判定してダメならIMPOSSIBLEとすれば良い。
B. Tidy Numbers
#define rrep(i,a,b) for(int i=a;i>=b;i--) string S; string sol() { int N = S.length(); rrep(i, N - 2, 0) if (S[i] > S[i + 1]) { if (S[i] == '1' && i == 0) { rep(j, 0, N) S[j] = '9'; return S.substr(1); } S[i]--; rep(j, i + 1, N) S[j] = '9'; } return S; } //----------------------------------------------------------------------------------- int main() { int T; cin >> T; rep(t, 1, T + 1) { cin >> S; printf("Case #%d: %s\n", t, sol().c_str()); } }
桁DPをする…と見せかけて貪欲法。
下の位から狭義単調増加してないかを判別する。
もしtidyに反するならば、上の位をデクリメントして、それ以降の桁を全て9で埋める。
これを上まで繰り返していけば答えが得られる。
証明できないし、微妙に正しくないような気もするけど、通る。
C. Bathroom Stalls
typedef long long ll; ll N, K; pair<ll, ll> sol() { priority_queue<ll> que; map<ll, ll> cnt; que.push(N); cnt[N] = 1; ll pre = N + 1; while (!que.empty()) { ll q = que.top(); que.pop(); if (pre <= q) continue; ll a = (q - 1) / 2; ll b = q - 1 - a; if (cnt[q] < K) { cnt[a] += cnt[q]; cnt[b] += cnt[q]; K -= cnt[q]; cnt[q] = 0; que.push(a); que.push(b); } else { cnt[a] += K; cnt[b] += K; cnt[q] -= K; return { max(a,b), min(a,b) }; } pre = q; } return { 0,0 }; } //----------------------------------------------------------------------------------- int main() { int T; cin >> T; rep(t, 1, T + 1) { cin >> N >> K; auto ans = sol(); printf("Case #%d: %lld %lld\n", t, ans.first, ans.second); } }
ダイクストラっぽいBFSをする。
条件より、仕切りが入るのは空白区間の最も長い所から埋まっていくので、それをシミュレーションしていく。
空白区間は約半分になるので、空白区間の状態集合はそんなに大きくないと想像でき、BFSが使える。
cnt[i] := 長さiの空白区間の個数
として、個数を数えながら、丁度K個目となるものを探していく。
あればそれを答えるだけ。
D. Fashion Show
int N, M; char A[10101]; int B[10101], C[10101]; //----------------------------------------------------------------------------------- string board[101], init[101]; void makeBoard(string *ptr) { rep(y, 0, N) { ptr[y] = ""; rep(x, 0, N) ptr[y] += "."; } rep(i, 0, M) ptr[B[i] - 1][C[i] - 1] = A[i]; } void debugPrint() { cout << endl; rep(y, 0, N) cout << board[y] << endl; } //----------------------------------------------------------------------------------- int ngx[101], ngy[101]; void solveX() { rep(y, 0, N) ngy[y] = 0; rep(x, 0, N) ngx[x] = 0; rep(y, 0, N) rep(x, 0, N) if (board[y][x] == 'x' || board[y][x] == 'o') ngx[x] = ngy[y] = 1; rep(y, 0, N) rep(x, 0, N) if (board[y][x] == '.' || board[y][x] == '+') { if (ngx[x]) continue; if (ngy[y]) continue; if (board[y][x] == '.') board[y][x] = 'x'; else board[y][x] = 'o'; ngx[x] = ngy[y] = 1; } } //----------------------------------------------------------------------------------- void solvePlusSmall() { rep(x, 0, N) { if (board[0][x] == '.') board[0][x] = '+'; else if (board[0][x] == 'x') board[0][x] = 'o'; } rep(x, 1, N - 1) { if (board[N - 1][x] == '.') board[N - 1][x] = '+'; else if (board[N - 1][x] == 'x') board[N - 1][x] = 'o'; } } void solvePlusLarge() { // todo } //----------------------------------------------------------------------------------- void sol() { makeBoard(init); makeBoard(board); //debugPrint(); solveX(); //debugPrint(); //solvePlusSmall(); solvePlusLarge(); //debugPrint(); int point = 0; rep(y, 0, N) rep(x, 0, N) { if (board[y][x] == 'o') point += 2; else if (board[y][x] == '+') point++; else if (board[y][x] == 'x') point++; } int cnt = 0; rep(y, 0, N) rep(x, 0, N) if (init[y][x] != board[y][x]) cnt++; printf("%d %d\n", point, cnt); rep(y, 0, N) rep(x, 0, N) if (init[y][x] != board[y][x]) { printf("%c %d %d\n", board[y][x], y + 1, x + 1); } } //----------------------------------------------------------------------------------- int main() { cin.tie(0); ios::sync_with_stdio(false); int T; cin >> T; rep(t, 1, T + 1) { cin >> N >> M; rep(i, 0, M) cin >> A[i] >> B[i] >> C[i]; printf("Case #%d: ", t); sol(); } }
https://code.google.com/codejam/contest/3264486/dashboard#s=a&a=3
この解説の和訳的な解説。あとsatanicさんの解説がくっそ分かりやすい。
satanic0258.hatenablog.com
まず、問題を分割する。
+.. +.o x.. こういう盤面をoが+とxの重なり合いだと考え ... +.. ..x +.+ x.. ... このように分割し、それぞれを別々に最適に解いて .x. +.. ..x +.+ x.. +.. その結果を合成して答えとする +x. +.o o..
はーという感じ。
まず、xの配置だが、これはおけるなら置くを繰り返して貪欲にやっていけば良い(solveX関数)
＋の配置では、SmallとLargeで方針が違う。
Small解(solvePlusSmall関数)
盤面の配列をB[y][x]とすると、B[0][0]～B[0][N-1]とB[N-1][1]～B[N-1][N-2]に+を置く。
すると最適な配置となる。
理由としては、今回の配置は右上がりの斜めと左上がりの斜めをどの+で繋ぐかという二部最大マッチング問題として考えることができ、上の方法の配置だと2(N-1)個配置ができ、これは最大マッチングになっていることが容易に分かる。
Large解(solvePlusLarge関数)
二部最大マッチングを解くのもいいが、最適な貪欲解が存在する。
この部分はsatanicさんのブログを見るのが分かりやすく、恐らく本家の解説もこれと同じ貪欲だと思う。
tanakhさんの貪欲もそう？
プロのツイート。すげぇわ
GCJ
— らて (@LatteMalta) 2017年4月9日
ABC：はい
D：oは、xと+が両方存在しているものとみなせる。よって、+とxについて独立に最適化すればいい。x側は完全2部グラフ(？)の最大マッチングなので貪欲でよくて、+側はうまい方法を思いつかなかったのでもう普通に二部マッチングやった
D: よくよく観察すると、oはxと+を両方置いていると考えることができることがわかる。oを考えなければ、xと+は完全に独立に配置することができる。xはNxNマスに飛車を置く方法なんでこれは自明。+は角を置く方法だけど、これは両端から貪欲において最適になるのは明らか。
— Hideyuki Tanaka (@tanakh) 2017年4月9日
