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

Codeforces Round #311 (Div. 2)は不参加です。この問題,一発できちんとした解法書くのが結構難しい気がする(書いてる途中で「あ…」ってなって何回か書き直した)。 問題 Problem - 557C - Codeforces 解法 ある長さxを最大長にしたいときはxより長い足の長さ…

これも考察が結構深くて面白かったです。 問題 Problem - C - Codeforces 解法 uwiさんのつぶやきを参考にして考えました(途中から考え方がずれてきてる気がしますが)。Cは最終的にクリーク2個以下にならなきゃいけない。とりあえず1をくっつけて、中に0がい…

個人的にはかなり新鮮で面白かったです。 問題 Problem - B - Codeforces 解法 まず条件を満たすような数列における特徴に注目します。まず条件を満たすためにはcyclic representationsはすべて長さが2以下でなければなりません。これは割と直感的に明らかで…

Codeforces Round #309 (Div. 1)に参加しました。結果はAB解けて個人的には満足だったんですがレートは多少落ちました(得点dynamic形式は強い人にかなり有利なルールな気がするのでもうちょっと工夫してほしいなぁと思います)。解いてて結構楽しかったのであ…

いや簡単だったか… 問題 Problem - D - Codeforces 解法 kを2進数表示した際の各桁が0/1になる場合の数を考える。0になる場合の数が簡単なのでそっちを考える(これを数えることができると1になる場合の数は2^n-(0になる場合の数)と求めることができる)。p[n]…

Codeforces Round #307 (Div. 2)には参加してません。 D難しいですね。 問題 Problem - 551C - Codeforces 解法 基本的には二分探索です。あるxが与えられた時,x秒以内に箱をすべて取り除くことができるかを判定します。基本的にm人の生徒はある規則にしたが…

この解法本番考えたけど棄却してしまった… 問題 Problem - 549B - Codeforces 解法 予想があたっている人がいたらその人を選ぶようにすると必ずうまく行く。 string board[105]; int a[105]; int cnt[105]; int main() { cin.tie(0); ios::sync_with_stdio(f…

これほんと簡単だしなんで本番解かなかったんだ… 問題 Problem - 549G - Codeforces 解法 人の移動を入れ替えで考えるとかなりめんどくさいので問題を単純なものに置き換えます。よく考えると誰と交換したかにかかわらず,前にa人分抜かせば所持金a円減るしa…

問題のレベル的にはE,F以外は解けるべきだったんだよな…ていうかこの問題設定何やねん…石取りゲームにすればええやん… 問題 Problem - 549C - Codeforces 解法 とりあえずゲーム木考えるのはアリだと思いますが状態量がn*nになり,今回の問題の制約では間に合…

問題読んだ時さっぱりわからなかったけど解説読んで目からウロコだった。 問題 Problem - 547C - Codeforces 解法 各クエリに対して,数aに注目しているとすると,gcd(a,b)が1になるものの数は, aの素因数がp1, p2, ..., pmと書けるとして, (p1〜pmのうち0個の…

Looksery Cup 2015に参加しました。結果的にADHを通しました。レーティングは大幅に上がったのでハッピーです。この問題は本番全く意味がわからないままサンプルを頼りにして通したんですが解法見て感動しました。 問題 Problem - 549H - Codeforces 解法 B…

意外に大したことない。 問題 Problem - E - Codeforces 解法 すこし考えれば難しいアルゴリズムは何も必要ありません。まず最後が1の時は絶対にムリ。 また,最後から3番目までずっと1で最後から2番目,1番目が0のときもムリ(これは帰納法的に示せる)。 それ…

問題 Problem - D - Codeforces 解法 奇数の場合は写真のようにすれば構成できる。偶数の場合は作ることは不可能(な気がする)。 あとで証明します。 uwiさんに教えてもらいました。@mayoko_ まず橋の個数がいくつでも、連結成分をまとめたものは木をなすから…

凸包デビュー。 問題 Problem - E - Codeforces 解法 (1/s, 1/r)の点を2次元上にプロットしていき,その凸包を考える。この時,凸法の下側にあるのが答え。理由がはっきりわからないんですが,こんな感じだと思います。 前提としては,水泳とランニングにかかる…

フローわかってる人にとってはとても簡単な問題。僕はよくわかってなかったのでVirtual participationした時には解けませんでした。 問題 Problem - 546E - Codeforces 解法 kmjpさんの解法を参考にしました。Codeforces #304 Div2 E. Soldier and Traveling…

問題 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 というの…

Codeforces Round #305 (Div. 1)に参加しました。ゼロ完。なかったことにしたい。 問題 Problem - 547B - Codeforces 解法 基本的な方針としては以下のような感じ。各値valに対し「最低でもvalという値を取るような数列の長さのうち最大の長さはいくらか」を…

問題 Problem - 545E - Codeforces 解法 ダイクストラで最短距離求めた後root以外の各頂点uについてd[u]-e.cost == d[e.to]となるやつのうちe.costが最小のやつを選ぶ。以下ソースコード struct edge { int to; ll cost; int id; edge(int t, ll c, int i) :…

不満を持つお客に対する血も涙もない対応がひどすぎて笑う。 問題 Problem - 545D - Codeforces 解法 待ち時間でソートする。で,不満を持つお客さんは徹底的に順番を後ろに追いやって不満のないお客さんは待ち時間順に対処する。以下ソースコード const int …

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

ハッシュポテト食べたい。 問題 Problem - B - Codeforces 解法 Z algorithmとかいうのがあるらしいですがハッシュで解決させてしまいました。まずなんでハッシュ値が必要なのかの話から…今回の問題ではy[i]とy[i+1]がp以上離れていたら特に何も問題なく文字…

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

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

問題 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>…

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

Codeforces Round #300に参加。結果はBCD通しただけであんまりよくない。一応レート上がったけど。 戦略としてはあとEかFのどっちかも解くつもりだったけどDで時間食いすぎて間に合わなかった。問題:Problem - 538D - Codeforces解法:よく似た問題がこちら。…

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

Codeforces Round #298 (Div. 2)に参加しました。結果はABCDが通ってくれて,div2とはいえ20位という好順位をとれ結構満足でした。問題:Problem - 534D - Codeforces解法:戦略としては,たくさんの人と握手したと主張する人がなるべく矛盾しないようにするため…

なんとなく初めて解く部類の問題な気がする。問題:http://codeforces.ru/problemset/problem/525/E解法:数列a[]のn個のうちの最初のn/2個を全探索して取りうる値及びその値を取る場合の数を調べる。次にn/2個からn個にある数を全探索して同じことをする。以…