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

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Round #397 ABCDE

A. Neverending competitions 問題概要 解法 B. Code obfuscation 問題概要 解法 C. Table Tennis Game 2 D. Artsem and Saunders E. Tree Folding

Codeforces Round #396 (Div. 2) A,B,D,E

C 問題は読めなかったので省略します。http://codeforces.com/contest/766 A. Mahmoud and Longest Uncommon Subsequence B. Mahmoud and a Triangle D. Mahmoud and a Dictionary E. Mahmoud and a xor trip

Codeforces Round #395 (Div. 1) D. Timofey and a flat tree

http://codeforces.com/contest/763/problem/D 問題概要 木が与えられる。ある頂点を根としてみたとき n 個の部分木がある。もっとも部分木の形状の種類が多くなるような根の選び方を求めよ。部分木の形状が等しい、というのは根付き木として同型であるとい…

Codeforces Round #395 (Div. 1) C. Timofey and remoduling (modsqrt)

http://codeforces.com/contest/763/problem/C

Codeforces Round #395 (Div. 1) B. Timofey and rectangles

http://codeforces.com/contest/763/problem/B 問題概要 N 個の長方形が与えられる。長方形の四隅は格子点上にあり、辺は軸に平行、辺の長さは奇数である。長方形同士は重ならない。長方形を 4 色で塗り分けたい。ただし接している長方形の色は異なる必要が…

Codeforces Round #395 (Div. 1) A. Timofey and a tree

http://codeforces.com/contest/763/problem/A 問題概要 木が与えられる。各頂点には色がついている。頂点をひとつ選び削除したとき、分離されたどの部分木も単色であるような削除の仕方を答えよ。

Educational Codeforces Round 17: D. Maximum Path (Simpath)

非想定解法です。普通に解いた方が明らかに楽です。http://codeforces.com/problemset/problem/762/D

8VC Vecture Cup 2017 - Elimination Round

E問題のコーナーケースに気づけなかったのが痛い。 (2017/01/16 15:01: どことは言わないけど、E問題の証明が間違ってたので訂正) http://codeforces.com/contest/755 A. PolandBall and Hypothesis B. PolandBall and Game C. PolandBall and Forest D. P…

Codeforces Round #391: A問題からF問題

http://codeforces.com/contest/757 A. Gotta Catch Em' All! B. Bash's Big Day C. Felicity is Coming! D. Felicity's Big Secret Revealed E. Bash Plays with Functions F. Team Rocket Rises Again

Good Bye 2016 A問題からE問題

黄色コーダーで終わりました。個人的には結構強くなったと思うんですが、数値だけ見ると去年の自分と大差ないですね。というか去年の自分が思ってるより強いですね。 http://codeforces.com/contest/611 A. New Year and Hurry B. New Year and North Pole C…

Codeforces Round #388 (Div. 2)

http://codeforces.com/contest/749

Codeforces Round #387 (Div. 2) A..F

http://codeforces.com/contest/747

Codeforces Round #375 (Div. 2)

http://codeforces.com/contest/723 The New Year: Meeting Friends 問題概要 解法 Text Document Analysis 問題概要 解法 Polycarp at the Radio 問題概要 解法。 Lakes in Berland 問題概要 解法 One-Way Reform 問題概要 解法 st-Spanning Tree 問題概要 …

Codeforces Round #374 (Div. 2): ABCD

http://codeforces.com/contest/721 A: One-dimensional Japanese Crossword 問題概要 解法 B: Passwords 問題概要 解法 C: Journey 問題概要 解法 D: Maxim and Array 問題概要 解法

Dynamic connectivity contest: Bridges: The Final Battle

http://codeforces.com/gym/100551/problem/D 問題概要 辺の追加・削除のクエリが与えられる。クエリを処理する毎に橋の個数を出力せよ。 1≦N,K≦105

Codeforces Round #373 (Div. 1) A. Efim and Strange Grade

A 問題に面倒な実装を持ってくるのやめて欲しい…。 http://codeforces.com/contest/718/problem/A 問題概要 小数点以下のすきな場所で四捨五入するという操作を t 回まで行えるので、操作によって得られる最大の値を求めよ。

Codeforces Round #373 (Div. 1): C. Sasha and Array

http://codeforces.com/problemset/problem/718/C 解法はよくある感じなので、発展的内容として Kitamasa 法について書こうと思います。セグメント木に関しては書きません。

