【ABC048】D - An Ordinary Game
問題概要
操作後に同一の文字が隣り合わないように, 両端以外からお互いに1文字ずつ取り除いていく. このような操作を行うことが出来なくなった方が負けとなる. 先手と後手のどっちが勝つかを出力せよ.
制約
- の中に同一の文字が隣り合う箇所はない
考察
操作できなくなる寸前の文字列の長さの偶奇が分かれば, 初期状態の文字列の長さの偶奇と比べることによりどっちが勝つか分かりそう.
両端の文字は絶対取り除けないから, 一旦からそれらを抜き出してみる.
例えば, は になる. 制約より, この隣り合っているの間に何らかの文字があったことは分かるので, となる.
初期状態では9文字だったのが, 操作できなくなる寸前では6文字と, 計3回の操作を行った時点で詰んでいるため先手の勝ちだと分かる.
厳密な証明が出来ないのが怖いけど, 通ったからよし(よくない)
ACコード(Python3🐍)
s = input() t = [i for i in s if i in (s[0],s[-1])] r = len(t) for c,d in zip(t[:-1],t[1:]): r += c==d print('Second' if len(s)%2==r%2 else 'First')
蛇足
(解説が天才すぎて理解できない;。;)
【ARC064】E - Cosmic Rays
問題概要
座標全体に宇宙線が降り注いでいる. 座標上に中心,半径の個のバリアがあり, バリア内では宇宙線から逃れられる. このとき, からまで移動したときの, 宇宙線に晒される距離の最小値を求めよ.
制約
考察
まず, バリア間を移動する際の最短距離を考えてみると, それぞれの円の中心同士を結ぶ線上を移動するのが最短みたい. よって, そのバリア間で宇宙線に晒される距離は, (中心間の距離)-(半径の和)で求められる. (入力例2みたいに重なると負になるから, 0とのmaxをとる)
これで, 任意の2バリア間の距離が求められるから, グラフとして扱えそう.
→ 距離は非負なのでダイクストラ法で求められる.
ただこれだと始点と終点の処理に困るから, それらも半径0のバリアとして扱っちゃえば問題ない!
ACコード(C++🔆)
int barrier[1010][3]; ld dis(int a, int b) { ld res = 0.0; res += sqrt(pow(barrier[a][0]-barrier[b][0],2) + pow(barrier[a][1]-barrier[b][1],2)); res -= barrier[a][2] + barrier[b][2]; if (res < 0) return 0; return res; } signed main() { int start = 0, goal = 1; REP(i,2) { SS(int,x,y); barrier[i][0] = x; barrier[i][1] = y; barrier[i][2] = 0; } SS(int,N); REP(i,2,N+2) { SS(int,x,y,r); barrier[i][0] = x; barrier[i][1] = y; barrier[i][2] = r; } Graph g(N+2); REP(i,N+1) REP(j,i+1,N+2) add_edge(g,i,j,dis(i,j)); vld v = Dijkstra(g,start); cout << setprecision(20) << v[goal] << ln; }
【Educational Codeforces】D - Bicolorings【Round 51】
問題概要
2列n行のマス目を白黒に塗り分ける。塗り分けた後、区画がk個できるような塗り分け方の数を求めよ。結果はかなり大きい数になるため、998244353で割ったあまりを出力せよ。
制約
- 1 <= n <= 1000
- 1 <= k <= 2n
考察
ぱっと見DPっぽいのでDPをする。
(黒,黒),(黒,白),(白,黒),(白,白)の4通りを毎行考えて、区画が増える場合とそうでない場合に分けてそれぞれ漸化式を考える。
dp[何行目まで見た][そこまでの区画数][左の塗り分け][右の塗り分け]とすると、求めるのはのはず。
ACコード(C++🔆)
/* (0,1,2,3) = ((黒,黒),(黒,白),(白,黒),(白,白)) */ const int MOD = 998244353; #define ADD(a,b) a=(a+ll(b))%MOD ll dp[1010][2020][4][4]; signed main() { SS(int,N,K); // 初期値 dp[0][1][0][0] = 1; dp[0][2][0][1] = 1; dp[0][2][0][2] = 1; dp[0][1][0][3] = 1; REP(i,N-1) REP(j,1,2*N+1) REP(a,4) REP(b,4) REP(c,4) { if (b==0 or b==3) { if(b==c) ADD(dp[i+1][j][b][c],dp[i][j][a][b]); else ADD(dp[i+1][j+1][b][c],dp[i][j][a][b]); } else { // (b,c) = (1,2), (2,1) if (b*c==2) ADD(dp[i+1][j+2][b][c],dp[i][j][a][b]); else ADD(dp[i+1][j][b][c],dp[i][j][a][b]); } } ll res = 0; REP(a,4) REP(b,4) ADD(res,dp[N-1][K][a][b]); P(res); }
【ABC103】D - Islands War
問題概要
東西に一列に並ぶN個の島と、それをつなぐN-1個の橋がある。 a_iとb_iの間を行き来できないようにしろ、という要望がM個寄せられた。 取り除かなければならない橋の本数の最小値を求めよ。
制約
- 2 <= N <= 105
- 1 <= M <= 105
- 1 <= a_i < b_i <= N
考察
b_iをソートして、それぞれのb_iの左隣の橋を崩していくのが最適っぽい。(区間スケジューリングっていうらしい)
とりあえず要望をvector<pair<int,int>>にぶち込んで、secondでソートする。
そのsecondを順番に辿って行って、隣の橋(b_i-1,b_i間)を崩したときに要望を達していたらそれを(-1,-1)にして判定の対象外にして...、を繰り返す。
ACコード(C++🔆)
signed main() { SS(int,N,M); vpii request; REP(i,M) { SS(int,a,b); request.PB(MP(--a,--b)); } int res = 0; sort(all(request),SORT_SECOND); REP(i,M) { if(request[i].first<0) continue; int x = request[i].second; REP(j,i,M) { if(between(request[j].first,0,x)) { request[j].first = -1; request[j].second = -1; } } ++res; } P(res); }
【Summer Festival Contest 2018】E - 石積み (Pyramid Piling)
問題概要
https://beta.atcoder.jp/contests/summerfes2018-div2/tasks/summerfes2018_e
制約
2 <= N <= 105
考察
2次元のやつを眺めてたら三角数の並びしてたから、n次元に拡張されたものあるやろっておもったらほんとにあった😮
n次元三角数の式をこねくり回すだけ
なるa,bを求める
式をちょっと睨めばa=n,b=n+1で成り立つことが分かる
ACコード(Python3🐍)
n=int(input()) print(n,n+1)
(https://beta.atcoder.jp/contests/summerfes2018-div2/submissions/3070531)
【CODE FESTIVAL 2015】D - 壊れた電車【予選A】
問題概要
それぞれX_i両目の車両にいるM人の整備士が、N両編成の電車をすべて点検し終えるのに最短で何分かかるか求めよ。但し、点検には時間はかからないが、隣の車両に移動するのには1分かかるものとする。
制約
- 1 <= N <= 109
- 1 <= M <= 105
- M <= N
- 1 <= X_i <= N
考察
方針
求める値をansとして、ansを0,1,2...と地道に増やしていくのだと、それだけでO(N)だから間に合わなさそう。
→ ansを二分探索すれば、そこはO(logN)くらいで収められる
点検できるかの判定
左(車両番号の小さい方)の整備士から順に点検していくとして、最終的な位置がなるべく右にあった方がうれしい。l両目まで点検済みで、c両目にいる整備士がt分点検するとする。
- c <= l のとき、整備士はc+t両目まで点検できるため、l=max(l,c+t)
- そうでないなら、左を経由して右に進む場合と、右を経由して左に進む場合をそれぞれ考えて、より右に進んだ方を選べばよい。但し、最終位置の左側に点検し残した部分がある場合、すなわちc-(l+1)>tのとき、すべて点検し終えることは絶対にできないので省く。
左を経由して右に進む場合、(c)→(l+1)→(r)と移動するため、(c-(l+1))+(r-(l+1))=t、整理してr=t-c+2(l+1)
右を経由して左に進む場合、(c)→(r)→(l+1)と移動するため、(r-c)+(r-(l+1))=t、整理してr=(t+c+l+1)/2
ゆえに、l=max(t-c+2(l+1), (t+c+l+1)/2)
この操作をすべてのcに対して行い、最終的にl>=N-1となれば点検が完了していると分かる。
点検部分は多分O(M)なので、合わせてO(MlogN)だから間に合いそう!
ACコード(C++🔆)
#define reps(i,a,b) for(int (i)=(a); (i)<(b); ++(i)) #define rep(i,n) reps(i,0,(n)) #define chmax(x,y) x=max(x,y) #define P(p) cout << (p) << endl; ll N,M,X[100100]; bool tenken(ll minute) { ll left = -1; rep(i,M) { ll c = X[i]-1; if (c <= left) { chmax(left,c+minute); } else { if (c-left-1 > minute) return false; ll r1 = minute - c + 2 * (left+1); ll r2 = (minute + c + left + 1) / 2; chmax(left,max(r1,r2)); } } return left>=N-1; } signed main() { cin >> N >> M; rep(i,M) cin >> X[i]; ll low = 0, high = 2 * N; while (low<=high) { ll mid = (low + high) / 2; if (tenken(mid)) { high = mid - 1; } else { low = mid + 1; } } P(low); }
https://beta.atcoder.jp/contests/code-festival-2015-quala/submissions/3062027
【ABC043D】アンバランス / Unbalanced【ARC059B】
問題概要
文字列sの中に、過半数が同じ文字となる2文字以上の部分文字列t(アンバランスな部分文字列)は存在するか判定せよ。tが存在するならその区間を、しないなら-1 -1
を出力せよ。
制約
- 2<=|s|<=105
- sは小文字のアルファベットのみからなる。
考察
tは2文字以上なので、とりあえず順番にどんな文字列がアンバランスなのか考えてみる。
2文字の場合は、
aa
やpp
といったAA型
以上、1通りのみ。
3文字の場合は、
dad
やmom
といったABA型zoo
やsee
といったABB型ddr
やmmo
といったAAB型aaa
やzzz
といったAAA型
以上、4通りだが、内ABB型、AAB型、AAA型はAA型を含んでいるため、実際はABA型のみを考えればよさそう。
4文字の場合は、
aaaa
やzzzz
といったAAAA型aaaz
やzzza
といったAAAB型aaza
やzzaz
といったAABA型azaa
やzazz
といったABAA型zaaa
やazzz
といったBAAA型
以上、5通りだが、全てAA型を含んでいるため考えなくてよさそう。
同様に5文字以降も考えていくと、AA型かABA型を含んでいそうなので、この2通りを判別する。
ACコード(Python3🐍)
s=input() for i in range(len(s)-1): if s[i]==s[i+1]: print(i+1,i+2) exit() for i in range(len(s)-2): if s[i]==s[i+2]: print(i+1,i+3) exit() print(-1,-1)