Particle

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

2018-02-10から1日間の記事一覧

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 であるようなすべての文字列) …