Codeforces Round #320 (Div. 1) [Bayan Thanks-Round] に参加しました。A, B を解いたんですが dynamic な scoring のせいでクソみたいな点数になって悲しかったです。 問題 codeforces.com 解法 まず, a 他の場合は, 必ず解があります。その証明も, 次の最…

問題 codeforces.com 解法 まず前提知識です。順列は必ずサイクルの集合で表すことが出来ます。例えば, 2 1 4 3 という順列を考えると, この順列は, 1 2 3 4 の交換によって表現されます。これは, (1, 2) というサイクルと (3, 4) というサイクルの集合で表…

Codeforces Round #319 (Div. 1) の Virtual Participation をやりました。A しか解けなくて死んだので結果的には寝坊してレートを得した感じです。 問題 codeforces.com 解法 割と単純です。まず x 軸を 1000 ごとに分けます。そして, その 1000 ごとの区切…

明後日からまた暇になるのでたくさん解けそうです。 問題 Problem - 552C - Codeforcescodeforces.com 解法 2 通り紹介します。まずひとつ目。 w が 2 と 3 の時は m がどんな値であろうと OK です。よって, それ以外の場合について考えればよいですが, m が…

納得できたようなできてないような。 問題 Problem - C - Codeforcescodeforces.com 解法 こどふぉ解説の図を使わせていただきます。Codeforces Round #318 [RussianCodeCup Thanks-Round] Editorial - Codeforcescodeforces.com木が 2 行の紙に書ける場合は…

