AtCoder Grand Contest 002:B - Box and Ball
問題
https://atcoder.jp/contests/agc002/tasks/agc002_b
考え方
実験??実験のコツがわかるようになりたい...。
赤いボールが入っている箱から 回の操作によって到達できる可能性がある箱については赤いボールが入りうる。ただし操作後に操作元の箱 x が空になる場合はその箱には赤いボールが入っていることはない。
これをシミュレーションすればよい。
Submission #4351818 - AtCoder Grand Contest 002
到達可能性について、editorialにように言われればまぁ理解できるが、なかなかぱっと正当性がわからない...。ちなみに以下が実験したコードというかぱっと思いついたdp解...実験用コード
public void solve(int testNumber, MyInput in, PrintWriter out) {
int n = in.nextInt(), m = in.nextInt();
// i 回目の操作で箱 j に赤いボールが r 個、白いボールが b 個入っている可能性があるかどうか
boolean[][][][] dp = new boolean[m+1][n][n+1][n+1];
for (int i = 0; i < n; i++) {
dp[0][i][i == 0 ? 1 : 0][i != 0 ? 1 : 0] = true;
}
for (int i = 0; i < m; i++) {
int x = in.nextInt()-1, y = in.nextInt()-1;
// 赤いボールと白いボールがある場合
boolean done = false;
for (int r = 1; r <= n; r++) {
for (int w = 1; w <= n; w++) {
if (dp[i][x][r][w]) {
// 赤いボールを渡す場合
for (int r2 = 0; r2 <= n; r2++) {
for (int w2 = 0; w2 <= n; w2++) {
if (dp[i][y][r2][w2]) {
dp[i+1][y][r2+1][w2] = true;
dp[i][x][r][w] = false;
dp[i+1][x][r-1][w] = true;
}
}
}
// 白いボールを渡す場合
for (int r2 = 0; r2 <= n; r2++) {
for (int w2 = 0; w2 <= n; w2++) {
if (dp[i][y][r2][w2]) {
dp[i+1][y][r2][w2+1] = true;
dp[i][x][r][w] = false;
dp[i+1][x][r][w-1] = true;
}
}
}
done = true;
}
}
}
// 赤いボールしかない場合
if (!done) {
for (int r = 1; r <= n; r++) {
if (dp[i][x][r][0]) {
// 赤いボールを渡す場合
for (int r2 = 0; r2 <= n; r2++) {
for (int w2 = 0; w2 <= n; w2++) {
if (dp[i][y][r2][w2]) {
dp[i+1][y][r2+1][w2] = true;
dp[i][x][r][0] = false;
dp[i+1][x][r-1][0] = true;
}
}
}
done = true;
}
}
}
// 白いボールしかない場合
if (!done) {
for (int w = 1; w <= n; w++) {
if (dp[i][x][0][w]) {
// 白いボールを渡す場合
for (int r2 = 0; r2 <= n; r2++) {
for (int w2 = 0; w2 <= n; w2++) {
if (dp[i][y][r2][w2]) {
dp[i+1][y][r2][w2+1] = true;
dp[i][x][0][w] = false;
dp[i+1][x][0][w-1] = true;
}
}
}
}
}
}
if (!done) new RuntimeException();
// 直前の状態のマージ(移動しなかった分)
for (int j = 0; j < n; j++) {
if (j == y) continue;
for (int r = 0; r <= n; r++) {
for (int w = 0; w <= n; w++) {
dp[i+1][j][r][w] |= dp[i][j][r][w];
}
}
}
}
// m回操作後の最終的な状態で赤いボールが入っている可能性がある箱の数を数える
int ans = 0;
for (int i = 0; i < n; i++) {
boolean ok = false;
top:
for (int r = 1; r <= n; r++) {
for (int w = 0; w <= n; w++) {
if (dp[m][i][r][w]) {
ok = true;
break top;
}
}
}
if (ok) ans++;
}
out.println(ans);
}
どこに着目して考察するべきだったか
実験をすると分かる
何がバグっていたか
得た知見(典型ポイント)
- 実験して法則を見出す
- シミュレーション
類題
yukicoder:No.793 うし数列 2
問題
https://yukicoder.me/problems/no/793
考え方
うし数列を 10 進数で桁ごとに考える。例えば の場合、
となる。項をまとめるのに等比数列の和の公式を用いた。そうすると後は各項ごとに modつきの累乗を取り、 で割る操作は逆元を取れば良い。
#318620 No.793 うし数列 2 - yukicoder
どこに着目して考察するべきだったか
数を 10 進数で見て、桁ごとに考えると解ける。
何がバグっていたか
得た知見(典型ポイント)
類題
全国統一プログラミング王決定戦 エキシビジョン:F - コラッツ問題
問題
https://atcoder.jp/contests/nikkei2019-ex/tasks/nikkei2019ex_e
考え方
サンプル2から であることが分かっているので、これを利用する。
を満たす を とすると である。この結果の両辺に すると
となる。左辺は の偶奇によって仮定の式を適応することができて は奇数であるから
となる。まとめると
となるから、これによって
となることが分かる。偶数の場合も同様だが、 の結果を求めてみよう。
であり は偶数である。この両辺に すると
であることから であることが分かる。
このようにして から の結果を得ることができるので から順番に まで求めることができる。
Submission #4347375 - 全国統一プログラミング王決定戦 エキシビジョン
どこに着目して考察するべきだったか
何が求められているか整理するとサンプル2の両辺から-1をすることで求めたい値を得ることができることが分かる。
何がバグっていたか
得た知見(典型ポイント)
類題
雑記
ちょっと冗長になってしまった...
全国統一プログラミング王決定戦本戦:C - Come Together
問題
https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_c
考え方
難しいが過去にも300点で似たような問題があるので、点数は相応な気はする...
どこに着目して考察するべきだったか
まずは H 軸、W 軸ごとに独立して考えることにしよう。W 軸についてコマを揃えることを考える。
サンプル 1 の例で考えると以下の図のようにそれぞれの列ごとに 1 0 2
マスのコマがあることになる。
これをある列 x にすべて揃えたい。i 列目にあるコマの数を 個としよう。その時のコストを とすると
である。この関数 の最小値を求めたいが、各 について考えると となり間に合わない。しかし は凸関数であることに気づくと三分探索を用いることができて計算量 で最小値を求めることができる。
よって W 軸についてある位置 x にするときの最小値を求めることができた。H 軸についても同様に最小値を求めて、それぞれの最小値の和が解となる。
Submission #4345231 - 全国統一プログラミング王決定戦本戦
何がバグっていたか
得た知見(典型ポイント)
- xy軸を独立に考える
- 差の絶対値の和は三分探索
- 中央値で最小値を取る
類題
- C - Linear Approximation 凸関数の最小値を求めるのに三分探索が使えます。中央値でもOK
SoundHound Inc. Programming Contest 2018 -Masters Tournament-:E - + Graph
問題
https://atcoder.jp/contests/soundhound2018-summer-qual/tasks/soundhound2018_summer_qual_e
考え方
考えていたこと
グラフは連結であるから、ある頂点のコストを決め打ちすると頂点と辺の関係から他の頂点のコストが一意に決まることが分かる。なのでまずは頂点 0 のコストを 0 として考えることとする。
そのとき頂点のコストを 0 から 1 に変化させると、偶数長の頂点は + の変化をして、奇数長の頂点は - の変化をすることが分かる。
がサンプル1のようにある頂点が偶数長にも奇数長にもなりうる場合にどうしていいかわからず...
解説見た
グラフが二部グラフであるかそうでないかが重要。二部グラフの場合、各頂点の偶奇は一意に決まるので、頂点 0 のコストを 0 できめうちして各頂点のコストを計算した後に、それぞれの頂点が 0 以下にならないように初期値の幅を調整すれば良い。このときの初期値の候補が求める場合の数である。
二部グラフではない場合は、実は場合の数は高々 1 通りになる。ある頂点について、奇数長でのコストを とし、偶数長でのコストを とすると、これらが一致するときの は で定まるためである。サンプル1の場合、以下の図のイメージ。グラフが2面あることをイメージすると理解しやすかった。
よって として頂点 0 から再度 dfs で各頂点のコストを求めたときにそれぞれの頂点のコストが 0 以下にならなければ解は そうでなければ となる。
Submission #4339483 - SoundHound Inc. Programming Contest 2018 -Masters Tournament-
実装テク
偶奇分の二回グラフを計算すると実装が楽。kmjpさんの実装を参考にした。
// [初期コスト][偶奇][頂点] = コスト cost = new long[2][2][n]; void dfs(int id, int st, int cur, long v) { if (cost[id][st][cur] == LINF) { cost[id][st][cur] = v; for (P p : g[cur]) { dfs(id, st^1, p.t, p.c - v); } } }
どこに着目して考察するべきだったか
頂点 0 からの長さの偶奇が重要である。また与えられたグラフが二部グラフであるかどうかがポイントであった。
何がバグっていたか
得た知見(典型ポイント)
- 偶奇性から二部グラフを考える
類題
参考
CODE FESTIVAL 2018 Final (Parallel):D - Three Letters
問題
https://atcoder.jp/contests/code-festival-2018-final-open/tasks/code_festival_2018_final_d
考え方
考えていたこと
文字 の長さについて つの箇所を全探索というナイーブな考察以外に思いつかなかった...。 文字なので、真ん中を固定して全探索して考えるとうまくいくことも多いが、解法は思いつかなかった。
あとは、最頻出の文字列について文字数が DP で求められたとすると文字列を復元できないか?最頻出の文字数が 文字だとすると は単調性があって二分探索でうまいことできないか?...などという明後日の方向の考察しか出てこなかった...。
解説見た
文字列の略称の候補を全探索する。その際に各文字について真ん中の文字 つを全探索して、左右の文字の候補については文字種類数で全探索する。略称の候補を数えるためには部分文字列のみが必要であって、文字の位置は問わないため。
そうすると計算量は となり、C++で実装すると間に合う。Java だと TLE
するのでかなり定数倍が重い。
実装テク
- 左右の文字列の計算
ある文字についてその文字位置の左右に登場する文字数を計算するのは、予め文字位置の右に登場する文字を前計算し、文字を進めるごとにその文字を し、左に登場することにするとよい。以下のような実装になる。
int m = str.length; int[] L = new int[52], R = new int[52]; fill(used, false); for (char c : str) R[c2i(c)]++; for (int i = 0; i < m; i++) { int n = c2i(str[i]); R[n]--; for (int left = 0; left < 52; left++) { for (int right = 0; right < 52; right++) { if (L[left] >= 1 && R[right] >= 1 && !used[left][n][right]) { max = Math.max(max, ++cnt[left][n][right]); used[left][n][right] = true; } } } L[n]++; }
Submission #4332300 - CODE FESTIVAL 2018 Final (Parallel)
どこに着目して考察するべきだったか
文字の真ん中を全探索。文字種類が であるから、 はギリギリ間に合うかも...という気持ちになると解ける。
何がバグっていたか
得た知見(典型ポイント)
- 3点の真ん中を全探索
類題
- C - Snuke Festival 3点の真ん中を全探索します
- D - Equal Cut 同じく3点の真ん中を全探索。二分探索との組み合わせ
AtCoder Regular Contest 058:E - 和風いろはちゃん / Iroha and Haiku
問題
https://atcoder.jp/contests/arc058/tasks/arc058_c
考え方
考えていたこと
条件を満たす数列はどのような数列であるか考えた。
を全探索する。そのとき の区間の長さを求めておいて、各区間の長さの要素の和が なる要素の組み合わせを考えると、これは重複組合せで求めることができる。範囲に含まれない要素は の任意の数を選択できる...
みたいな考察を進めていた。がサンプル3で合わず。よく考えると、範囲外の要素で XYZ
の数列が含まれるので数列を重複して数えていることになる。
解説見た
余事象の数え上げを考える。余事象のほうが数え上げやすいため。数列の要素ごとに左から全探索していくことを考える。例えば という XYZ
の組み合わせを考えると、X Y
が決まっていたとすると、どういうときに次の数 Z
を選べないか。
それまでの数字の和が 1 2
となる場合は次に Z
として 1
をとることはできない。 XYZ
が 121
になってしまうため。
数列の状態を bit で考えることにしよう。 であるから として状態を持つことができる。
今までの数列の和の状態が左から 1 2
となる場合に bit として となっているとしよう。このように bit で状態をもつことを考えることがこの問題を bitDP で解くために重要な考察な気がする。このとき として をとることを考えると bit の状態は となる。これは bit の下位(0-indexed)から考えて となっているので状態として遷移することができない。そうでない場合、例えば などを選ぶ場合は となるので遷移することができる。
よって次のようなメモ化全探索を考えよう
桁目まで考えて数列の状態が であるような場合の数
DP遷移は 桁目に数 をとるとすると next = state << j | 1 << j - 1
となる(実装のまんま)。これが XYZ
にならないとき、つまり next >> z - 1 && next >> y + z - 1 && next >> x + y + z - 1
にならないときのみ遷移可能
Submission #4328265 - AtCoder Regular Contest 058
何がバグっていたか
- ダブって数え上げしてしまう
得た知見(典型ポイント)
- 余事象を考える
- 状態を bit でもって全探索
類題
- D - ディスクの節約 bitDPという意味で