codechef
問題概要 01のならんだ文字列が与えられる。自マスと隣接マスが0の個数を数える問題。
問題概要 T個のテストケースに対して答がY/Nという結果がT個ならんでいる。完全一致していたら正解でそれ以外は不正解となる。 解法 どれが答になっているか全探索する。全部合わなかったら全部NOと出力する。
問題概要 階差数列の和が一定数を越えるか判定する問題。
問題概要 辺が与えられる。辺にはコストとAまたはBの属性がある。全域木をつくって、Bに属するコストを最大化し、そのなかで全コストの和を最小化したい。それぞれの値を求める問題。 解法 ただの最小全域木。
問題概要 ?の混じった文字列が与えられる。回文になるように?にアルファベットを埋める方法が何通りあるか求める問題。 解法 対応する2箇所を比べる。
問題概要 長さN( 解法 前から順に最小値を覚えておく。
問題概要 長さNの置換pがprime permutationであるとは各iについて最初のi個の数字の中でp[i]がX番目(X=1or素数)に小さいようなものを言う。各iについて長さiのprime permutationがいくつあるか求める問題。 解法 p(i)をi以下の素数の個数とする。今、ans[i+1…
問題概要 長さN,M( 解法 末尾がn文字一致している状態から必要な個数の期待値をE[n]とする。failure linkを用いて連立一次方程式を立式できる。このとき、各iについてE[i]=P[i]+Q[i]*E[0]とおくことによってE[N]=P[N]+Q[N]*E[0]までDPで計算できる。あとはE[…
結果。 4/5完。接続不良でペナルティにほとんど意味が無い。SPOJ使う限りこうなるのは避けられない気がする。
問題概要 数字からなる部分列が与えられる。長さ1~4の部分列でdigit rootが9になるものの個数を求める問題。 解法 digit rootが9となることは各桁の和が9の倍数かつ0でないことと同値。なので、長さと和を9で割った余りを状態としてDPすればO(N*5*9)位で求め…
問題概要 長さNの配列がある。最初はX[i]=iである。区間に定数を足し込む操作を繰り返した後、最大値と最小値の差を出力する問題。 解法 いもす法で処理できるけど、真面目にやるとTLEする。なので適当に座標圧縮する。
問題概要 4,7からなる文字列S(|S| 解法 置換はとりあえず無視して、各iに対してF(S[0:i])を求めておく。また、F(S[i:$])も求めておく。これにより4と7の切り替わる位置を全探索することができる。位置iで切ったときの最大値はF(S[0:i])+F(S[i:$])になるから…
問題概要 無向重み付きグラフが与えられるのである点からある点までの最短路のパスの総数を求める問題。 解法 サイズが小さいのと重みが非負なのでDijkstraするまでもなく(位置、距離)を組にしたDPでやるのが簡単。
問題概要 P( 解法 貪欲に選べばよい。
問題概要 2次元平面上にN( 解法 どの3点も同一直線上にないので、N=4以外のときは自由に選べる。N=4のときは単純に全探索すれば良い。多分純粋に全探索でも間に合うけどN=4のときの計算しやすさとTLE対策に一応凸法とってからやってみたら余裕だった。
問題概要 文字列Tを前半と後半(ただし後半は非空)に適当に分け、前半に含まれる4の数と後半に含まれる7の数が一致するときTはバランスがとれているという。長さL( 解法 文字列Tがバランスがとれている条件を考える。4[i,j]を部分文字列T[i,j]([i,j)の半開区…
問題概要 長さ50以下の文字列がK+N個(K,N 解法 小さいので愚直にやって間に合う。
結果。 3/5完。lucky numberな回。もう少し早く解けるようになると嬉しい。
問題概要 G=(V,E)からG'を以下のように得る。G'=(V',E')とすると、V'=Eで、辺aと辺bがGで同じ頂点に接続していたら(a,b) in E'となる。今、グラフG[0]=(V,E)(|V|, |E| 解法 まず、|E|
問題概要(適当) 全探索すれば解ける問題。
結果。 2/5完。整理できてないままコーディングを始めると混乱すると分かっているのになぜ書き始めてしまうのか。 数学ゲーの方が簡単らしいけどグラフに逃げた。解けたので結果オーライだけど、戦略としてはよくない。
問題概要 DAG上で最長パスを求める。
問題概要 ノード数N( 辺を追加する 辺を削除する K(>1)彩色の仕方が何通りあるか出力する を処理する。ただしグラフは常に森である。 解法 答えは、各連結成分に対してK*(K-1)^(size-1)をかけ合わせる。 連結成分の個数とサイズを求めるのは、制約が緩いので…
問題概要 球面上にN個の点とM個の点がある。N個の点を中心として半径R以内にあるM個の点との間に辺をはる。M個の最大マッチングを持つ最小の半径Rを求める問題。 解法 球面上での2点間の距離は公式で求められる(弧度法に変換するのを忘れないこと)。後は半径…
問題概要 ノード数V( 解法 クエリを受ける前に全ての答えを計算しておく。まず、前処理として始点から各頂点への距離と終点から各頂点への距離をdijkstraで求めておく。 また、ついでに始点からのshortest path treeとshortest pathを計算しておく。このとき…
問題概要 ノード数N( 解法 適当な頂点を選んで根付き木にして、LCAを計算しておく。Sの元(v,u)は、lca(u,v)!=u or vのとき(v,lca(v,u)), (u,lca(v,u))と変換してもよいことが分かる。この様な変換を加えておくと、再帰的に計算するとき上手く値をキャンセル…
問題概要 dat[x][y][z]は0or1の値を持つ。以下のクエリを処理する。0:x1 解法 各座標独立に考える。和のクエリ(x1,y1,z1,x2,y2,z2)が来たときに、([x1,x2]での0の個数)*([y1,y2]での0の個数)*([z1,z2]での0の個数) + ([x1,x2]での0の個数)*([y1,y2]での1の個…
問題概要 f(N) = Σ di μ(di) に対して、|f(N)|>Xとなる最小のNを求める問題。X 解法 この式はn=Π p_i^e_iに対してf(n) = Π (1-p_i)を計算する式である。基本的には元の数より大分小さくなって損してしまい、結局素数が有利になる。X+2以上の最小の素数が答え…
問題概要 ノード数V( σ(0)=0 (v,u) in E ⇒ (σ(v), σ(u)) in E 解法 まず、0を根とした有向木にする。各部分木に対して同型判定が簡単にできれば再帰的に掛け合わせて答えを求めることができる。問題は各部分木に対して同型判定を以下に効率よくやるかだが、…
問題概要 N( 解法 一度レストランとつながった家はレストランになると考えれば分かりやすい。コストを昇順に持つプライオリティーキューを用意して、片方がレストランになってるような辺を随時加えていく。この際家がレストランになったならその家を端点に持…
