オイラーツアーツアー終点です。 セグメント木は典型以外はあんまり自信持って書けません。 問題 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 未満ならその…

この解法 TLE すると思ってたので「は？」と言わざるを得ない。 問題 3046 -- Ant Counting 解法 dp[n][t] = (n 種類目まで見ている時点で, セットの大きさが t 以下になるような集合の数)とします。 すると, dp[n][t] は, n 種類目まででセットの大きさが t…

今では典型ですね。 問題 3280 -- Cheapest Palindrome 解法 典型なので略。 const int INF = 1e9; int dp[2020][2020]; int cost[26][2]; string s; int dfs(int l, int r) { if (l >= r) return 0; int& ret = dp[l][r]; if (ret != -1) return ret; ret =…

dp の練習で蟻本のやつを解いてみました。これは簡単。 問題 3616 -- Milking Time 解法 まずスタートの時間ごとにソートする。dp[m] = (m 番目から最後までの milking time だけで最大化しようとした場合の最大値)として, 適当に dp する。 struct Milk { i…

満点解法書いてみてなんとなく理解したので書きます。ソースコードは解説コードに少し説明を加えただけです。 問題 G: おおきなかずを作った (I made a huge number) - 技術室奥プログラミングコンテスト | AtCoder 解法 基本的な方針は以前書いたものと変わ…

SRM 665 に参加しました。今回は 0 完でしたが運良く unrated になった(なりそう)のでレート下降は避けられそうです。前にも今回のような感じで「全探索してもギリギリいけそうなきがするけどダメな制約」的な問題があったような気がするんですが, また引っ…

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

蟻本の文字列の章読んでたら出てきたので解きました。POJ めっちゃ久しぶりや… 前やった SRM の問題に似てます。SRM 519 div1 med:RequiredSubstrings - mayoko’s diarymayokoex.hatenablog.com 問題 3691 -- DNA repair 解法 蟻本に書いてあるとおり。 cons…

技術室奥プログラミングコンテストに参加しました。ABCDEだけ解くという普通の人でした。 蟻本の chapter 4 (上級編)まともに読んでないので suffix array とか言われてもさっぱりで, 満点解法を紹介するのは時間がかかりそうなのでとりあえず部分点解法だけ…

倍々ゲームからバイバイ(激寒)。 問題 C: 倍々ゲーム - AtCoder Beginner Contest 027 | AtCoder 解法 スライドと言っていることは本質的に同じですが, 試行錯誤の仕方は違ったのでそっちを紹介したいと思います。2 倍とか言っているところがビットっぽいの…

ぐぬぬ… 問題 D: ロボット - AtCoder Beginner Contest 027 | AtCoder 解法 スライドがわかりやすいのでほとんどそのままです。 abc027 from AtCoder Inc. www.slideshare.net一応すこし補足すると,最終的な答えがソートした際の(後半そのまま) - (前半その…

良いdpの練習問題ですね…(全然サンプルが合わなくて死んだ) 問題 TopCoder Statistics - Problem Statement 解法 dpの組み合わせです。全体で参加者が N 人であるとします。 次のような2つのdpっぽいものを考えます。dp[n][p] = ([n, N]の人の得点のみを気に…

疲れた… やっぱ構文解析難しいです。 問題 No.265 数学のテスト - yukicoder 解法 構文解析する。ノリは↓と同じです。AOJ 109 Smart Calculator - mayoko’s diarymayokoex.hatenablog.com int d; typedef string::const_iterator State; vector<ll> expression(S</ll>…

SRM 520 にちょっとだけ参加しました。easy だけささっと解いて yukicoder 参加です。あとで med も解きたいと思います。 問題 TopCoder Statistics - Problem Statement 解法 easy と med で luck を使う時間を全探索して,それでいてかつ解く順番も全探索し…

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

"As you must know," 怖い… 練習です。 問題 Problem - 566F - Codeforces 解法 dp[n] = (nを約数とする数字の個数)とします。数列 a を直接使うのではなく, b[p] = (数列 a の中に p という数がいくつあるか)という配列を用意しておけば, dp[n] の計算は, M…

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

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

言われてみると桁DPの一般化っぽい感じ。 問題 TopCoder Statistics - Problem Statement 解法 主となるアイデアは桁DPとほとんど変わりません。つまり,ある文字列の状態(stateとする)にaからzのいずれかの文字を追加した時の次の状態(nextstateとする)とし…

解説(http://tenka1.klab.jp/2015/explain/quala_d.html)微妙に違うような…「葉」の解釈にもよるけど。 問題 D: ハシポン - 天下一プログラマーコンテスト2015予選A | AtCoder 解法 概ね解説のとおりなのですが,「葉」と書いてあるところは「次数1の頂点」と…

SRM519の練習会に参加しました。今回はeasyもmedも難しい印象です(easyに関しては僕だけかも)。 問題 TopCoder Statistics - Problem Statement 解法 とりあえず気づかないといけないのは,ある数xからx+1に変わる時カードをひっくり返すことによって得られる…

天下一プログラマーコンテスト2015予選Aに参加しました。天下一完でした。別に予選通過できるとは思ってないけどもうちょっと解けないかなぁ… 問題 C: 天下一美術館 - 天下一プログラマーコンテスト2015予選A | AtCoder 解法 基本的に,AとBで一致している部…

前言ったかもですがmedはたいてい「気付きの『けり』」が2つ必要な印象。 今回は1つも気づきませんでした。 問題 TopCoder Statistics - Problem Statement 解法 まず気づかないといけないのは,「rigionの大きさの2乗の合計」は,「経路がつながっている頂点…

SRM 664に参加しました。easyを通してレート上昇です。うれしいけどmed解きたい… 問題 TopCoder Statistics - Problem Statement 解法 結論から言うと tmp = min(A, B) * 2^K mod (A+B) として,min(tmp, A+B-tmp)が答えです。(2^K mod (A+B))はO(log K)で高…

なんか結果が合わなくて解ききる前に寝てしまった。 問題 No.260 世界のなんとか3 - yukicoder 解法 見た目から明らかに桁DPです。dp[n][big][exist][mod3][mod8] = (n番目までで,元の数より大きいフラグがbigで,とある桁に3があるかのフラグがexistで,3で割…