Learning Algorithms

アルゴリズムの勉強メモ

Codeforces

CF Croc Champ 2013 - Round 1 E. Copying Data(別解)

CF Croc Champ 2013 - Round 1 E. Copying Data(別解) Problem - E - Codeforces 解法 RBSTの実装法を学んだので、過去に解いた問題をRBSTで書いてみた。遅延セグ木でぐちゃぐちゃする問題が、思考停止ではい、の問題に変わった。解としては自明に正しいけ…

CF Round #304 Div.2 E. Soldier and Traveling

Codeforces Round #304 Div.2 E. Soldier and Traveling Problem - 546E - Codeforcesフローで解けることを知っていながら解いたが、解説無しでACしたのでよし。n個の街があって、m個の道によって連結である。各街には兵士がa[i]人かいて、彼らは今いる街に…

ICM Technex 2017 and Codeforces Round #400 (Div. 1 + Div. 2, combined) D. The Door Problem

ICM Technex 2017 and Codeforces Round #400 (Div. 1 + Div. 2, combined) D. The Door Problem Problem - D - Codeforces2SATの問題。ドアがn個あって、それぞれのドアはそれぞれちょうど2個の異なるスイッチによって操作でき、スイッチは動かすと状態が反…

CF Croc Champ 2013 - Round 1 E. Copying Data

Codeforces Croc Champ 2013 - Round 1 E. Copying Data Problem - E - Codeforces数列a[i]とb[i]が与えられる。これらの数列について、以下の2種類のクエリを実行していくという問題。 ・aのx番目からk個をbのy番目からk個にコピーする ・b[x]を出力する …

CF Round #271 Div.2 F. Ant colony

Codeforces Round #271 Div.2 F. Ant colony Problem - F - Codeforcesある数列に対するクエリに順に答えていく。クエリは[l, r]で与えられ、その区間の各数について、「その数が他のすべての数を割り切る」という条件を満たさないものの数を求める。総数はr…

CF Round #223 Div.1 C. Sereja and Brackets

Codeforces Round #223 Div.1 C. Sereja and Brackets Problem - D - Codeforces"("と")"のみからなる文字列が与えられる。クエリとしてある区間[l, r]が与えられるので、その区間の中で、"("と")"のペアがうまくつくれるようなものは何個あるかを答える問題…

CF Round #197 Div.2 D. Xenia and Bit Operations

Codeforces Round #197 Div.2 D. Xenia and Bit Operations Problem - D - Codeforces2のn乗個の数列に対して、 奇数番目の数とその次の数同士のorをとって数列をつくる 奇数番目の数とその次の数同士のxorをとって数列をつくる という操作を数が1個になるま…

CF Round #208 Div.2 E. Dima and Kicks

Codeforces Round #208 Div.2 E. Dima and KicksProblem - E - Codeforceskmjpさんの解法を丸パクリ参考にさせていただきました。ありがとうございます。 kmjp.hatenablog.jpとはいえ、自分で理解するためにコメントを書き、少し理解しやすいように書き換え…

CF Round #375 Div.2 E. One-Way Reform

Codeforces Round #375 Div.2 E問題Problem - E - Codeforces与えられた単純無向グラフに対して、入次数と出次数が等しい頂点の数が最大化されるように各辺に向きをつける、という問題。連結とは限らないことに注意する。辺の追加はできないので、そもそも次…

CF Round #296 Div.1 C. Data Center Drama

Codeforces Round #296 Div.1 C. Data Center Dramaオイラー路の問題をまとめて解いている。 Problem - C - Codeforcesn頂点、m辺の無向グラフが与えられる。各頂点について、その頂点から出ていく本数とその頂点に入ってくる本数がともに偶数になるように、…

CF Round #288 Div.2 D. Tanya and Password

Codeforces Round #288 Div.2 D. Tanya and PasswordProblem - D - Codeforces長さ3の文字列n個が与えられる。それらすべてが、長さがn + 2ある適当な文字列の3-gramとなっているならば、その文字列を出力する。解法自体は容易である。すなわち、xyzという文…