けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

CodeforcesDIV1-A

Codeforces Round #687 (Div. 1) A. Bouncing Ball (R1400)

個置きに累積和をとるの、3 ヶ月前の僕だったら思いつかなかったかもしれない。 問題へのリンク 問題概要 整数 が与えられる。また、長さ の 0 と 1 のみからなる文字列 が与えられる。文字列 に対して以下の操作を行うことができる。 文字列 中の文字 "0" …

Codeforces Round #681 (Div. 1) A. Extreme Subtraction (R1800)

区間加算操作は、「差分」をとる (いもす法) と、2 点加算になる! 問題へのリンク 問題概要 長さ の数列 が与えられる。これに対して以下の操作を好きな順序で好きな回数だけ行うことで、数列の値がすべて 0 になるようにすることが可能かどうか、判定せよ…

Codeforces Round #680 (Div. 1) A. Division (R1500)

面白かった 問題へのリンク 問題概要 正の整数 が与えられる。 の約数であって、 の倍数ではないような整数の最大値を求めよ。 (というデータセットが 個与えられる) 制約 考えたこと の約数をすべて列挙したのでは間に合わない。とりあえず 自身が で割り切…

Codeforces Round #201 (Div. 1) A. Alice and Bob (R1600)

シンプルで楽しい感じ 問題へのリンク 問題概要 要素からなる数列 がある (互いに相異なる)。交互に以下の操作を行う 数列から 2 つの整数を選んで、その差を数列の末尾に追加する ただし、「その差の値」がすでに数列中に含まれる場合は、この操作を行うこ…

Codeforces Round #625 (Div. 1) A. Journey Planning (R1400)

面白かった 問題へのリンク 問題概要 要素の数列 が与えられる。以下の条件を満たすような部分数列のうち、要素和の最大値を求めよ。 抜き出した数列のどの 2 項についても「値の差分」と「index の差分」とが等しい 制約 考えたこと たとえば の場合は、こ…

Codeforces Round #614 (Div. 1) A. NEKO's Maze Game (R1400)

いくらなんでも 2 分で解ける問題とは思えないのですが... 問題へのリンク 問題概要 2 × N のグリッドが与えられる。最初はグリッドのマスはすべて「通路」の状態であって、マス (1, 1) からマス (2, N) に到達することができる。以下の q 個のクエリに答え…

Codeforces Round #609 (Div. 1) A. Long Beautiful Integer (R1700)

こういうのは、いかにシンプルにできるか... 問題へのリンク 問題概要 桁の整数 が与えられる (文字列として)。leading zero はない。整数 が与えられる。 以上の整数 であって の 桁目と 桁目の値は等しい という条件を満たす最小値を求めよ。 制約 考えた…

Codeforces Round #511 (Div. 1) A - Enlarge GCD (R1800)

大昔 osa_k 法と呼ばれていたやつ。 問題へのリンク 問題概要 個の整数 が与えられ、 をこれらの最大公約数とする。 今、 個の整数から何個かを取り除いて、その最大公約数が より大きくなるようにしたい。取り除くべき最小個数を求めよ。ただし、どのように…

Codeforces Round #360 (Div. 1) A. NP-Hard Problem (R1500)

http://codeforces.com/contest/687/problem/A リハビリ第一弾 問題概要 無向グラフ (頂点数 n, 枝数 m) が与えられる。 このグラフの頂点集合を互いに disjoint な 2 つの集合 A, B に分割して、 A, B がともに vertex cover となっているようにせよ。 その…