競プロ記録

問題を解いた際に自分の復習用として使ってます

2017-10-14から1日間の記事一覧

AGC014 B問題 Unplanned Queries

問題 agc014.contest.atcoder.jp 解説 まずこの問題では木を根付き木として考えます。各辺は偶数回 +1 されていれば良い、つまり各辺の値が0, 2, 4, ...となっていれば良いのでmod2で考えることができます。そして根をrとすると, +1する辺を(a, b)ならば(a,r…

AGC013 B問題 Hamiltonish Path

問題 agc013.contest.atcoder.jp 解説 まず適当に頂点uを選択します。頂点uから移動可能な頂点vを探して頂点vから今まで訪れた頂点でない頂点xを選択し頂点xから移動可能な今まで訪れた頂点でない頂点yを選択し、、、 このような操作を繰り返していくと移動…

ARC083 D問題 Restoring Road Network

問題 AtCoder Regular Contest 083 - AtCoder 解説 入力例のケースで考えてみます。 3 0 1 3 1 0 1 3 1 0 この場合三角形の頂点に3つの街があると仮定し、辺の付近に都市間の距離を書いた、図は 3 ①ーー③ 1| / ②/ 1 となります。 しかし都市間の距離を長…

AGC002 C問題 Knot Puzzle

問題 agc002.contest.atcoder.jp 解説 この問題は結び目に注目して考察すれば解くことができます。 最後にほどくのは必ず左右のロープの長さの和がL以上の結び目でなければなりません。したがってそのような結び目が存在しなければほどくことはできません。 …

AGC001 B問題 Mysterious Light

問題 agc001.contest.atcoder.jp 解説 解法の方針はユークリッドの互除法です。 なぜこの問題を見てユークリッドの互除法が思いつくのかをまず解説していきます。 ユークリッドの互除法を幾何的に説明したサイトがあったので紹介します。 math-arithmetic.bl…