SRM575 Div1 Easy - TheNumberGameDivOne
わかりませんでした😠
ゲーム系のeasyにしてはむずくない?
解法
nが奇数 or 2の奇数乗なら後手、それ以外は先手が勝つ
このゲームは素数を渡されたら負けってことになる
素数は2以外は全部奇数なことに注目する
○nが奇数のとき
そもそもnが素数の場合は先手が即負け
そうじゃない場合、nはどんな操作をしても「2の累乗ではないような偶数」になる
(何かしらの操作によってnを2の累乗にできると仮定するとnは2の累乗の倍数 → 偶数になるから矛盾)
そういう数字は必ず奇数の約数が存在するため、返しのターンで後手が奇数にして返せる
よって何度繰り返しても先手には奇数が返ってきて、いつかはそれが素数になる
○nが2のp乗のとき
このnに操作を行うと「2の累乗」or「2の累乗でない偶数」のどちらかを作れる
↑の通り後者を相手に渡すと負けるから前者を選び続けるしかない
前者にするってのはnをn/2に変えるってことで、そうするとターン数はpターンになる
よってpが奇数なら負け、偶数なら勝ち
class TheNumberGameDivOne { public: string find(ll n) { if (n%2) return "Brus"; rep(i,60) if (i%2 && n==(1ll<<i)) return "Brus"; return "John"; } };
https://community.topcoder.com/stat?c=problem_statement&pm=12496&rd=15495
第3回ドワンゴからの挑戦状 本戦 A - 計算ドリル
俺のrated500埋めの最後の問題がこれ
atcoderでこういう実装ゲーはかなり珍しい
問題
'0'〜'9'、'+'、'-' のみからなる文字列sが与えられる
これをk文字まで書き換えて得られる、逆ポーランド記法で計算できる正しい文字列のうち、計算結果の最大値を求めよ
1 <= |s| <= 52
0 <= k <= |s|
解法
メモ化しながら区間dp
数式の一番最後の文字は '+' か '-' である必要があり、それ以外の部分は2つの式に分けることができるってのがポイント
この区切りとそれぞれの区間に割り振るkを全探索して更新していく
詳細は↓のコメントの通り
string s; int n, k, dp[55][55][55][2]; bool fin[55][55][55][2]; const int M = 10000; // [l,r]をk文字まで変えたときの最(b?大:小)値 int rec(int l, int r, int x, bool b) { if (fin[l][r][x][b]) return dp[l][r][x][b]; fin[l][r][x][b] = 1; int &res = dp[l][r][x][b]; res = (b ? -M : M); // どう変えても正しい式にならない場合 if ((r-l+1)%2==0) return res; // 1桁の場合 if (l==r) { if (x) res = (b ? 9 : 0); else if (isdigit(s[l])) res = s[l]-'0'; return res; } // 一番右の文字は+か-にする int xp = x - (s[r]!='+'), xm = x - (s[r]!='-'); // 2つの式の和の最大値は (最大)+(最大) or (最大)-(最小) if (b) { reps(i,l,r-1) { rep(j,xp+1) { int tx = rec(l,i,j,1), ty = rec(i+1,r-1,xp-j,1); if (tx!=-M && ty!=-M) chmax(res, tx+ty); } rep(j,xm+1) { int tx = rec(l,i,j,1), ty = rec(i+1,r-1,xm-j,0); if (tx!=-M && ty!=M) chmax(res, tx-ty); } } } // 最小値は (最小)+(最小) or (最小)-(最大) else { reps(i,l,r-1) { rep(j,xp+1) { int tx = rec(l,i,j,0), ty = rec(i+1,r-1,xp-j,0); if (tx!=M && ty!=M) chmin(res, tx+ty); } rep(j,xm+1) { int tx = rec(l,i,j,0), ty = rec(i+1,r-1,xm-j,1); if (tx!=M && ty!=-M) chmin(res, tx-ty); } } } return res; } signed main() { cin >> k >> s; n = s.size(); int res = rec(0,n-1,k,1); if (res==-M) cout << "NG" << endl; else cout << "OK" << endl << res << endl; }
https://beta.atcoder.jp/contests/dwacon2017-honsen/tasks/dwango2017final_a
ARC087 F - Squirrel Migration
これ800点ってマジ?ムズすぎてハゲた
問題
n頂点の木があり、全ての頂点にリスがいる
長さnの順列pを決め、頂点iのリスを頂点p[i]に移動させる
各リスの移動距離の総和が最大になるようなpは何通りあるか
2 <= n <= 5000
解法
x-yを繋ぐ辺を通るリスの数の最大値は、xyそれぞれを根とする部分木をtx, tyとすると、
2 * min(|tx|, |ty|) である
サイズが小さい方の部分木のリスが全てもう片方の部分木に移動する場合にこうなる
○木の重心が2個ある場合
重心間の辺について↑の条件を満たせば他の全ての辺も条件を満たす
重心が2個ある場合、各重心を根とする部分木のサイズはどちらもn/2になるから、答えは{(n/2)!}^2
○重心が1個しかない場合
重心から伸びている辺全てについて↑の条件を満たせば他の全ての辺も条件を満たす
各部分木の全リスが「元々いた部分木上の頂点」以外のどこかに行くような順列pの個数を求めればいい
これは部分木ごとにサイズが違うから重心が2個の場合ほど単純には行かない
ここで余事象の「同じ部分木に留まるようなリスが1匹以上存在する」を考える
明らかにこっちの方が考えやすそうだからこっちを包除原理で求める
重心に隣接する各頂点を根とする部分木をT1, T2, ..., Tkとする
以下数式が複雑でタイプするのめんどいからクソ汚いメモをそのまま貼ります
途中で|T|とかΣ|Ti|って何回か書いてるけどこれは明らかにn-1(重心以外の全頂点の個数)
あと最後の行のdp[|T|][x]はdp[k][x]の間違い
実装(プログラムの流れ)
f[i]: iの階乗 は最初に求めておく
頂点0を仮の根とし、rec()で各頂点vを根とする部分木のサイズsz[v]を求めつつ重心を探す
直接の子c[i]全てについてsz[c[i]]がn/2以下 かつ n-sz[v]もn/2以下ならvは重心
(木の重心の詳細はググって)
gが1個目の重心でggが2個目の重心
2個目の重心ggが存在する場合は{(n/2)!}^2を出力して終了
次に重心gを木の根とし、rec2()で各頂点vを根とする部分木のサイズsz[v]を求める
gに隣接する頂点を根とする部分木のサイズをvector
あとは↑の通りにdpして包除原理
comb(n,k) = nCk は省略
#define int long long int n, a, b, sz[5050], g = -1, gg = -1, f[5050], k, dp[5050][5050], res; vector<int> e[5050], t; int rec(int v, int p) { bool gp = 1; sz[v] = 1; each(i,e[v]) if (i!=p) { int tmp = rec(i,v); if (tmp>n/2) gp = 0; sz[v] += tmp; } if (gp && n-sz[v]<=n/2) { if (g==-1) g = v; else gg = v; } return sz[v]; } int rec2(int v, int p) { each(i,e[v]) if (i!=p) sz[v] += rec(i,v); return sz[v]; } signed main() { f[0] = 1; reps(i,1,5050) f[i] = f[i-1]*i %mod; cin >> n; rep(i,n-1) { cin >> a >> b; a--, b--; e[a].push_back(b), e[b].push_back(a); } rec(0,-1); if (gg!=-1) return cout << f[n/2]*f[n/2] %mod, 0; memset(sz, 0, sizeof(sz)); rec2(g,-1); each(i,e[g]) t.push_back(sz[i]), k++; dp[0][0] = 1; rep(i,k) { int sum = 0; rep(j,i) sum += t[j]; rep(x,sum+1) rep(y,t[i]+1) (dp[i+1][x+y] += dp[i][x] * comb(t[i],y) %mod * comb(t[i],y) %mod * f[y]) %= mod; } rep(i,n) (res += dp[k][i] * f[n-i] * (i%2 ? -1 : 1)) %= mod; (res += mod) %= mod; cout << res << endl; }
冷静に見ると1つ1つはそこまで難しくない典型の組み合わせなんだよな
論理的思考+典型力で解ける問題ではあるんだろうな
Codechef - Chef and K Segments [CHEFKO]
問題
n個の区間があり、i個目区間の左端はL[i]、右端はr[i]である
これらから好きな区間をk個選び、それら全ての共通区間の長さをスコアとする
スコアの最大値を求めよ
1 <= k <= n <= 10^5
1 <= L[i] <= r[i] <= 10^9
解法
スコアを二分探索すれば解ける
スコアをdにすることが出来るかの判定方法を考える
共通区間の左端右端はそれぞれ、n個の区間のどれかの左端右端と一致するはず
よって左端右端の候補はそれぞれn通りしかない
左端をL[i]とすると、
1) 左端がL[i]以下
かつ
2) 右端がL[i]+d以上
の区間がk個存在すれば良い
与えられる区間を左端の昇順にソートして左から順に1個ずつ見ていくことにすると、条件1を満たすのは今見ている区間と今まで見た区間だけになる
更にその中に条件2を満たすものが何個あるかを数えたい
これは降順priority_queueに今まで見た区間の右端の座標を入れていけばわかる
queue.top()が今の条件2を満たすまでpopし続け、その後のqueueのサイズが条件を両方とも満たすような区間の個数になる
区間は左端の昇順に並んでるから、見る区間を右にずらしていくと条件2は単調に厳しくなっていくため、一度popした要素は二度と使うことはない
O(n(logn)^2)で、TLが1sで0.93sかかってる
こういうやたら厳しいTLって極限まで定数倍高速化した愚直解とかbitsetで高速化みたいなのが間違って通らないためにやってんだろうけど、ちょっと定数倍が遅いくらいのまともな解法が落ちるよりはそっちのが不幸な人減らない?
int Q, n, k; pair<int,int> p[100100]; bool ok(int d) { priority_queue<int, vector<int>, greater<int> > q; rep(i,n) { q.push(p[i].second); while (!q.empty() && q.top()<p[i].first+d) q.pop(); if (k<=q.size()) return 1; } return 0; } signed main() { cin >> Q; while (Q--) { cin >> n >> k; rep(i,n) cin >> p[i].first >> p[i].second; sort(p, p+n); int l = 0, r = 1<<30; while (r-l>1) { int m = (l+r)/2; (ok(m) ? l : r) = m; } cout << l << endl; } }
CF519 F - Make It One
良問だった
問題
n個の整数aが与えられる
aの部分集合のうち全要素のgcdが1になるようなもののサイズの最小値を求めよ
(存在しない場合は-1)
1 <= n <= 3*10^5
1 <= a[i] <= 3*10^5
解法
2*3*5*7*11*13 < 3*10^5 < 2*3*5*7*11*13*17
より答えはたかだか7であることがまずわかる
dp[i][j]: i個の要素を含み、それらのgcdがjになるような部分集合の個数
とすると包除原理より
dp[i][j] = (a[]のうちjで割り切れるものをi個選ぶ組み合わせの数) - Σdp[i][k] (k: jを除くjの倍数)
となる
d[i]: iで割り切れるa[j]の個数 を事前に求めておき、dpテーブルをjの降順に埋めていけばO(mlogm)で求められる
(m: max(a))
dp[i][1]>0を満たす最小のiが答え
int n, a[300300], b[300300], dp[10][300300], d[300300]; signed main() { cin >> n; rep(i,n) { cin >> a[i]; b[a[i]]++; } reps(i,1,300200) for (int j=i; j<=300200; j+=i) d[i] += b[j]; reps(i,1,8) for (int j=300200; j>=1; j--) { dp[i][j] = comb(d[j], i); for (int k=j*2; k<=300200; k+=j) (dp[i][j] += mod - dp[i][k]) %= mod; } reps(i,1,8) if (dp[i][1]) return cout << i << endl ,0; cout << -1 << endl; }
CF519 D - Mysterious Crime
超凡ミスで2問落としてまた1893まで落ちちゃった
マジで深夜はパフォーマンス落ちる
問題
長さnの順列がm個与えられる
それぞれの順列の先頭と末尾からいくつかの数字を消し、全ての順列を一致させたい
数字の消し方は何通りあるか
1 <= n <= 10^5
1 <= m <= 10
解法
1個目の順列が 1,2,3,... となるように各順列の数字を変換する
(2,1,4,3 -> 1,2,3,4 とすると 2->1, 1->2, 4->3, 3->4 という変換ルールが出来るということ)
すると、最終的な数列のうち1個目の順列のk番目を左端とするものの最長の長さは
min(各順列のkから右にk+1, k+2, ...と1ずつ増えていくような列の長さの最大値)
となる
この長さの最大値は単純なdpで求められる
左端と最長の長さLが決まれば、kを左端とする長さ1,2,...,Lの数列は全て作れるから、左端を全部試して答えにLを足していけばいい
今見るとめちゃくちゃ簡単なんだけど眠すぎてボケてたのか、本番では長さの最大値をdpするって発想が出てこなくて二分探索してた
二分探索だと4,5,6と4,6,5の区別が付かないからダメ & 計算量的にも危険
int n, m, a[11][100100], res, p[11][100100], dp[11][100100]; map<int,int> con; signed main() { cin >> n >> m; rep(i,m) rep(j,n) cin >> a[i][j]; rep(i,n) con[a[0][i]] = i+1; rep(i,m) rep(j,n) a[i][j] = con[a[i][j]], p[i][a[i][j]] = j; rep(i,m) for (int j=n-1; j>=0; j--) { if (a[i][j]==a[i][j+1]-1) dp[i][j] = dp[i][j+1] + 1; else dp[i][j] = 1; } reps(j,1,n+1) { int mn = 1<<30; rep(i,m) chmin(mn, dp[i][p[i][j]]); res += mn; } cout << res << endl; }
Tenka1 Programmer Contest 2018 E - Equilateral
はてなブログたまに写真表示されなくならないか?
問題
h*wのグリッドがあり、いくつかのマスにはコインが置かれている
相異なるコイン3つの組のうち、どの2つのコイン同士のマンハッタン距離も同じであるようなものは何個あるか
1 <= h, w <= 300
解法
マンハッタン距離ってことでとりあえず45度回転して考える
2点X, Yの max(x座標の差, y座標の差) をdとすると、3点X, Y, Zが問題の条件を満たすには、X, Yそれぞれを中心とした1辺2dの正方形の交線上にZがある必要がある
↓はX, Yのx座標とy座標が共に異なり、共通範囲が点になる場合
結局↑のように3点のうち2点のx座標かy座標は等しくなることがわかる
よってx座標 or y座標が等しい2個のコインのペアを全て見て、この↑交線上にあるコインの個数を足し合わせていけばO(h^3 + w^3)で答えが得られる
ただし同一正方形の3 or 4角にコインがある場合は同じ組を重複カウントしてしまう
3角にコインがある正方形は1個につき1、4角の正方形は1個につき4だけ答えから引けばきれいに重複を消せる
(絵描いてみればわかる)
実装
重複を消すのは、x座標が等しい2点のペアを全部試す時に「同じ正方形の3角にコインがある」ことを確認する度に1引けばok
こうすれば3角の正方形は1回、4角の正方形では4回引っかかるからちょうど重複を消せる
hs: ヨコ方向の累積和
vs: タテ方向の累積和
int h, w, a[666][666], hs[666][666], vs[666][666], res; string s[333]; signed main() { cin >> h >> w; rep(i,h) { cin >> s[i]; rep(j,w) if (s[i][j]=='#') a[i+j+1][i-j+300] = 1; } reps(i,1,600) reps(j,1,600) { hs[i][j] += a[i][j] + hs[i][j-1]; vs[i][j] += a[i][j] + vs[i-1][j]; } reps(i,1,600) reps(j,1,600) reps(k,j+1,600) { int d = k-j; if (a[i][j] && a[i][k]) { if (i-d>=0) { res += hs[i-d][k] - hs[i-d][j-1]; res -= a[i-d][j] + a[i-d][k]; } if (i+d<=600) { res += hs[i+d][k] - hs[i+d][j-1]; res -= a[i+d][j] + a[i+d][k]; } } if (a[j][i] && a[k][i]) { if (i-d>=0) res += vs[k][i-d] - vs[j-1][i-d]; if (i+d<=600) res += vs[k][i+d] - vs[j-1][i+d]; } } cout << res << endl; }
後からなら何でも言えるけどD捨てれば解けてた
まあ反省するべきはそれよりDが解けなかったことだな
構築っぽくて見ただけで拒否反応が出たけど閃きが必要な問題ではなかったから冷静に考えれば解けたはず
Cで割と萎えてたのはあると思う
https://beta.atcoder.jp/contests/tenka1-2018/tasks/tenka1_2018_e