@morio_progの精進日記

解いた競プロの問題をつらつらと。(AtCoder: morio__)

【ARC064】E - Cosmic Rays

AtCoder ARC-E ARC064 ダイクストラ法

問題概要

xy座標全体に宇宙線が降り注いでいる. 座標上に中心(x_i,y_i),半径r_iのN個のバリアがあり, バリア内では宇宙線から逃れられる. このとき, (x_s,y_s)から(x_t,y_t)まで移動したときの, 宇宙線に晒される距離の最小値を求めよ.

制約

  • 1\leq N\leq 1000
  • -10^{9}\leq x_s,y_s,x_t,y_t,x_i,y_i\leq 10^{9}
  • 1\leq r_i\leq 10^{9}

考察

まず, バリア間を移動する際の最短距離を考えてみると, それぞれの円の中心同士を結ぶ線上を移動するのが最短みたい. よって, そのバリア間で宇宙線に晒される距離は, (中心間の距離)-(半径の和)で求められる. (入力例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】

Codeforces Educational Codeforces DP

問題概要

2列n行のマス目を白黒に塗り分ける。塗り分けた後、区画がk個できるような塗り分け方の数を求めよ。結果はかなり大きい数になるため、998244353で割ったあまりを出力せよ。

制約

  • 1 <= n <= 1000
  • 1 <= k <= 2n

考察

ぱっと見DPっぽいのでDPをする。

(黒,黒),(黒,白),(白,黒),(白,白)の4通りを毎行考えて、区画が増える場合とそうでない場合に分けてそれぞれ漸化式を考える。

dp[何行目まで見た][そこまでの区画数][左の塗り分け][右の塗り分け]とすると、求めるのは\displaystyle\sum_{a=0}^{3} \sum_{b=0}^{3} dp[n-1][k][a][b]のはず。

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);

}

http://codeforces.com/contest/1051/submission/43163168

【ABC103】D - Islands War

AtCoder ABC-D ABC103 区間スケジューリング

問題概要

東西に一列に並ぶ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);
}

Submission #3101715 - AtCoder Beginner Contest 103

【Summer Festival Contest 2018】E - 石積み (Pyramid Piling)

AtCoder

問題概要

https://beta.atcoder.jp/contests/summerfes2018-div2/tasks/summerfes2018_e

制約

2 <= N <= 105

考察

2次元のやつを眺めてたら三角数の並びしてたから、n次元に拡張されたものあるやろっておもったらほんとにあった😮

n次元三角数の式をこねくり回すだけ

\frac{a(a+1)\dots(a+n-1)}{n!} = \frac{b(b+1)\dots(b+n-2)}{(n-1)!}なる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】

AtCoder CODE FESTIVAL

問題概要

それぞれ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】

ABC-D ARC-B ABC043 ARC059 文字列 AtCoder

問題概要

文字列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)

https://beta.atcoder.jp/contests/abc043/submissions/3013859