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回…

leetcode.com 概要 あなたはN種類の括弧を持っていて、互いに区別可能である。あなたはこれらを一列に並べる。すべての括弧に関しては、閉じる括弧'）'よりも前に開く括弧'（'が先に来る必要がある。 この並び方は何通り存在してるのか？で割ったあまりで答…

つぎのような問題を考える。 サイズNの無向木が与えられる。木の頂点に色を塗っていき、隣あった頂点には同じ色を塗ってはならない。 木をちょうどK色で塗るとき、何通りの塗り分け方があるか？で割ったあまりを答えよ。制約： 2

atcoder.jp 概要 n個の1~nまで番号がついてる部屋があって、それぞれ1人ずついる。ある部屋にいる一人が別の部屋へと行く行動をアクションと呼ぶ。 アクションがちょうどk回行われたときに、それぞれの部屋にいる人の数の組み合わせの数を10^9+7で割ったあま…

このサイトが詳しい。drken1215.hatenablog.com次のような問題を考える。 文字列S(|S| a, b, rが与えられて、S[a, a + r], S[b, b + r]が同じ連続部分文字列かどうかを判定せよ。 いい感じに前処理をして、クエリ1回ごとにかかる計算量O(1)とかO(log N)でな…

codeforces.com 概要 H*Wのグリッドを与える。そのグリッドには"."と"#"の2つがある。あなたは1*2のサイズのドミノを持っていて、縦向きか横向きのいずれかの向きで、グリッドの2つ連続で"."になってる場所における。 次のq個のこqueryに答えよ。 グリッドを…

atcoder.jp 概要 長さNの数列Aが与えられ、それらの中の２つの要素の組はN*(N-1)/2個あるが、それら積のうち、小さい順にK番にあたる値を求めよ。制約： 1 -10^9

codeforces.com 概要 長さNの数列Aが与えられる。あなたは次の操作を何度してもよい。 Aの連続部分列を1つ選び、その連続部分列の亘る区間をすべてその連続部分列の平均とする。 この操作を繰り返して、Aを辞書順に最小にするとき、Aはどうなるか？制約：1 1…

atcoder.jp 概要 f(x, y) := 1回の行動でx+1 or y+1しかできないときに、(0, 0)から(x, y)まで行く場合の数 と定める。r1, c1, r2, c2が与えられる。 r1 制約： 1

Attachments - 2019-2020 ICPC Asia Taipei-Hsinchu Regional Contest - Codeforces 概要 N点与えられる。そのうちの適切な順番で4つの点を選び、作れる最大の四角形の面積を求めよ。制約： 4

atcoder.jp 概要 m段階の明るさを調節できるランプとリモコンがある。1回リモコンの「進む」ボタンを押すと、明るさが1段階上昇、一番上のレベルmの場合はレベル1に戻る。 もう1つ、「ショートカット」ボタンがあり、これは1回押すと、事前に決めたX段階の明…

codeforces.com 概要 N頂点M辺の無向グラフが与えられる。次の条件を満たす全域木を1つ出力せよ。 全域木を構成する辺のうち、頂点1と連結してる辺はD本である。制約： 1 1 ACするまで 1. ひとまず適当にグラフを書いてみると、頂点1から出てるいくつかの辺…

atcoder.jp 概要 サイズNの木が与えられる。それぞれの辺に黒、白の二色のいずれかで塗る。 次のM個の条件をすべて満たす塗り方の場合の数を求めよ。 ・頂点u~頂点vを結ぶ経路の上に、必ず1つ以上の白く塗られた辺が存在する。制約: 1 min(20, (N-1)*N/2) AC…

新ABCになって、6問制になってから、2020/1/6現在まで、Z-algorithmは二回(500, 600)出題されてます。これからも継続して出そうな「文字列照合」で強力なツールとなるZ-algorithmですが、既存資料たちは非常によく説明されていますが、どこか筆足らずのよう…

codeforces.com 概要 Xが与えられる。lcm(a, b)=Xを満たすような(a, b)の組のうち、max(a, b)を最小化せよ。制約： 1

atcoder.jp 概要 長さNの相異なるバイナリ列、S, Tを考える。C[]という長さNの配列が与えられる。Sのi(1-idx)桁目を変更するとき、C[i]*(変更直前のS xor Tの立ってるbit数)だけのコストがかかる。次のようにf(S, T)を定める。 SをTと一致させるときにかかる…