読者です 読者をやめる 読者になる 読者になる

Manthan, Codefest 16 C: Spy Syndrome 2

問題 Problem - C - Codeforces 解法 文字列の一致判定はローリングハッシュにしてもらって、メモ化再帰で計算量を減らす。 コード #include <bits/stdc++.h> using namespace std; typedef long long ll; struct ToLower { char operator()(char c) { return tolower(c); }</bits/stdc++.h>…

Codeforces Round #339 Div2 C: Peter and Snow Blower

問題 codeforces.com 解法 内側の円は中心の点と最も近い線分との距離になる。外側の円は中心から最も遠い頂点との距離になる。 点と線分の距離を求めるライブラリ double distanceVertex(pair<double, double> p1, pair<double, double> p2) { double dx = p1.first - p2.first; double dy =</double,></double,>…

Codeforces Good Bye 2015 D: New Year and Ancient Prophecy

kenkoooo.hatenablog.comrng_58 さんのコードを参考にした。 よく考えたら、ハッシュなんか使わなくても解けるんだよなあ #include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <algorithm> #include <cmath> #include <string> #include <vector> #include <list> #include <queue> #include <stack> #incl</stack></queue></list></vector></string></cmath></algorithm></iomanip></fstream></sstream></iostream></cstdio>…

Codeforces Good Bye 2015 D: New Year and Ancient Prophecy

問題 codeforces.com 解法 Rolling-Hashing で文字列の大小関係をO(log N)で求めようのコーナー kenkoooo.hatenablog.com コード #include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <algorithm> #include <cmath> #include <string> #include <vector> #include <list> #include <queue> #inc…</queue></list></vector></string></cmath></algorithm></iomanip></fstream></sstream></iostream></cstdio>

Codeforces Good Bye 2015 C: New Year and Domino

問題 http://codeforces.com/contest/611/problem/Ccodeforces.com 解法 2次元の累積和。kenkoooo.hatenablog.com コード #include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <algorithm> #include <cmath> #include <string> #include <vector> #include <list> #include </list></vector></string></cmath></algorithm></iomanip></fstream></sstream></iostream></cstdio>

Codeforces Round #337 Div2 D: Vika and Segments

問題 codeforces.com 解法 y座標について Fenwick Tree を作りたいので、y 座標を座標圧縮する。 xを小さい方から順に見ていく。 xで始まる水平方向の区間があれば、それをBITに保存する。 x上にある垂直方向の区間を全て足し合わせる。ただし、水平方向と重…

Codeforces Round #336 Div2 D: Zuma

問題 codeforces.com 解法 区間DP。@mayoko_ 申し訳ねぇ申し訳ねぇ… [l,r]で回文を挿入しまくって文字列を作りたいです. a[l]==a[i]のところがあったときそこを使うことにしたとき,[l+1,i-1]と[i+1,r]について考えればOKです 回文が始まるのは長さ1か長さ2…

Codeforces Round #323 Div2 D: Once Again...

問題 codeforces.com 解法 増加列に含まれる値の種類は多くてN種類なので、T>Nならば、最も多い種類の点の数を (T-N) 回足せば良い。 コード import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.Scanner…

Codeforces Round #323 Div2 C: GCD Table

問題 codeforces.com 解法 テーブル上の既に明らかになっているGCDを取り除いた時に最大の数は、必ず元の配列に含まれているはずである。 コード import java.util.ArrayList; import java.util.Map; import java.util.Scanner; import java.util.TreeMap; p…

Codeforces Round #319 Div1 C: Points on Plane

問題 codeforces.com 解法 縦,横1000の長方形に切る.長方形内で点をyの値でソートする.ひとつの長方形内では,そこに含まれる点の数をPとすると,x軸方向に1000*P,y軸方向にの長さが最大で必要になる.長方形間ではx軸方向に最大で2000必要になり,これ…

Codeforces Round #319 Div1 B: Invariance of Tree

問題 codeforces.com 解法 codeforces.com1つだけでループしている頂点があれば,その頂点から他の頂点に辺を出せば良い.2つだけでループしている頂点があれば,その2点を中心にし,そこから他の頂点に辺を出していく.この2点間の間は1本の辺だけで条件を…

Codeforces Round #318 Div1 C: Bear and Drawing

問題 Problem - C - Codeforcescodeforces.com 解法 頂点iに接続している頂点vについて考える。 vが葉に接続している一本道の途中にある頂点であれば、葉の一部と考えれば良い。 i以外にvが持っている葉が2枚以下であれば、vはiの対岸の行に収めることができ…

Codeforces Round #317 Div1 B: Minimization

問題 Problem - B - Codeforcescodeforces.com 解法 「N人をK個のグループに分ける。グループの人数はN/KまたはN/K+1でなければならない。グループの人間を身長順にソートした時の隣接する2人の身長の差の合計を、グループのコストとする。グループのコスト…

Codeforces Round #317 Div1 A: Lengthening Sticks

問題 Problem - A - Codeforcescodeforces.com 解法 合計lだけ長くした時、辺の組み合わせは全部で(l+2)*(l+1)/2通りになる。このうちhalf=(a+b+c+l-1)/2とした時に、辺の長さがhalfを超える場合三角形にならないので引けばいい。 コード import java.util.S…

Codeforces Round #316 Div2 D: Tree Requests

問題 Problem - D - Codeforcescodeforces.com 解法 Codeforces Round #316 (Div. 2) D. Tree Requests - mayoko’s diarymayokoex.hatenablog.com コード import java.io.IOException; import java.io.InputStream; import java.util.ArrayDeque; import jav…

Codeforces Round #316 Div2 E: Pig and Palindromes

問題 Problem - E - Codeforcescodeforces.com 解法 dp[h][w][rh][rw]:=(h,w)を通り、(rh,rw)を通る経路が回文である経路数を持たせたいがメモリが足りない。しかし、(1,1)と(h,w)、(H,W)と(rh,rw)の距離を両方mとして、mを少しずつ小さくしていくようにすれ…

Codeforces Round #315 Div1 A: Primes or Palindromes?

解法 2000000以下の素数と回文を全列挙して、全てのnについて条件を満たすかどうかしゃくとり法で調べれば良い。 コード import java.util.ArrayList; import java.util.BitSet; import java.util.Collections; import java.util.Scanner; public class Main…

Codeforces Round #Pi Div2 C: Geometric Progression

問題 Problem - C - Codeforcescodeforces.com 解法 について考える。 の時、自分より前に出てきたbの数を記録しておく。 の時、自分より前に出てきたに記録されているbの数の和を記録しておく。 の時、それまでに出てきたbの数に1加える。 コード import ja…

Codeforces Round #Pi Div2 D: One-Dimensional Battle Ships

問題 Problem - D - Codeforcescodeforces.com 解法 残ったボードに存在しうる船の数を常に保持するようにする。 コード import java.util.Scanner; import java.util.TreeMap; public class Main { public void solve() { Scanner scanner = new Scanner(Sy…

Codeforces Round #312 Div2 D: Guess Your Way Out! II

問題 Problem - D - Codeforcescodeforces.com 解法 含む範囲のクエリは、重なっている部分だけを取り出していけば、必ず1つだけの範囲になるはず。離れた2つの範囲が出てきた場合、題意に合わないのでcheatである。含まない範囲のクエリは、和集合を取って…

Codeforces Round #312 Div2 E: A Simple Task

問題 Problem - E - Codeforcescodeforces.com 解法 [i文字目から][jの文字が][k個連続している]という同じ文字列が連続している区間の情報を保持しておく。(start, end, d)というクエリに対して、startからendの中に入っている文字列の数を種類ごとに集計し…

Codeforces Round #313 Div1 C: Gerald and Giant Chess

問題 Problem - C - Codeforcescodeforces.com 解法 包除原理を使う。各障害物のセルとゴールのセルに、 (スタートからの経路数)-(障害物を1つ通る経路数)+(障害物を2つ通る経路数)-(障害物を3つ通る経路数)-...を記録するようにすれば良い。 コード import …

Codeforces Round #312 Div2 C: Amr and Chemistry

問題 Problem - C - Codeforcescodeforces.com 解法 最終的な値が入力の最大値を超えることはない。 aとbが一致するまで大きい方を1/2ずつしていった時の最終的な値をM(a,b)とすると、最終的な値はM(a0,a1,a2,...)を2の累乗倍したものである。 コード import…

Codeforces Round #296 Div2 C: Glass Carving

問題 Problem - C - Codeforcescodeforces.com 解法 クエリ処理のたびに、最大の高さと、最大の幅を知りたい。 切られるたびに1つ辺が減り、2つ新しい辺が出来る。 以下、縦に切った場合を考える。 w0の長さの辺が切られ、新たにw1とw2の長さの辺が出来ると…

Codeforces Round #311 Div2 E: Ann and Half-Palindrome

問題 Problem - E - Codeforcescodeforces.com 解法 Codeforces #311 Div2 E. Ann and Half-Palindrome - kmjp's blogkmjp.hatenablog.jp半回文の文字列の洗い出しと、K番目の文字列の探索は、各で求めることができるので時間内に終わる。 しかし、kmjpさん…

Codeforces Round #311 Div2 C: Arthur and Table

問題 Problem - C - Codeforcescodeforces.com 解法 テーブル内で最大になる高さを総当たりする。最大の長さLの脚がM本存在する時、Lより長い脚は全て切り、Lより短い脚については、合計M-1本以下になるようにエネルギーの小さい方から切る。 コード import …

Codeforces Round #307 Div2 E: GukiZ and GukiZiana

問題 Problem - E - Codeforcescodeforces.com 解法 平方分割を用いる。与えられたN個の数字をの配列に入れる。個で1ブロックと考え、ブロック全体がカバーされている加算操作に対しては、別の場所に記録しておく。 import java.io.IOException; import java…

Codeforces Round #310 Div1 C: Case of Chocolate

問題 Problem - C - Codeforcescodeforces.com 解法 各(x,y,UL)クエリに対して、一番近い右のクエリを見れば欲しい情報が書いてあるようにしておく。 コード import java.util.Scanner; import java.util.TreeMap; public class Main { public void solve() …

Codeforces Round #309 Div1 C: Love Triangles

問題 Problem - E - Codeforcescodeforces.com 解法 Codeforces Round #309 (Div. 1) C. Love Triangles - mayoko’s diarymayokoex.hatenablog.com問題分が分かりにくいが、「ある2人が同じ人を好き、あるいは嫌いな場合、その2人は愛しあわなければならない…

Codeforces Round #310 Div1 B: Case of Fugitive

問題 Problem - B - Codeforcescodeforces.com 解法 島とに対して架けられる橋の長さaは を満たさなければならない。, とおいて、shortDでソートしておく。ある距離lengthについて小さい方から見ていく。shortD=lengthとなる島間距離があったら取り出して、l…

Codeforces Round #309 Div2 C: Kyoya and Colored Balls

問題 Problem - C - Codeforcescodeforces.com 解法 最大の数字kについて考える。kがn個あり、それ以外の数字がm個あるとすると、kのうち1つは一番後ろでなければならない。残りのn-1個の取りうる場所の組み合わせは、k以外の数字の区別をつけなければ通りに…

Codeforces Round #309 Div2 D: Kyoya and Permutation

問題 Problem - D - Codeforcescodeforces.com 解法 Codeforces Round #309 (Div. 1) B. Kyoya and Permutation - mayoko’s diarymayokoex.hatenablog.com コード import java.util.ArrayList; import java.util.Scanner; public class Main { private long[…

Codeforces Round #307 Div2 D: GukiZ and Binary Operations

問題 Problem - D - Codeforcescodeforces.com 解法 kをビットに直して考える。各aのi番目のビットの組み合わせは通りあるが、kのi番目のビットが0になるためには、そのうち1が連続して存在するものを取り除かなければならない。 例えば、n=3のとき、以下の5…

Codeforces Round #308 Div2 D: Vanya and Triangles

問題 Problem - D - Codeforcescodeforces.com 解法 全ての組み合わせを列挙すると通りあるため、間に合わない(と思われていたがC++なら間に合う)。3点が同一直線上にあるパターンと、3点のうち2点以上が重なっているパターンを除けば良い。 まず、点iに注…

Codeforces Round #308 Div2 C: Vanya and Scales

問題 Problem - C - Codeforcescodeforces.com 解法 天秤が釣り合う時、となる。この時、と書ける。 mをwで割り切れる限り割り続けると、またはというように、あまり1か-1になる。つまりmがwで割り切れる時は割り続け、割り切れなくなったら1を足すか引くか…

Codeforces Round #308 Div2 E: Vanya and Brackets

問題 Problem - E - Codeforcescodeforces.com 解法 しゃくとり法。 コード import java.util.Scanner; public class Main { public void solve() { Scanner sc = new Scanner(System.in); String input = sc.next(); sc.close(); int N = input.length(); i…

Codeforces Round #302 Div2 E: Remembering Strings

問題 Problem - E - Codeforcescodeforces.com 解法 Editorial Codeforces Round #302 - Codeforcescodeforces.comstrings[i][j]に注目した時に、2つの操作を考える。 strings[i][j]だけを変える。この時はcost[i][j]がかかり、少なくともstrings[i]が覚えや…

Codeforces Round #302 Div2 D: Destroying Roads

問題 Problem - D - Codeforcescodeforces.com 解法 Codeforces #302 Div1 B. Destroying Roads - kmjp's blogkmjp.hatenablog.jpまず二点間の最小距離を出しておく。nの最大値が3000なのでワーシャルフロイトをするとだから終わらない。辺の数の最大値が300…

Codeforces Round #307 Div2 C: GukiZ hates Boxes

問題 Problem - C - Codeforcescodeforces.com 解法 Codeforces #307 (Div. 2) Editorial - Codeforcescodeforces.com二分探索で間に合う最小の時間を探す。適当に決めた時間に対して、以下の操作を繰り返す。 残ってる人の中から1人を、残っている一番遠い…

Codeforces Round #302 Div2 C: Writing Code(動的計画法)

問題 Problem - C - Codeforcescodeforces.com 解法 動的計画法で dp[i][j][k]:=i人目まででj行書いてバグがk個ある組み合わせ を求める。ある行fまで終わっている時にfからf+1、f+2、...への遷移を考えると以下のような4重ループになる。 // dp[i][j][k]:=i…

Codeforces Round #299 Div2 E: Tavas and Pashmaks(凸包)

問題 Problem - E - Codeforcescodeforces.com 解法 Codeforces #299 Div1 C. Tavas and Pashmaks - mayoko’s diarymayokoex.hatenablog.com コード import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.…

Codeforces Round #304 Div2 D: Soldier and Number Game(素因数分解・セグメント木)

問題 Problem - D - Codeforcescodeforces.com 解法 スコアを上げるためにはできるだけ多く割り算したいので、プレイヤーはnに対して素因数分解する。なので、aの素因数の数をとすると、求める数はである。 クエリのたびに計算すると時間がかかりすぎるので…

Codeforces Round #304 Div2 E: Soldier and Traveling(最大フロー問題)

問題 Problem - E - Codeforcescodeforces.com 解法 最大フローやるだけ。 コード import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Main { private final int MAX = 10000; public void solve() { Scanner sc…

Codeforces Round #305 Div2 E: Mike and Foam(素因数分解・包除原理)

問題 Problem - E - Codeforcescodeforces.com 解法 Codeforces Round #305 (Div. 1) C. Mike and Foam - mayoko’s diarymayokoex.hatenablog.com例えば、棚に(1, 2, 3, 4, 6)が入っていて、6を入れる場合を考える。 1, 2, 3, 4, 6と6は公約数として1をもつ…

Codeforces Round #305 Div2 D: Mike and Feet (スタック)

問題 Problem - D - Codeforcescodeforces.com 解法 各人iが最弱になるチームを考え、そのチームには最大で何人まで入れることが出来るかを考える。そのためには、iより小さい人がiより右とiより左のどこにいるかを調べれば良い。類題:D: 登山家 - CODE FEST…

Codeforces Round #306 Div2 E: Brackets in Implications (貪欲)

問題 Problem - E - Codeforcescodeforces.com 解法 ...->1->0の形にならないといけないので、最後の数字が0でなければNO x->1=1なので最後から2番めの数字が1ならばYES ...->0->0 となっている時、すなわち、最後の2つが0の時を考える 最後の2つ以外に0が1…

Codeforces Round #306 Div2 D: Regular Bridge

問題 Problem - D - Codeforces各頂点からk本ずつ辺が出ているような無向グラフで、橋が存在するものは存在するか。 解法 k=1の時はサンプルをコピペする。橋を取り除いた時、残ったグラフの片方は次数がk-1の頂点が1つ存在し、残りの頂点の次数はkである。…

Codeforces Round #305 Div2 C: Mike and Frog

問題 Problem - C - Codeforcescodeforces.com 解法 h[i]->a[i]になるまでの時間first[i]とa[i]->a[i]の時間cycle[i]を取っておく。求める時間secはsec=first[i]+cycle[i]*zのような形になるので、ゴリ押しでループさせていけば良い。(それでも間に合う)se…

Codeforces Round #299 Div2 E: Tavas and Malekas (Z Algorithm)

問題 Problem - D - Codeforcescodeforces.com 解法 Z Algorithm を使って文字列の各位置における最長の一致prefixを計算しておく。文中で文字列が交差した際に、計算した条件に合わなければ0を返せば良い。 コード import java.util.Scanner; public class …

Codeforces Round #301 Div2 E: Infinite Inversions (Binary Indexed Tree)

問題 Problem - E - Codeforces 解法 下記リンクで丁寧に解説されている。 Codeforces Round #301 (Div. 2) E. Infinite Inversions - mayoko’s diary Codeforces #301 Div2 E. Infinite Inversions - kmjp's blogBinary Indexed Tree については以下の問題…