Particle

競技プログラミングについての雑記

AGC 017 E Placing Squares

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

SRM 691 Div1 Medium Moneymanager

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

SRM 678 Div1 Medium TheEmpireStrikesBack

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

SRM 675 Div1 Medium LimitedMemorySeries1

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

SRM 675 Div1 Easy TreeAndPathLength3

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

AGC 005 E Sugigma: The Showdown

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

SRM 670 Div1 Medium Treestrat

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

SRM 670 Div1 Easy Bracket107

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

SRM 666 Div1 Medium SumOverPermutations

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

SRM 666 Div1 Easy WalkOverATree

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

SRM 661 Div1 Medium ColorfulLineGraphs

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

SRM 661 Div1 Easy MissingLCM

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…

SRM 660 Div1 Medium Privateparty

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

SRM 659 Div1 Medium CampLunch

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

SRM 657 Div1 Medium PolynomialGCD

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

SRM 654 Div1 Medium SuccessiveSubtraction2

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

SRM 652 Div1 Medium MaliciousPath

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

SRM 651 Div1 Medium FoxConnection3

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

SRM 650 Div1 Medium TheKingsRoadsDiv1

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

SRM 646 Div1 Medium TheGridDivOne

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

SRM 644 Div1 Medium MakingTournament

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

SRM 641 Div1 Medium ShufflingCardsDiv1

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

SRM 633 Div1 Medium DoubleTree

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

SRM 632 Div1 Medium CandyCupRunningCompetition

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

SRM 591 Div1 Med PyramidSequences

editorial にわかりやすく解法が纏まっているが、良問なので(できるだけ)自力で解く方が良さそう。 https://apps.topcoder.com/wiki/display/tc/SRM+591一応ヒントを出すと、整数のペアなので、それに対する典型手法を用いると見通しが良くなります。(editor…

SRM 590 Div1 Med XorCards

全く分からず、Editorial を見ながら通した。 xor なので、GF(2) での連立方程式の解の個数と対応している。解の個数は、2^(自由度) = 2^(n-rank) となっている。 rank を求める必要があり、難しい版の gauss-jordan を実装する必要がある。 #define N 60 ve…

ARC 009 C

C - 高橋君、24歳 問題概要 Nコのポストに手紙を届ける。Kコの手紙だけ正しくないポストに届き、すべてのポストに手紙が1コずつ届く。このとき、ポストと手紙の対応関係は mod 1777777777 (素数) で何通りか。(2 ヒント1 正しく届かない手紙・ポストの集合を…

CODE FESTIVAL 2016 Grand Final G

FESTIVA (256^0 の位) + (AVITSE+F) + (AVITSE+FF)+ (AVITSE+FFFF) +... +(AVITSE+FF...FF) (256^1 の位) + (AVITS + E) + ... (AVITS + EE...EE) (256^2 の位) ... + AA...AA (256^7 の位) のような文字列を考えると、256進数と対応する。 文字数は、高々 1…

ARC 073 F (嘘解法)

想定解法は segment tree だが、O(N^2) の DP を、隣の状態より strict に良い状態だけを残すような枝刈りしても通る。発見した中でのワーストケースでは、 与えられる点が、 200000, 1, 100000, 50000, 75000, ... のときに、保持する必要がある状態数が 20…

SRM 568 Div1Med EqualsSum

問題 一部の成分が指定されているN*N行列が与えられる. が一定で全ての成分が非負整数になるような割り当ての個数を1e+7で割った余りを求める. 解法 Editorial と違う解法で解いた.のうち、3つが既知のとき、残りの1つも一意に定まるので、その成分をあらか…