AtCoder Regular Contest

ARC087 F - Squirrel Migration

これ800点ってマジ?ムズすぎてハゲた 問題 n頂点の木があり、全ての頂点にリスがいる 長さnの順列pを決め、頂点iのリスを頂点p[i]に移動させる 各リスの移動距離の総和が最大になるようなpは何通りあるか2 解法 x-yを繋ぐ辺を通るリスの数の最大値は、xyそ…

ARC081 F - Flip and Rectangles

問題 h*wのマス目があり、各マスの色は黒か白である 「ある行[列]を選び、その行[列]の全てのマスの色を反転する」という操作を任意の回数行える 黒いマスのみを内側に含む長方形の面積の最大値を求めよ2 解法 タテかヨコの長さが1の長方形は明らかに自由に…

ARC064 F - Rotated Palindromes

creep06.hatenablog.com これにだいぶ似てる 問題 以下の条件を全て満たす数列aを用意する 1) 長さn 2) 各要素は1以上k以下の整数 3) 回文(∴ aを逆順にした数列はaと一致する) その後aを好きな回数rotateする 最終的なaとしてあり得るものは何通りか1 1 解法…

ARC101 E - Ribbons on Tree

問題 n(:偶数)頂点の木が与えられる これらの頂点を端点を共有しないペアn/2組に分け、各ペアの2頂点間にリボンを張る どの辺にも少なくとも1本のリボンが張られているようなペアの分け方は何通りあるか2 解法 f(S): Sのどの辺にもリボンが張られていないよ…

ARC096 E - Everything on It

春に解説pdfを見ても全く意味がわからなくてずっと放置してて、さっき解説放送見たらやっと理解できた 700点とかの問題と比べると恐ろしいほどむずいけど勉強になる問題だった 問題 あるラーメン屋はn種類のトッピングを提供している 各トッピングは乗せるか…

ARC102 E - Stop. Otherwise...

問題 1〜kが等確率で出るk面サイコロをn個振る 2 ただしサイコロ同士は区別しない1 2 解法 どの2つの出目の和もtにならない組の個数を求めたい これは a+b = t となる各(a,b)について、どちらか一方が現れない or 両方とも現れなければいい (ただしtが偶数の…

ARC103 D - Robot Arms

問題(言い換え) n個の点が与えられ、i個目の座標は(x[i],y[i])である 事前に自然数mとm個の数値dを自由に決めることができる その後原点からスタートし、以下の操作をm回繰り返す i番目の操作: 上下左右どれかの方向にd[i]だけ移動する 各操作の方向は自由に…

ARC103 E - Tr/ee

問題 長さnの文字列sが与えられる 以下の条件を満たすn頂点の木が存在するか判定し、存在する場合は具体的に1つ構築せよ(条件) 1-basedで、 s[i]= '1' のとき) 木からある辺を1つ取り除くことでサイズiの連結成分が作れる s[i]= '0' のとき) 木からどのよう…

ARC102 D - All Your Paths are Different Lengths

問題 以下の条件を満たす有向グラフを1つ作れ ・頂点数20以下で、全ての頂点には1〜Nの相異なる番号が付けられている ・辺数60以下で、全ての辺には0〜10^6の整数の長さが付けられている ・全ての辺は番号の小さい方の頂点から大きい方の頂点に向かって向き…

ARC093 E - Bichrome Spanning Tree

問題 n頂点m辺の重み付き無向グラフと整数xが与えられる このグラフの各辺を白or黒で塗る方法で、以下の条件を満たすものの個数を求める 条件: 白く塗られた辺と黒く塗られた辺をともに含む全域木が存在し、そのような全域木のうち最も重みが小さいものの重…

ARC101 D - Median of Medians

問題 長さnの数列aが与えられる この数列の全ての連続する部分列の中央値を並べ、新しい数列mを作る 数列mの中央値を求める1 1 解法 (思考) 各要素が中央値になるような区間が何個あるかわかると嬉しい →値aが中央値になるような区間っていうのは、(区間に含…

ARC099 E - Independence

問題 n個の街とm本の無向辺があり、これらの街を2つの州に分けたい ただし同じ州内のどの2つの都市も直接道で結ばれているように分けないといけない そういうふうに分けたときの、"両端の都市が同じ州内に属しているような道"の本数の最小値を求める 解法 条…

ARC098 E - Range Minimum Queries

問題 長さnの数列に対し「長さkの区間を選び、その中の最小の要素を取り除く」という操作をq回行う 取り除いた要素の最大値をx、最小値をyとしてx-yの最小値を求める 解法 最小値を決め打ちして最大値を最小化する方針 最小値をyにするには、y未満の数字を含…

ARC097 E - Sorted and Sorted

問題 1〜nが重複なく書かれた白/黒のボールが各n個ずつ計2n個一列に並べられている 「隣り合う2つのボールをswapする」という操作を繰り返して、「任意のペアi,j (i<j)について、iと書かれた黒/白のボールがjと書かれた同色のボールより左にある」という状…

ARC095 E - Symmetric Grid

問題 H行W列のマス目の各マスに英小文字が書かれている 任意の異なる2行/列をswapするという操作を何度でも行えるとき、マス目が点対称になるようにできるか判定 H,W 解法 行のswapと列のswapは可換 行のswapの仕方が決まっているとき、列をうまくswapして条…