E - Placing SquaresN を増やしたときの差分について観察するとうまく解けるようになる。 M = 0 の場合でも難しいので、まずは M = 0 の場合を考える。 右端の正方形が k*k で、それ以外の正方形の面積の積(=重み)が a であるような状況を考える。 右端に辺…

X = 0 であるときは、a/b が大きい方が前に来るようにすればよい。 前半・後半に分ける集合を固定したときも、それぞれの集合内では、a/b が大きい方が前に来るのが最適となっている。 あとは、前半・後半にどう分けるかが問題となるのだが、a/b でソートし…

まず、LIS になるように余分な惑星を取り除く (x1 すると、T を固定したときに greedy にミサイルを打つ回数の最小値が求められるようになるので、二分探索する。 class TheEmpireStrikesBack { public: int find(int AX, int BX, int CX, int AY, int BY, i…

長さ n ( 1 MB 以下、10 sec 以下でクエリの答えの総和を求める問題。問題文にも書かれているように、メモリが足りないので数列を保持することはできない。 数列の要素の値の最大値は 1e9+7 であり、sqrt(1e9+7) 個の int 型配列を持つことができることに着…

この回は個人的に Easy も Med も面白い問題だと思った。s が小さいとき (497 以下のとき) は、パスグラフでも 500 頂点を超えないようにできる。 そうでないときは、1 頂点 u の周りに 101 個頂点をくっつけた木を考えて、その周りに 頂点を付け足していく…

問題: E - Sugigma: The Showdownまず、しぐま君 (追いかけられる方のプレイヤー) の必勝条件について考える。 すぎむ君 (追いかける方のプレイヤー) の木において、距離が 3 以上離れた頂点を行き来できるような頂点に先に到達し、直後のターンに負けないこ…

まず、木なので高々 N ステップでゲームが終了する。 A のトークンは複数あるが、すべて独立に計算できるので、それぞれ別に計算する。 A のトークンが 1 つの場合は、BFS を行うことで、解が計算できる。 #define N 55 int d[N][N]; class Treestrat { publ…

s に含まれる 1 文字を別な場所に動かすと、LCS(s, t) が |s| または、|s|-1 になるようにできる。 s >= 4 であるので、必ずLCS(s, t) が s -1 かつ、正しくカッコが対応している t が存在する。 t の候補 (LCS(s, t) が |s|-1 であるようなすべての文字列) …

左端のビンから考え、DP をする。 dp[i: i 番目のビン][j: i 番目のビンは、左の i 個のビンの中で j 番目に使われる][k: (i+1)番目のビンが i 番目のビンよりあとなら 1、そうでないなら 0] ::= 条件を満たす状態数 とし、累積和を計算しながら DP を計算す…

頂点 0 まで戻ってくる場合の問題について考える。 すると、無駄な探索をしなければ、L/2+1 個の頂点に到達することができる。 頂点 0 まで戻る必要が無い場合には、深さが最大となる頂点までの距離の分 (すなわち深さの最大値) だけ移動距離を増やせるため…

求める値は、簡単な考察で分かる。(各 i に対して、どこに辺を張るかを考えると、辺を張るときは K-1 倍、張らないとき K 倍となる) M が 10^6 以下と小さいので、1 周期分計算し、周期の回数(N/M回)だけかけ、周期からはみ出す分(N%M の部分)を掛け合わせれ…

lcm は、各素数ごとに max を取るのと同じなので、各素数ごとに独立に M の lower bound を計算できる。 class MissingLCM { public: bool isPrime(ll x){ if(x<=1) return false; for(ll i = 2; i*i <= x; i++) if(x%i==0) return false; return true; } in…

各頂点に対して独立に期待値を求める。 有向グラフにして考える。 開始頂点を w とする。 頂点 u から v に辺が張られているとする。u が先に招待される場合は、自明に u は招待される。 v が先に招待される場合は、v の先の頂点まで見る必要があるので DFS …

想定解とはおそらく少し違う方法で解いた (定数倍高速化を頑張って TLE ギリギリなので、想定解が思いつくならそちらの方がよい。)まず、i 日目で隣り合う 2 人がどうペアになるか全列挙し、高速ゼータ変換を行う。すると、i 日目の食事で、ペアにできない人…

各素数ごとに独立になっているので、それぞれ解いて解を掛け合わせればよい。 素数 p の出現回数が一番多くなる場所を決めると、全体で何回 p が出現するかを O(NlogN/p) 程度で計算でき、場所の個数は、Nなので、各素数ごとに、O(N^2logN/p) で計算できる。…

区間を 2 つ選んで符号を反転させることができるので、区間和の最小値が計算できれば、あとは簡単に計算できる。 これは、O(N) でやってよいので、配列が更新される度に最初から計算し直せば良い。(解いているときは何も考えずに、StarrySky Tree を貼ってし…

K = 0 のときは、 dijkstra で解ける。 頂点を *1 と拡張すると、K>0 の場合も dijkstra を多少書き換えるだけで解くことができる。 辺の長さが少し特殊なので、k=0..K として順番に dijkstra を行うことで効率よく最短路が求まる。 計算量は、O(K(N+M)logN)…

2次元グリッド上にきつねがN匹いる (N すべてのきつねが辺で連結になるように動かすとき、最小で何ステップでできるか？(きつねは重なることは出来ない)まず、1次元の場合には、中央値に寄せるのが一番効率がよい。 (N が偶数のときは、真ん中の2つの値の平…

グラフ G が与えられる。G が深さ9以下の完全二分木に3本の余計な辺を追加したグラフであるかを判定する問題である。色々な解法が考えられるが、根の候補を小さくしてから、それが正しいか判定するという方針で解いた。 根の候補を小さくする部分は、 全点間…

制約を見ると明らかに座標圧縮なので、座標圧縮して dijkstra 等のアルゴリズムで最短経路を求めると解ける。出題された当時は地力 (実装力) が足りず解けなかったが、今見ると、特に難しいところのない素直な問題に見える。 #define N 150 ll d[N][N]; vect…

実験すると、K=1 のときは、フィボナッチ数列になる。 K>1 のときは、2^K +1 項間漸化式になりそうなので、最初の 2^K +1 項あたりまでを愚直に計算すると、行列を復元することができる。というのを実装したら通った。直感的には正しいことが分かるが、ちゃ…

最終状態から、初期状態に戻していく方針で考察していく。まず、0回のシャッフルで良い場合は 0 を返す。 それ以外の場合は、 0-origin で偶数番目のカードについて、初期状態で先頭 N 枚に来るカード (すなわち N 以下の数が書かれたのカード) の枚数を X …

まず根を 1 つ固定して考える。すると、頂点 x を用いるならば、x の親の頂点 y を用いるという制約がある上でできるだけスコアが大きくなるように頂点集合を選ぶ問題になる。 これは典型最小カット問題 (燃やす埋める問題) なので、最大フローを計算するこ…

辺の容量にものすごく差がある場合の max flow を解く。 辺 i の容量は、3^i で、コストが大きい辺から greedy に使っていけばよい。(容量の小さい辺を通るフローのために容量を残しても解は大きくならないので) 容量が大きい方から辺を追加していき、その辺…