問題概要 1~M(M 解法 直前何桁まで連続しているかを持ちながらDP。leading zeroに注意。

問題概要(適当) merge sortのmergeの際にどちらから選んだかの情報が与えられるので元のデータを復元する問題。 解法 まず、順にシミュレートして与えられるデバッグ出力列のどの部分が充てられるのかを求めておく。この情報を持っておけば逆順に復元するこ…

問題概要 整数S(0, x+y>0)で、x+y+a+bのとりうる最小値を求める問題。 解法 comb(x+y,y)がS以下となる組み合わせは多くないので全列挙する。以下のコードは色々怪しい。

結果。 Cは簡単。Aは自信なかった。Bは今見返すとAより簡単。大量に解かれていて全完必須だった。

問題概要(適当) 辺数がE=18のグラフがある。ふたりでゲームをする。交互に色を塗り、三角形ができたら1ポイント獲得してさらに自分の手番になる。先手が勝つか後手が勝つか引き分けか判定する。 解法 既に選んだ辺に関してビットDPする。

問題概要 ノード数N( 解法 二重辺がある場合はLCAで簡単。二重辺がない場合、ひとつのサイクルに木がぶら下がってる感じになる。そのとき、同じ木の中にある2点間についてはLCAで、そうでないときは根までの距離に紺のサイクル上の距離をたしたのが答えにな…

競技プログラミング歴2年目 2年経ってまだ黄コーダー…。周囲のレベルが上がっていることは確実(自分がSRMに出始めたときはDPやsetの存在すら知らなかったけどeasy解くだけで黄まですぐいけた)なんだけど、やっぱり赤くなりたい。いやMarathonとかは開始1年で…

問題概要 2*N(N 解法 dp[n] = {2*nのサイズの全てが白のボールを上から黒く塗る場合の数}とするとこれは二項係数を用いて簡単に計算することができる。後は最初に塗るボールをどれにするか全通り試せば良い。

問題概要(適当) 再帰的に定義される数列があるので第N項を計算する問題。 解法 数列の定義を正確に把握できればコードにはすぐ落とせる。

結果。 virtual participationした。序盤にかなりつまづいたのが痛かった。解いていてそこまで難しくは感じなかったけど実装が妙に面倒なのが多かった印象。最後はC問題やってたけど実装面倒+二重辺に気づかず通せなかった。

問題概要 サイズ10*10のライツアウトを解いて最小手順を答える。 解法 このサイズなら全探索。(サイズが大きくなったら連立一次方程式を考える)

問題概要 区間[0,1]で単調減少な関数が与えられるので根を求める問題。 解法 二分探索。浮動小数点数のせいで端点の処理が面倒くさい。

問題概要 長さN( 解法 全探索。タイブレークのルールをよく理解していないけど要素数の多い方を優先するようにしたら通った。

問題概要 N( 解法 期待値の線形性を使う。各箱について、それが1度以上選ばれる確率を求めてやればよい。

問題概要 長さN( 考えたこと 答えに関して二分探索。判定は貪欲でやる。

問題概要 ノード数V( 解法 頂点、偶奇を組にしてDijkstraするだけ。

問題概要 子供がK( 解法 W個の指定されたものによって円ができてよいのはK個全てが出現したときだけ。それ以外のときは直線が集まったものなら残りを適当につなげて円を作ることができる。連結なグラフが直線である条件は最低次数が1で最高次数が2以下である…

問題の流用があったのか複数収録されている(微妙に出力や入力が違う、ソート済みかそうでないかとか)。 問題概要 N(k-1個の円をそれぞれ下の二つの間に置いていく。このときちゃんと置けることが保証されている。一番上に置いた円の中心の座標を求める問題。…

問題概要 x,y,z(いずれも値はsigned intに収まる)が与えられるのでx^y (z)を求める問題。 解法 いわゆるバイナリ法を使って計算する。

問題概要 [0,10^6(=:L))でのスケジュールを考える。[a,b)というスケジュールがN( 解法 長さLの配列を塗りつぶしていく。計算量が危ないように錯覚したけどダブった時点で処理を止めれば計算量はO(L)で抑えられる。

問題概要 長さN( 解法 1~10^9までにlucky numberは1022(=:M)個しかない。これよりlucky numberがそれぞれ何個あるか、というデータ構造に変更しておくと、易しいDPの問題に落ちる。

問題概要 4がa1個、7がa2個、47がa3個、74がa4個部分文字列として含まれる辞書順最小の部分文字列を求める問題。できないときは指摘。 解法 場合分けでといたが、それはあまりよくない。辞書順最小の定石どおり、判定問題に落として解くべきだった。

問題概要 4、7からなる長さN(スワップする、書き換えるのにコストが1かかる。文字列XをYに変換するのに必要なコストを求める。 解法 もともと同じ位置に同じ文字が入っているのは無視してよい。4->7(7->4)にしなければならないのをA(B)とするとmax(A,B)が答…

結果。 lucky numberな回。順位はそれなり。でもやっぱり2500は手も足もでない感じだった。 Aはさっくり。Bは場合分けに行ってしまったのが残念(判定がO(1)でできれば場合分けしなくてもいいけど無理だよなぁ、とか本番中は考えていた。冷静に考えたらO(1)で…

問題概要 DAG上で最長パスを求める。

問題概要 ノード数N( 辺を追加する 辺を削除する K(>1)彩色の仕方が何通りあるか出力する を処理する。ただしグラフは常に森である。 解法 答えは、各連結成分に対してK*(K-1)^(size-1)をかけ合わせる。 連結成分の個数とサイズを求めるのは、制約が緩いので…

問題概要 球面上にN個の点とM個の点がある。N個の点を中心として半径R以内にあるM個の点との間に辺をはる。M個の最大マッチングを持つ最小の半径Rを求める問題。 解法 球面上での2点間の距離は公式で求められる(弧度法に変換するのを忘れないこと)。後は半径…

問題概要 N*N(N 解法 r,cを辞書順にソートして貪欲に小さい方に詰めていけばよい。最も小さいところを選ぶのにはBITやsetなどの適切なデータ構造を用いれば対数時間程度で求めることができる。

問題概要 ノード数V、辺数E(V,E 解法 単にdijkstraして、最短路が丁度Lになるような頂点をまず数える。その後各辺についてそのような位置を数える。0個あるか1個あるか2個あるかは場合分けで求められる。

問題概要 文字列SとT(長さアナグラムになっている部分文字列がいくつあるか求める問題。ただしSには任意の文字として扱える?が存在する。 解法 文字数をカウントしながらスライドしていくだけ。マッチしているかどうかの判定は愚直にO(|Σ|)かけてよい。