Mujin 2017 A. Robot Racing
考察
- 2つ前までしか移動できないので、ロボットが2つ連続で並んでいる箇所があると自由にゴールさせられない。
- 逆にいうとそういう箇所がなければ任意の順でゴールさせられる。
- あるロボットに着目し、前にあるロボットをいくつゴールさせれば自分がゴールできるか考えてみる。とりあえず最初にゴールさせられるかどうかで考える。
ロボットより後ろのロボットをわざわざ動かす必要はない。それより前にあるロボットを2つ連続しないように動かすことができれば最初にゴールさせられる。
直感的に前が詰まり過ぎていると、連続を回避しようと前へ前へと動かすが最終的に座標1に近いあたりで頓挫することがわかる。
こうならない必要条件としては、前に個ロボットがいるなら各についてが挙げられる。これは、最終的に座標1から一つおきに並んでいるギリギリの状態になったとするとそれぞれのロボットはその最終位置よりも右側にある、という条件である。
ここでこの条件が成り立っていると仮定すると、前から順に最終位置にそろえていくことで必ず着目しているロボットを最初にゴールさせられることがわかる。
ここまでくると各ロボットについて前のロボット達を最低何個ゴールさせなければならないか?を考えたくなる。ここで"最低"と言ったがある個をゴールさせれて着目しているロボットをゴールさせられるならば、どの個をゴールさせても適切に前に詰めることでロボットをゴールさせられることがわかる。
一つも動かさなくてよい場合と同様に考える。1つのロボットをゴールさせられると直感的に2マス分の余裕が生まれる。したがって、前に個ロボットがいるなら個くらい取り除く必要がある予想できる。
帰納法でいい感じに示せそう(雑)ということまで確認して実装するとACした。なおこの値の計算は累積maxでやるとになり、これが計算できれば順列の数の計算は簡単な掛け算でできる。
感想
- 限界の状態を考えて条件の定式化、必要条件⇒実は十分の流れがちゃんと導けたので良かった(結構苦手なタイプ)
- ただもう少しスムーズに解きたかった。
- 解説では初めにゴールさせられるか、の考察からstackを使った解法に至っていたが、実質的に上の予想を利用している(スタックの番目が以上だったら...の部分)
void solve() { int N; cin >> N; vector<int> x(N); for (int i = 0; i < N; i++) { cin >> x[i]; } vector<int> c(N, -1); c[0] = c[1] = 0; vector<int> cnt(N + 1, 0); cnt[0] = 2; for (int i = 2; i < N; i++) { int expected = 2 * i - 1; c[i] = max(c[i - 1], (expected - x[i - 1] + 1) / 2); cnt[c[i]]++; } for (int i = 1; i <= N; i++) cnt[i] += cnt[i - 1]; mint ans(1); for (int i = 0; i <= N; i++) { if (cnt[i] - i <= 0) break; ans *= mint(cnt[i] - i); } cout << ans << endl; return; }
Exawizards 2019 C. Snuke the Wizard
考察
- 青diffだが全然わからなくてかなり苦戦した。あることに気づけばあとは簡単。
- 各ゴーレムはあるゴーレムよりも向こう側に行こうと思うと、そのゴーレムと一緒に行動するしかない。すなわち、消滅するゴーレムは左右の端の連続した区間となる。
- この単調性に気づけばあとは二分探索するだけ
感想
- 軽く1時間は溶かしたと思う。なかなか解けないときは対象(今回ならば消える/残るゴーレム)一つ一つの性質ではなく集合全体の性質を考えてみる、というのを意識したい。
- 何かしらの単調性というのが鍵に成る問題は多い。特に1次元上の問題では今回のような性質を真っ先に疑えるような感覚を養っていけると理想。
void solve() { int N, Q; cin >> N >> Q; string s; cin >> s; vector<char> t(Q), d(Q); for (int i = 0; i < Q; i++) { cin >> t[i] >> d[i]; } auto check = [&](int x) { int pos = x; for (int i = 0; i < Q; i++) { if (s[pos] == t[i]) { if (d[i] == 'L') pos--; else pos++; } if (pos < 0) return -1; if (pos >= s.size()) return 1; } return 0; }; int L, R; { int l = -1, r = s.size(); while (r - l > 1) { int mid = (l + r) / 2; if (check(mid) < 0) l = mid; else r = mid; } L = r; } { int l = -1, r = s.size(); while (r - l > 1) { int mid = (l + r) / 2; if (check(mid) > 0) r = mid; else l = mid; } R = l; } cout << R - L + 1 << endl; return; }
Keyence2019 D. Double Landscape
考察
- D - 25個の整数で学んだように、最大値から順番に位置を決定していくのが筋がよさそう。
- 最大値から順に決めていくと、数字の位置を決めることで縦と横のそれぞれ最大値になるかならないかやその数が既に置かれたマスのx,y座標の集合を管理するだけでわかる。
- あとはその情報を用いてうまく数え上げられる。
感想
- つい最近解いた問題で得た教訓が生きてよかった。
void solve() { int N, M; cin >> N >> M; vector<int> A(N), B(M); cin >> A; cin >> B; vector<int> r(N * M, -1); vector<int> c(N * M, -1); for (int i = 0; i < N; i++) { A[i]--; if (r[A[i]] != -1) { cout << 0 << endl; return; } r[A[i]] = i; } for (int i = 0; i < M; i++) { B[i]--; if (c[B[i]] != -1) { cout << 0 << endl; return; } c[B[i]] = i; } mint ans(1); set<int> R, C; int num = 0; for (int i = N * M - 1; i >= 0; i--) { if (r[i] == -1 && c[i] == -1) { int pos = (int)R.size() * C.size() - num; if (pos <= 0) { cout << 0 << endl; return; } ans *= mint(pos); } else if (r[i] == -1) { if (C.find(c[i]) != C.end()) { cout << 0 << endl; return; } ans *= mint(R.size()); C.insert(c[i]); } else if (c[i] == -1) { if (R.find(r[i]) != R.end()) { cout << 0 << endl; return; } ans *= mint(C.size()); R.insert(r[i]); } else { if (C.find(c[i]) != C.end() || R.find(r[i]) != R.end()) { cout << 0 << endl; return; } R.insert(r[i]); C.insert(c[i]); } num++; } cout << ans << endl; return; }
ACL1 C. Moving Pieces
考察
- 最小費用流の形にできそう、超頂点S,Tを用意してコマの開始位置へSから容量1コスト0の辺を張って、好きなところから1つずつ回収してTに送る容量1コスト0の辺を加える。
- 元のグリッドグラフ上では各頂点から右と下に容量無限(コマの個数でよい)コスト-1の辺を張る(ここで-1なのはパスの長さの和を最大化したいから)。
しかし、最小費用流が負辺があるのは少し厄介である。今回は明らかに負の閉路はない。負の辺に対応するには
グラフを変形して負辺を除去する
ポテンシャルの初期化をDijkstraではなくBellman-Fordを用いる
の2通りの方法があるが、今回は1を採用した。(理由: ベルマンフォードでポテンシャル初期化するライブラリを持っていない&ACLにもなかったため)
- グラフの変形による負辺の除去は蟻本のコラムにある。少し複雑そうにも見えるが、基本的なアイデアは負の辺にあらかじめ目一杯流しておいて後で戻すである。 流す量なども変形によって代わることに注意。
想定解&感想
- 想定解ではもっと綺麗に最小費用流の形に言い換えていて、この方法ではグラフに負の辺ははじめから現れない。
- 「パスの長さの和の最大化」として捉えるのではなく、「一番右下まで行ったときに比べてどれくらい損をしたか、の和を最小化」と捉えることですんなりと最小費用流で解ける。
- グラフの変形もそこそこ面倒なのでBellman-Fordで間に合いそうな時用にライブラリ準備しておくべきだなぁ...と思った。
void solve() { int N, M; cin >> N >> M; vector<string> f(N); cin >> f; int s = N * M, t = N * M + 1; int S = N * M + 2, T = N * M + 3; atcoder::mcf_graph<int, int> g(T + 1); auto encode = [&](int i, int j) { return i * M + j; }; int C = 0; for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) if (f[i][j] == 'o') C++; g.add_edge(S, s, C, 0); g.add_edge(t, T, C, 0); int F = C; int geta = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (f[i][j] == '#') continue; int u = encode(i, j); g.add_edge(u, t, 1, 0); if (f[i][j] == 'o') g.add_edge(s, u, 1, 0); if (i + 1 < N && f[i + 1][j] != '#') { int v = encode(i + 1, j); geta -= C; F += C; g.add_edge(v, u, C, 1); g.add_edge(S, v, C, 0); g.add_edge(u, T, C, 0); } if (j + 1 < M && f[i][j + 1] != '#') { int v = encode(i, j + 1); geta -= C; F += C; g.add_edge(v, u, C, 1); g.add_edge(S, v, C, 0); g.add_edge(u, T, C, 0); } } } auto res = g.flow(S, T, F); cout << -res.second - geta << endl; assert(res.first == F); return; }
ACL1 B. Sum is Multiple
考察
- 式を整理すると、を任意の整数としてが成り立つような最小のを求める問題である。
- の素因数がにどのように振り分けられているのかが気になる。
- と置き、がの倍数、がの倍数であるとしよう。の数はそんなに多くないのでこれを固定して全部試すのは可能。
- いまおいた仮定から、整数を用いてとなるが、ここでを消去するととなる。
- これは馴染みのある形で、extgcdで解ける不定方程式である。これを解いて、を満たすが最小の解を求めれば、が求めたかったである。
拡張ユークリッドと中国剰余定理
この問題の想定解ではCRT(中国剰余定理)を用いている(ACL記念回なので使うのはそれはそう...)。自分もどうせCRT使うんだろうとメタ読みして居たのだが先にextgcdで解ける形になったのでそちらで解いてしまった。 自分の中でこの2つの問題は結びついていなかったが、実質的にほぼ同じであることにこの問題で気付かされた。
例えばは今回の変形の逆でと置くことでとなり を解くのと同じことになる。逆も似たように変形できる。
void solve() { ll N; cin >> N; auto fac = factorize(2 * N); int M = fac.size(); ll ans = LLINF; for (int i = 0; i < (1 << M); i++) { ll mul = 1ll; for (int j = 0; j < M; j++) { if ((i >> j) & 1) mul *= fac[j].second; } ll a, b; ll p = mul, q = 2 * N / mul; extgcd(p, q, a, b); if (a >= 0ll) { ll d = ((a / q) + 1); a -= d * q; b += d * p; } if (b <= 0ll) { ll d = ((-b) / p + 1); a -= d * q; b += d * p; } ll d1 = (b - 1) / p; ll d2 = (-1 - a) / q; ll d = min(d1, d2); a -= d * q; b += d * p; assert(a <= -1); assert(b >= 1); chmin(ans, p * (-a)); } cout << ans << endl; return; }
AGC 046 B. Extension
水diffだが解けなかったので自戒の意を込めて記録。
制約から2乗のDPかと思い考えたがうまく重複せずに数えられずDPでない方針を考えた。 その結果いろいろと言い換えはできた(各ブロックは下か左のどちらかから見え、どちらからも見えるものはない等)が、うまく数え上げられず解説を見た。
この問題を解く上で大切な意識は「一つの状態を作るための操作列は様々ありうるが、一つの状態を一つの操作列に1対1に対応させる」ということだった。
今回の場合、一番上の行に黒マスが1つしかないならば最後の操作は行の追加、そうでないならば最後の列の操作である、としてよいことが鍵となる。あとは素直にDPできる。
void solve() { int A, B, C, D; cin >> A >> B >> C >> D; auto dp = vect(C + 1, vect(D + 1, vect(3, mint(0)))); dp[A][B][0] = mint(1); for (int i = A; i <= C; i++) { for (int j = B; j <= D; j++) { if (i == A && j == B) continue; if (i > A) { dp[i][j][0] = dp[i][j - 1][0] * mint(i - 1); dp[i][j][1] = (dp[i - 1][j][0] + dp[i - 1][j][1] + dp[i - 1][j][2]) * mint(j); dp[i][j][2] = dp[i][j - 1][1] + dp[i][j - 1][2] * mint(i); } else { dp[i][j][0] = dp[i][j - 1][0] * mint(i - 1); dp[i][j][1] = dp[i][j - 1][0] + dp[i][j - 1][1] * mint(i - 1); dp[i][j][2] = dp[i][j - 1][1] + dp[i][j - 1][2] * mint(i); } } } cout << dp[C][D][0] + dp[C][D][1] + dp[C][D][2] << endl; return; }
ARC 091 F. Strange Nim
考察
- 独立なゲームが個あるのでGrundy数を考えてみる。が例えば十分大きい偶数なら以下の様になる
0, ..., K-1 | K, ... , 2K - 1 | 2K, ... 0, 0, ....0 | 1, 0, .... 1, 0 | 2, 1, 0, 2, 1, 0...
- Grundy数さえ高速に(くらいで)求められればXOR取るだけ
- 愚直に求めようとすると間に合わないので周期性を用いたい
- が大きい場合と小さい場合に分けてそれぞれの特徴を活かして計算するタイプのやつだろうと直感が働く
- まずが大きい場合、上の例で縦棒で区切っているようにK個ごとのグループに分ける。このときが大きければ(具体的には以上とか)グループ数はさほど多くない(程度)。 番目のグループ内では番目のグループの最後の個にを加えた周期の列が繰り返される。この各グループの周期を求めるのは列の切り貼り挿入ができる平衡二分探索木を用いればlog一つくらい乗るがシミュレーションできる。
- 次にが小さい場合について考えるものの、グループ数が多すぎて手に負えず困った。
- ここで断念して解説を見た
想定解
- Grundy数をと書くことにするとがの倍数でないとき、倍数の時が成り立つ。これは上の考察を踏まえれば簡単にわかる。
- 基本的にはこの式にそって再帰的にもとめていく。ここで前者の場合に、を引いてもなおで割った商が変化しないのであれば一気に引けるだけ引く。これは二分探索で境界を探せば簡単にできる。
- くらいで再帰回数が抑えられ(再帰1回で1ブロック分進むから)、1ステップでだいたい倍くらいになる。
- が大きいときは前者が効いてきて、小さい時は後者が効いてくることでどちらの場合も程度でGrundy数を求められる。
反省点
- Grundy数の様子は把握できていたのにの式を立てられていなかった。周期が見えているときはそれに頼るだけでなくちゃんと定式化するべきだった。(これができていれば大きい場合はわかっていたので、が小さい場合は愚直に再帰して間に合う、ARMERIAさんの解法がそれ(ARC091 F - Strange Nim - ARMERIA))
int grundy(int a, int k) { if (k == 1) return a; if (a < k) return 0; if (a % k == 0) return a / k; int b = a / k; int l = 1, r = a / (b + 1) + 1; while (r - l > 1) { int mid = (l + r) / 2; if ((a - (ll)(b + 1) * mid) / k < b) r = mid; else l = mid; } assert(a - (ll)(b + 1) * l >= 0); return grundy(a - (b + 1) * l, k); } void solve() { int n; cin >> n; int g = 0; for (int i = 0; i < n; i++) { int a, k; cin >> a >> k; g ^= grundy(a, k); } if (g == 0) cout << "Aoki" << endl; else cout << "Takahashi" << endl; return; }