問題 codeforces.com 解法 まず, w と b の最小公倍数 lcm ごとになにか周期になっているっぽいことは明らかです。で, この問題の場合は L が n * lcm + a (0 自然数) と表せる場合のみ結果が引き分けになります。ただ, n = 0, a = 0 の場合は問題の都合上除…

問題設定ちょっと不自然な気がして最初誤読しました。普通上におけるのは体積の小さいものではなかろうか…？ 問題 codeforces.com 解法 素直に dp 解法を取ろうとすると, dp[i] = max(dp[j], j > i, vj > vi) + vi (vi は i の体積) となりますが, これを普…

問題 Problem - 557D - Codeforces 解法 辺が1つもない場合は3本辺を追加するしかない。この場合は頂点の選び方でnC3通り。次に,グラフが二部グラフでない場合は,奇数長の閉路が存在することになるのでこの場合は0本辺追加となる。 グラフが二部グラフの場合…

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

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

問題 codeforces.comA さんと B さんが N 次の多項式の係数を埋めるゲームをする(係数は実数ならなんでも良い)。A さんの目的はこの多項式が x-k で割り切れるようにすることで, B さんはそれを阻止することが目的である。B さんが先行ですでにいくつかの係…

情弱故に敗北した。問題：http://codeforces.com/problemset/problem/527/C解法：最大の面積は(横の長さの最大長さ)×(縦の長さの最大長さ)に等しくなることに注目する。このことにより、横の長さの最大値と縦の長さの最大値をそれぞれ求めれば良いことになる…

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

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

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

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

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

起きれなかったので virtual participation で参加しました。ABCD 解けてそこそこです。ただ D 解くのが遅かったので反省です。 問題 codeforces.com 解法 dp[state][f] = (今までに選んだ食事が state で表されて, 一番先頭に選んでいる食事が f の時の, 最…

問題 codeforces.com 解法 まず, 攻撃されていない町をスタート地点にしても得しない, というか損するのでスタート地点は少なくとも攻撃されている都市のいずれかである, ということがわかります。攻撃されている町全体が連結になるように木を作ることが出来…

問題 codeforces.com 解法 各マグネットの中心(重心)座標しか興味ないので入力値からそれを求めます。この時, double で管理しようとすると不幸になるのですべての座標が 2 倍されてると考えて座標が整数になるようにしましょう。この重心座標については, ど…

Codeforces Round #331 (Div. 2) に参加しました。 AB しか解けず撃沈。C は誤読して難しい問題を解いていたようでアレですが, それに気づいてからも実装に時間がかかるなどしてやっぱり実装力無いなぁと。 問題 codeforces.com 解法 とりあえず誤読してない…

問題 codeforces.com 解法 配列 a の j 番目の数が i 番目のクエリの時点で +k されているとしましょう。この時, j を含む区間 [l, r] において最大値が d になっているというヒントが与えられたとすると, j 番目の数は d-k 以下になっていなければなりませ…

問題 codeforces.com 解法 p 個の数字を使えるとすると, その p 個の数字は w の大きい方から順に選ぶのが明らかに最適です(w は関係ないですね)。ということで, 問題は N 個からなる数列が与えられた時, 最大いくつまで数字を使えるか, の p を求めることで…

問題 codeforces.com 解法 この問題では N, M が比較的小さいので, 一つのクエリにつき O(N log N) 程度で処理できれば AC します。まず, 7000 行目で頂点がいくつぐらいあるのかを確認してみましょう。プログラムに計算させると 109315 個であるとわかりま…

問題 codeforces.com 解法 T の i ブロック目を T[i] と書きます(例えば T[i] = 4-a だったら実際には T[i] = "aaaa")。で, T の l ブロック目から r ブロック目をつなげたものを T[l..r] と書きます。文字列 T の区間 [l..r] に文字列 S があるための条件は…

解いてる時はなんとなく提出したら正解だった, という感じでした。 問題 codeforces.com 解法 右に向いてるやつを左から順番に取っていき, その後に左に向いてるやつを右から順番に取っていく, というのが最適な milking の一つです(左に向いてるやつを右か…

問題 codeforces.com頂点数 n の木 T 上の点 v が T の centorid であるとは, T から v を取り除いて得られる任意の連結成分が, 全て頂点数 n/2 以下であることを言う。各頂点について, その頂点が以下の操作を一回以下許したとき centroid になるかどうかを…

問題 codeforces.comn 頂点の凸多角形が x 軸方向の負の方向に単位時間 v で移動する。この凸多角形の内部に入らないように, y 軸を y = w まで移動したい。 y 軸の移動速度が最大で u の時, 最短で何秒で y = w まで移動できるか。 解法 凸多角形の左側を歩…

本番TLEしたやつ。こういうの慣れてないのでこれから慣れていかないと。問題:Problem - F - Codeforces解法:全探索すると間に合わないのは明らかなので,いろいろと工夫する。 まず第一の工夫が,左右に分けて探索すること。これによって探索量が大幅に減る。 …

Codeforcesの練習はじめました。いきなりひどい目にあった… 問題 Problem - C - Codeforces 解法 変にある程度greedyできる解が見えるから良くない(ACするまでにunionFindとか全探索してから場合分けとかいろいろやってしまった)。賢くやろうとせずに全探索…

問題 Problem - 540D - Codeforces 解法 適切にメモ化再帰する。 以下ソースコード double dp[111][111][111][3]; vector<double> dfs(int r, int s, int p) { if ((r==0 && s == 0) || (s==0 && p==0) || (p==0 && r==0)) { vector<double> ret(3); if (r) ret[0] = 1; if (</double></double>…

こういうのあんまり慣れていないので良い練習問題でした。 問題 Problem - 540E - Codeforces 解法 これによく似た問題として蟻本のBITの説明のところに書いてある問題(p162)があります。これはわかっているという前提で説明します。2つの数の組(i, j)につい…

問題 Problem - C - Codeforces 解法 まずl番目の値がtより大きい場合はどうしようもないので-1を返す。 そうでない時は二分探索する。r番目の数まで0にすることのできる必要十分条件は,s[r] C++の場合オーバーフローに注意(全部10^6で抑えられるのでlong lo…

Codeforces Round #303 (Div. 2)に参加。結果は全完で236位でした。全完出来たのは嬉しいけどB問題でわけのわからんつまり方して順位を大きく落としたのは残念。 問題 Problem - 545C - Codeforces 解法 貪欲で解けるらしいがメモ化再帰で解いた。 dp[n][fla…

問題 Problem - 547A - Codeforces 解法 基本的には公式の解説通り。 http://codeforces.com/blog/entry/18126ただ途中でやってる g(g(...(g(x)))) は c = 1, d = 0 for i = 1 to c c = (cX) % p d = (dX + Y) % p Then, f(x) return (cx + d) % p というの…