atcoder.jp 概要 サイズNの木が与えられる。頂点に1~Nの番号が振られている。k=[1, N]として次の条件下で問題を解け。 頂点kに最初に赤色を塗る。次に塗ることができるのは、すでに塗った頂点に隣接する頂点、というルールのもとで色を塗るとき、何通りの塗…

codeforces.com 概要 円状にN個の数が並んでいて、時計回り順にt[i]である。次の条件を満たすように、これらの数に色を塗る。 隣り合った異なる値の数字どうしは、必ず異なる色が塗られている。 これを満たすように、最小限に色を使って塗ったときの一例を示…

codeforces.com 概要 長さが100万以下の文字列Sが1つあたえられる。構成されてる文字は、アルファベットの最初の20文字、すなわち'a' ~ 't'である。これの連続部分文字列を1つ選んで、1回だけ反転してよい。(しなくてもよい) 操作を終えた時、文字列Sの連続…

codeforces.com 概要 2つの長さNの文字列S, Tが与えられる。次の操作を任意回行えるとして、SとTを一致させることはできるか？ x 同時に反転させる。 例えば、S="sen", T="shojin"でx=3の連続部分列を次のように選べる。 S'="sen", T'="hoj" これを同時に入…

codeforces.com 概要 N人いて、それぞれのprogramming skill(以降PSと略す)はa_iである。N人でいくつかチームを組む。3人以上の人間で１つのチームを組むことができる。 チームの不満度を、チーム内の最大のPSを持つ人と、最小のPSを持つ人との差と定める。 …

atcoder.jp 概要 N個の区間が与えられる。これらの区間をグループ１、グループ２に分ける。それぞれのグループ内の区間の積集合の区間を計算し、その長さの和を最大化せよ。制約： 2

atcoder.jp 概要 長さNの数列A[]が与えられる。次のようにf(l, r)を定める。 l さて、1 制約： 1

codeforces.com 概要 n行m列の行列で、毎行のxorの結果はa[1~n]、毎列のxorの結果はb[1~m]として与えられる。これを満たす行列を存在するのならば、YESと答えて、1つ構築せよ。存在しないのならば、NOとだけ答えよ。制約： 1

codeforces.com 概要 0 数列の要素のXORがuと等しく、和がvに等しい

codeforces.com 概要 サイズNの木が与えられる。そのN-1本の辺に、それぞれ1つずつ、0~N-2の数字を重複なく割り当てていく。 頂点uと頂点vの間を通る単一のパス(木なので必ず存在する)上の辺に含まれる数の集合をSとする。Sに含まれない、最小の非負整数をME…

atcoder.jp 概要 サイズNの木が与えられ、頂点には１～Nまでの番号が振られてる。AliceとBobはAliceからゲームを始め、自分の手番が終わったら、相手に交代する。自分の手番では、次の操作を行う。 木の辺を1本取り除く。これによって、木は2つの部分木に分…

atcoder.jp 概要 ある文字列sが存在し、次の操作を考える。 sの空でない連続部分文字列を1つ選び、これをpとする。pのそれぞれの番目を'?'に置き換えるorそのままにする。 この操作で得られた3つの文字列、a, b, cが存在するとき、元のsの最短の長さを答えよ…

シリーズの構成 １．計算幾何の基本 ２．計算幾何のインフラ整備 ３．直線、線分の計算幾何 ←いまここ ４．円の計算幾何 ５．多角形の計算幾何 ６．AOJにある問題の解説

ei1333.hateblo.jpこれの例題1について、実装の備忘録。 dfs2の操作 今着目してるidx=子とその親をつなぐ辺は必ず使うとする。 すると、子からさらに孫方向での最長はdfs1で求まっている。欲しいのは親の子方向ではない向きの最大。これは下図のようになる。

シリーズの構成 １．計算幾何の基本 ２．計算幾何のインフラ整備 ←いまここ ３．直線、線分の計算幾何 ４．円の計算幾何 ５．多角形の計算幾何 ６．AOJにある問題の解説

シリーズの構成 １．計算幾何の基本 ←いまここ ２．計算幾何のインフラ整備 ３．直線、線分の計算幾何 ４．円の計算幾何 ５．多角形の計算幾何 ６．AOJにある問題の解説

www.acmicpc.net 概要 問題文はハングルオンリーなので、僕は機械翻訳で読んだ。グラムの重りそれぞれ1つずつある。あなたはこれらを一度に1つずつ、天秤に載せる。 天秤には左と右、両方の皿が存在する。載せる際、常に左の皿の重さが右の皿の重さ以上であ…

codeforces.com 概要 n人の参加者がいる2回コンテストが行われた。Senくんは1回目ではx位、2回目ではy位であった。総合順位は、2回のコンテストで取った順位の和を、全員分広義単調減少になるようにならべて、前からの順位とする。 ほかの参加者が1回目と2回…