SRM510の練習会に参加しました。1問も解けなくて国内予選の前日なのにお通夜状態でした。 問題 TopCoder Statistics - Problem Statement 解法 桁DPでも解けるんですが今回は状態量がに抑えられるので全探索します。下のコードでは500msくらいかかってるので…

ACM-ICPC国内予選にboTechというチームで参加しました。結果は5完で11位でした。東大は闇なのでアジア予選には進出できないと思いますが正直こんなに上位争いに食い込めるとは思ってなかったので素直にうれしいです。また来年も参加したいですね。担当したの…

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

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

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

本番は問題文が読めなくて非常にイライラした問題(多分解けなかったけど)。こんな複雑な処理みんなよく短時間で書けるなぁ。 問題 TopCoder Statistics - Problem Statement 解法 kmjpさんの解説を参考にしました。TopCoderOpen 2015 Round2B Medium Balance…

SRM509の練習会に参加しました。easyだけ通しただけです。確か練習会ではmedを通した人がいなかったんですがmedは本番も異様に正解率低かったですね。僕も20回ぐらい提出してやっとACしました()今回のeasyは簡単すぎると思うので省略します。 問題 TopCoder …

TCO Round2Bに参加。結果はeasyだけ解いてレーティングが元通りくらいに復帰しました。しばらくSRMはなさそうなのでSRMの練習は練習会だけにしてこどふぉの練習しようかなと思います(div1 のABC)。 med解けないとSRMのレートも高くて1800くらいで止まりそう…

いや簡単だったか… 問題 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人の生徒はある規則にしたが…

オチがそれかよって感じだった。解けなかったの悔しいですね。 問題 TopCoder Statistics - Problem Statement 解法 見た目的に漸化式作って行列累乗でもやるのか(実際には行列累乗はしませんが)という趣があるので漸化式を考えます。n-1個の点を作る方法がp…

SRM661には不参加です。一応easyは自力で解けましたが結構時間かかってしまいました。medはこれから解きます。 問題 TopCoder Statistics - Problem Statement 解法 C++で500ms近くかかっています。想定解とは違うかも。サンプルにヒントがあるように2*Nとい…

言われてみるとなんで気づかなかったって言う奴なんだよなぁ… なんとなくこれ↓に発想が似てる気がする。SRM 506 div1 med:SlimeXGrandSlimeAuto - mayoko’s diarymayokoex.hatenablog.com 問題 TopCoder Statistics - Problem Statement 解法 基本的には狐の…

このDPは思いつかなかった… 良い問題。 問題 TopCoder Statistics - Problem Statement 解法 まず気づかないといけないのは「和がorの和と等しくなるならすべてのa[i]について2進法で表した時のbitの1がかぶっていない」ということです。軽く説明すると,3つ…

SRM練習会に参加。easyは解けてもよかったのですがしょうもないミスをして0完になってしまいました。 問題 TopCoder Statistics - Problem Statement 解法 最初に割り算して個数を減らしてからシフトをしていくのが有利。 どのタイミングからシフトを始める…

9だと思います。 問題 6/2(1+2) | Aizu Online Judge 解法 今までのように返す値を単なるintみたいな感じにしても上手くいかないのでsetを返すようにする。式を分析するときはそれぞれのoperatorがどの順番で使われるのかをnext_permutationで調べていく(た…

題名長いっすね。構文解析の練習です。だいぶ慣れてきた。 問題 How can I satisfy thee? Let me count the ways... | Aizu Online Judge 解法 formulaにしたがって構文解析する。 typedef string::const_iterator State; int formula(State& begin, int s);…

ACM-ICPCの模擬国内予選に参加しました。チーム(@haraduka_, @garasubo, @mayoko_)としてはA, B, Dの3問を解いてなるほど。といった感じでした。以前1年分やった感じでは4完はできると思っていたのでちょっと悲しいです。しかも僕が担当して解かれた問題は一…

本番出したのは計算量の見積もりが甘くてclimpetさんにギリギリまで追い込まれました。 問題 TopCoder Statistics - Problem Statement 解法 B = Nc + Nb * L^3とします。最低でもこの体積分は必要です。 また,実は調べるべき体積はBからB+L^3で抑えられるこ…

SRM 507の練習会に参加。結果はeasyとmedを通してそこそこでした。ただmedは再提出して150ptだったし計算量的にやや危なかったので反省ですね。 問題 TopCoder Statistics - Problem Statement 解法 問題の制約で色は6個以上あるので色が5種類以上あれば絶対…

デバッグに非常に時間がかかったけどなんとか出来た。 問題 Equation | Aizu Online Judge 解法 問題文中に最高のヒントが書いてあるのでそれを元に関数を作る。 <equation> ::= <formula> "=" <formula> <formula> ::= "T" | "F" | "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | </formula></formula></formula></equation>…

今日残りの国内予選の幾何問題を見てて察したのですが,幾何問題は面倒すぎて多分「普通だったら特に練習しなくても解けるし難しかったら解けない」という気がするので構文解析の技術を身につけるほうが良さそうな気がしてきました。ということではい。 問題 …

幾何むずい。 問題 鎖中経路 | Aizu Online Judge 解法 問題文中でご丁寧に示してあるように,最適解では円の交点を通りながらゴールに向かうことになります。円の交点を求める公式はこちらを参考にしました。 円と円の交点を求める - Shogo Computing Labora…

目からウロコおじさんだった。 問題 つながれた風船 | Aizu Online Judge 解法 風船のx, yの座標(X, Y)を一つに決めると,z^2の値としてありえるのはmin()(i = 0〜n-1)となります(はそれぞれ杭に繋がれた糸の長さ,杭のxy座標)。これはに関して上に凸な関数で…

ICPCに参加することになりました。よろしくお願いします。ということで少し練習しようかな,と。2013年 会津大会 の問題を解いてみましたが,問題Cと問題Dは無事正解できました。多分AとBはできると思うのでこの年だと(自分だけなら)4完ですかね。 問題 階層民…

この解法本番考えたけど棄却してしまった… 問題 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になり,今回の問題の制約では間に合…

なんとなく解いたらACした。 問題 TopCoder Statistics - Problem Statement 解法 多くのターンお金を渡しているといつかすべての友達の所持金がたかだか1の差になる。こうなったら後は平等にお金をばら撒けば良いだけなので均等に友達にお金を割り振る。後…

これ解けなかったの若干悔しいかもしれない。 問題 TopCoder Statistics - Problem Statement 解法 単純に再帰関数書こうとするとdfs(n, m) -> dfs(n, m-1) -> ... dfs(n, 1) -> dfs(n, n-1) -> ... -> dfs(n, m)みたいな感じになってぐるぐる回るので死亡す…