Codeforces Round #371 (Div. 1) C. Sonya and Problem Wihtout A Legend

タイトルの Wihtout はタイプミス…? http://codeforces.com/contest/713/problem/C 問題概要 数列が与えられる。要素を +1, -1 する操作ができる。数列を狭義単調増加にするのに必要な最小の操作回数を求めよ。

Codeforces Round #371 (Div. 1) D. Animal and Puzzle

http://codeforces.com/contest/713/problem/D 問題概要 (x1,y1)から(x2,y2)の長方形領域内にある最大正方形を求めるというクエリを順次処理せよ。

Codeforces Round #371 (Div. 1) B. Searching Rectangles

http://codeforces.com/contest/713/problem/B 問題概要 (1,1)から(n,n)の領域の中に長方形が 2 つある。この長方形の座標は整数であり、2つの長方形は共通部分を持たない。 (x1,y1)から(x2,y2)の領域の中に完全に含まれている長方形の数を数えるクエリを投…

Educational Codeforces Round 16: E. Generate a String

問題ページ 問題概要 現在の文字列の末尾に 'a' を追加(コスト x) 現在の文字列の末尾を削除(コスト x) 現在の文字列全体をコピーし、末尾に貼り付け(コスト y) という 3 種類の操作を使って長さ n の文字列を作る最小のコストを求めよ。 $1 \le n \le…

Dynamic connectivity contest: GraphAero

問題ページ とりあえず LC 木で解けるので解きました。ただこの方法だと D 問題が解けない。 問題概要 N 頂点 M 辺の無向グラフが与えられる。辺(u,v) を追加するというクエリが K 個与えられるので順次処理せよ。各クエリを処理した後、グラフ中にある橋の…

Educational Codeforces Round 16: F - String Set Queries

問題ページ 問題概要 文字列 s をリストに追加 文字列 s をリストから削除 文字列 s の中にリスト中の文字列がいくつ存在するか数える という 3 種類のクエリを順次処理せよ。オンラインクエリ。

Codeforces AIM Tech Round 3 (Div. 1) C. Centroids

あまり筋の良い方法ではないです。 問題ページ

Codeforces AIM Tech Round 3 (Div. 1) B. Recover the String

問題ページ

Codeforces AIM Tech Round 3 (Div. 1) A. Letters Cyclic Shift

問題ページ

Educational Codeforces Round 16: D - Two Arithmetic Progressions

問題ページ

Codeforces Round #368 (Div. 2)

Haskell の練習です。D は C++ のコードも載せておきます。 http://codeforces.com/contest/707 Brain's Photos 問題概要 解法 Bakery 問題概要 解法 Pythagorean Triples Persistent Bookcase

Codeforces Round #367 (Div. 2)

最後の問題が解けなかったのは残念。

Codeforces Round #365 (Div. 2) E. Mishka and Divisors

http://codeforces.com/contest/703/problem/E 問題自体は典型だけど TL 1000ms + オーバーフロー + K=1 のコーナーケースで苦しめられた。

Codeforces Round #365 (Div. 2) D. Mishka and Interesting sum

http://codeforces.com/contest/703/problem/D

Educational Codeforces Round 15: A-E

つい最近 Haskell の練習を始めたので、一部の問題を Haskell で解き直しました。本番中はすべて C++ で解いています。 A. Maximum Increase B. Powers of Two C. Cellular Network D. Road to Post Office E. Analysis of Pathes in Functional Graph

Educational Codeforces Round 15: F. T-Shirts

http://codeforces.com/problemset/problem/702/F 別の解があるようです。それと嘘解法の可能性があるので、あまり鵜呑みにしないでください。

Codeforces Round #363 (Div. 1) C. LRU

http://codeforces.com/contest/698/problem/C

Codeforces Rounds #361 (Div. 2)

http://codeforces.com/contest/689 A. Mike and Cellphone 問題 解法 B. Mile and Shortcuts 問題 解法 C. Mike and Chocolate Thieves 問題 解法 D. Friend and Subsequences 問題 解法 E. Mike and Geometry Problem 問題 解法

Codeforces Round #360 (Div. 1)

http://codeforces.com/contest/687

Codeforces Round #359 (Div. 1) A. Robbers' watch

http://codeforces.com/contest/685/problem/A 問題 0..n-1 時 0..m-1 分まで 7 進表記で表示できる時計がある。どの桁も異なる表記は何通りあるか。 1≦n,m≦109