いや〜この問題好きですわ。 問題 Problem - 573B - Codeforcescodeforces.com 解法 問題の特徴を観察してみます。まず, 両端のブロックは必ず消えます(問題の本質とは関係ないですが, このことより (N+1)/2 ターン以内にすべての tower が消滅することがわ…

Codeforces Round #202 (Div. 1) の練習会に参加しました。冴えてたというかなんと言うかで ABD を解けました。 問題 Problem - 348B - Codeforcescodeforces.com 解法 発想としては非常に単純です。dp[v] = v 以下の部分木でバランスされている場合に, その…

B より正解者が少ないという。 問題 Problem - 571A - Codeforcescodeforces.com 解法 0 条件を満たすかを考えずに長さを割り振ると, その割り振り方は 通りあります。ここから条件を満たさないような場合の数を引いていきます。例えば, a, b, c の 3 辺の中…

Codeforces Round #317 [AimFund Thanks-Round] (Div. 1) (長い) に参加しました。 前考えていた通り B から解いてみたところ, B だけ正解してレートが上がりました。 A は解けなくてもレート上がるんや！ 問題 Problem - 571B - Codeforcescodeforces.com …

問題 Problem - 557E - Codeforcescodeforces.com 解法 まず dp[i][j] = (i 文字目からの j 文字が半回文になっているかどうか)を適当に求めます。 で, sum[i][j] = (i 文字目から j 文字以上使う文字列の中で 半回文になっているものの数)とします。これを…

問題 Problem - 558D - Codeforcescodeforces.com 解法 まず ans = 1 のものを集めて範囲を絞ります。 その後に ans = 0 のものを集めて範囲を狭めていきます。 const int MAXQ = 100010; int H[MAXQ]; ll L[MAXQ], R[MAXQ], ans[MAXQ]; int main() { int h,…

問題 Problem - E - Codeforcescodeforces.com 解法 毎回のクエリでは, 区間内に存在する文字数を記録し, その文字数ごとにそれぞれの文字を区間に並べなおす, ということをします。 例えば abababbba という文字列で 2 6 1 というクエリが渡された場合, 区…

なるほど… 問題 Problem - 346C - Codeforcescodeforces.com 解法 kmjp さんの解法を参考にしました。Codeforces #201 Div1. C. Number Transformation II - kmjp's blogkmjp.hatenablog.jp int main() { cin.tie(0); ios::sync_with_stdio(false); int n; c…

昔流行ってたのかな…最近よく見る文字列の状態遷移問題。 問題 Problem - 346B - Codeforcescodeforces.com 解法 上で書いたように, まず virus の状態遷移をはっきりさせます。蟻本の 4 章に書いてある文字列テクニックを使います。で, そしたらdp[x1][x2][…

Codeforces Round #201 (Div. 1) の練習会に参加しました。結果は AB 正解でそこそこです。よく考えたらこどふぉレートあげたいんだったら B 解けるかどうかで判断すれば良い気がしてきた。 問題 Problem - 346A - Codeforcescodeforces.com 解法 d を a[1] …

なんとなく方向性わかっても実装できない… 問題 Problem - 570E - Codeforcescodeforces.com 解法 基本的には左上からと右下から同時に攻めて行く感じです(同じ文字だったら進軍可能)。で, これを求めるために dp で解きます。最初に考えたのは dp[x1][y1][x…

問題 Problem - 570D - Codeforces 解法 質問のクエリだけがやってくるので先に質問を全部読んでおきます。で, 各クエリについて, query_v[v] は頂点 v に関するクエリ番号の集合を表し, query_h[i] はクエリ番号 i の質問では高さがいくつの頂点について聞…

オイラーツアーツアー終点です。 セグメント木は典型以外はあんまり自信持って書けません。 問題 Problem - 343D - Codeforces 解法 やっぱりオイラーツアーします。そしてやっぱりセグメント木を 2 つ用意します。 一つは区間に一様に値 x を入れて更新し, …

オイラーツアーツアーその 2 です。 問題 Problem - C - Codeforces 解法 やっぱりオイラーツアーしてセグメント木の問題に落とし込みます。頂点 v の深さを depth[v] とします。頂点 v に x を加えた時, v を含む子 u にはどれだけ値が加算されるかというと…

昨日の練習会の D 問題は解法が「オイラーツアーしてセグメント木」という問題だったらしいんですが, そもそもオイラーツアーって名前しか聞いたことがなかったので, ちょっと練習してみました。 問題 Problem - C - Codeforces 解法 「オイラーツアー 木」…

B よりこっちのほうがアイデアは簡単(実装は面倒)に感じました。 問題 Codeforces 解法 動かしても良い距離 x を決めると, それぞれの disk head をどう動かせばよいのかを貪欲に求めることができるので, x に関して 2 分探索すれば良いです。 const int MAX…

この問題面白かったです。 問題 Codeforces 解法 同じ記号が連続していると, その部分は何もないのと同じにしても良いです。 例えば, -++- の記号を考えます。このとき, ++ の部分は + が - の上に乗っかっているだけなので -- という記号列と同じ意味になり…

Codeforces Round #200 (Div. 1) の練習会に参加しました。ABC 解けてそこそこです(Div. 1 で3 問解けたことなんて多分 1 度もない)。 問題 Codeforces 解法 a/b が 1 以上なら 1 + 1 + ... + 1 + (1 未満の分数) という形にします。 a/b が 1 未満ならその…

Codeforces Round #315 (Div. 1)に参加しました。A しか解けずちーん。 調べてみたらわかったんですが, 僕はCodeforces の Div. 1 で 1 回しかレートを上げたことが無いようです(Div.1 Div.2 合同のラウンドで上げてる)。 問題 Problem - 568B - Codeforces …

昔の SRM に少し似てる問題がありました。 問題 Problem - 566D - Codeforces 解法 union_find を使います。ただ, type = 2 のものは素直に x, x+1, ..., y を union_find でつなげるという発想では時間が足りません。そこで, 例えば 4 から 7 の数字を unio…

最初はすぎむさんの解法だけをお借りするつもりだったのですが,よくわからないTLEに悩まされたので結局ソースコードまでお借りしました。 問題 Problem - E - Codeforces 解法 s から t までの最短経路は普通は複数通りあります。で,問題の解答としては,「最…

Codeforces Round #Pi (Div. 2) は寝坊して不参加です。代わりに virtual participation やったら 4 完でした。 問題 Problem - 567D - Codeforces 解法 二分探索で解きました。med個目までshotした時嘘を付いているとはっきりわかるならtrueを,そうでないな…

実装弱いマンなので実装に非常に苦しみました。 問題 Problem - C - Codeforces 解法 やること自体はそれほど難しくなく,要するに「各iについてa[i]からたどり着くことのできる数を列挙し,それぞれの数に到達する最小手数を求める。すべてのa[i]からたどり着…

本番は筋の悪い方法で考え込んでしまった。 問題 Problem - C - Codeforces 解法 最近流行り(?)の包除原理で解けます。解法の流れとしては,障害物をp個以上通る経路の数をf(p)とすると,求める経路の数はf(0) - f(1) + f(2) - ...で求めることが出来るので,そ…

Codeforces Round #313 (Div. 1)に参加しました。 AしかACせずお通夜でした。そろそろ感覚戻ってきたし良い結果も出したい… 問題 Problem - B - Codeforces 解法 ２つの文字列についてある意味「ソート」のようなことをして,それぞれが一致するかどうかを判…