Educational Codeforces Round 13 F. Lena and Queries

http://codeforces.com/contest/678/problem/F 問題 以下の 3 種類のクエリを処理せよ。 点 (x,y) を set に追加する i 番目のクエリで追加した点を set から削除する xq+y の最大値を求める

Codeforces Round #353 (Div. 2) E. Trains and Statistic

http://codeforces.com/contest/675/problem/E 問題 n 個の駅があり、i 番目の駅からは i+1..a[i] の駅に移動可能である。 ρ(i,j) を駅 i から駅 j への最短ステップ数とする。すべての i

Codeforces Round #353 (Div. 2) D. Tree Construction

http://codeforces.com/contest/675/problem/D 問題 二分探索木の動作をシミュレーションせよ。 i 回目の操作で挿入された値の親の値を出力すればよい。挿入する値は distinct であることが保証されている。 2≦n≦105 1≦a[i]≦109

Codeforces Round #353 (Div. 2) C. Money Transfers

http://codeforces.com/contest/675/problem/C 問題 数列 an が与えられる。i 番目にある値を i-1,i+1 のどちらかに流すという操作ができる。 すべての要素を 0 にするのに必要な最小の操作回数を求めよ。 2≦n≦105 1≦a[i]≦109

Codeforces Round #353 (Div. 2) B. Restoring Painting

http://codeforces.com/contest/675/problem/B 問題 3x3 のグリッドがあり、a,b,c,d の値が分かっている。 ?a? b?c ?d? また、? に入る値は 1..n であることも分かっている。 どの連続した 2x2 のグリッドを切り出しても総和が等しくなるような ? の当てはめ…

Codeforces Round #353 (Div. 2) A. Infinite Sequence

http://codeforces.com/contest/675/problem/A 問題 a, a+c, a+2c, a+3c,... と列挙していったとき b は現れるだろうか。 -109≦a,b,c≦109

Codeforces Round #350 (Div. 2) F. Restore a Number

問題文が短いにもかかわらず題意を汲み取るのに苦戦した。 http://codeforces.com/contest/670/problem/F 問題 ある整数 n があり、n に n の桁数をくっつけてシャッフルした文字列 Sと n の一部分 T が与えられる。ありうる n の最小値を求めよ。

Codeforces Round #350 (Div. 2) E. Correct Bracket Sequence Editor

問題文に図があって助かる。 http://codeforces.com/contest/670/problem/E 問題 以下の処理が行えるテキストエディタの動作をシミュレーションせよ。 カーソルを右に動かす カーソルを左に動かす カーソル上の括弧と、それに対応する括弧の間を削除する。 …

Codeforces Round #350 (Div. 2) A,B,C,D

今回は比較的解きやすい問題だったせいか E まで解けた人が多く、解くスピードも求められたようだ。 A. Holidays http://codeforces.com/contest/670/problem/A 問題 一年が n 日ある惑星の話で、平日 5 日と休日 2 日が交互にやってくる。1 年を通した休日…

Codeforces Round #348 D. Little Artem and Time Machine

http://codeforces.com/contest/668/problem/D 問題概要 以下の 3 種類のクエリを処理せよ。 時刻 t に飛んで多重集合に x を 1 個追加する 時刻 t に飛んで多重集合から x を 1 個取り除く 時刻 t に飛んで多重集合にある x の個数を数える

Codeforces Round #348 C. Little Artem and Random Variable

http://codeforces.com/contest/668/problem/C 問題概要 1 から n の目まであるサイコロが 2 種類ある。このサイコロは出目の確率が均一とは限らない。 このサイコロを同時に振ったときの「目の最小値の確率分布」と「目の最大値の確率分布」が与えられるの…

Codeforces Round #348 B. Little Artem and Dance

http://codeforces.com/contest/668/problem/B 問題概要 1..n が順に並んだ数列 A が与えられる。この数列に対して以下の 2 種類の操作を行う。 数列を x だけ回転シフトする。 隣り合う要素同士を交換する。つまり i:0→n/2-1 に対して swap( A[ 2i ], A[ 2i…

Educational Codeforces Round 12 F. Four Divisors

大体は Editorial に書いてある方法だと思います。 http://codeforces.com/contest/665/problem/F 問題概要 1 から n までの整数のうち約数をちょうど 4 つ持つものは何個あるか。