凸包デビュー。 問題 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 というの…

問題 TopCoder Statistics - Problem Statement 解法 基本的な方針は以下の通り。 まず0行目は必ずoutputの0行目と一致していなければならない(0行目は変更することが出来ないから)。そして1行目以降は,i行目とi-1行目にのみ依存してoutputが生成されること…

SRM練習会に参加しました。結果はeasy, med解いてまぁよかったんですがeasy気づくのが遅すぎて140ptくらいしか取れなかったのが残念です。 問題 TopCoder Statistics - Problem Statement 解法 単にシミュレーションするだけ。ただ本当に愚直にやると黒を引…

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

そこそこ惜しかったな… 問題 TopCoder Statistics - Problem Statement 解法 普通にやろうとするとN!通りとかN*2^N通りとか試さないといけないので当然間に合いません。期待値だともはやありきたりな感じがありますがこういう時は期待値の線形性を利用して計…

SRM練習会に参加。結果はeasyだけ解いてはい。 問題 TopCoder Statistics - Problem Statement 解法 結構本番不安だったんですがメモ化再帰で解きました。undertoastedとovertoastedがソートされているとします。「1種類のパンを考慮するときにundertoasted…

topcoderっぽい良い問題だと思います。 問題 TopCoder Statistics - Problem Statement 解法 無理ゲーにしか見えなかったので解説(http://apps.topcoder.com/wiki/display/tc/SRM+502)を参考にしました。こちらには考える動機的なものも多少書いてあります(…

Dancing・Forever。 問題 TopCoder Statistics - Problem Statement 解法 kmjpさんの記事を参考にさせていただきました。TopCoder SRM 658 Div1 Hard DancingForever - kmjp's blogkmjp.hatenablog.jpなんでこの解き方で良いかについて少し補足しようと思い…

これ↓に参加しました。Comic Ver “Too Much Turmoil Over My Childhood and My Affianced One” |paiza online hackathon 5paiza.jp考えたこと,及びソースコード↓paizaのアレネタバレして良さそうなので公開 https://t.co/qKx2kBcF7b 15パズルで遊んでたら上8…

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

ツボクラさんがSRM 502のmedはこの問題の類題で解いたとつぶやいていたので解いてみました。 こっちの方が3倍位難しく感じる… 問題 No.54 Happy Hallowe'en - yukicoder 解法 medと同じように何らかの基準を見つけ,その基準通りもらえる家の順番を並べ,dpし…

この記事↓SRM 502 div1 easy:TheLotteryBothDivs - mayoko’s diarymayokoex.hatenablog.com で言ったとおりTrie木でもやってみました。最初に宝くじに当たりがつくところにflagを立てながらTrie木を構成していきます。その後に,dfsでflagが立てたノードに来…

問題 TopCoder Statistics - Problem Statement 解法 普通に調べようとすると多分思いつくのはO(n * 2^n)の動的計画法です。しかしこれでも計算量が多すぎるので更に工夫が必要です。そこで,少し別の問題を考えてみます： 仮に解く問題が決まっているとする…

SRM 502の練習会に参加しました。結果は全落ちで（◞‸◟）でした。 問題 TopCoder Statistics - Problem Statement 解法 例えば{"74", "4"}というのを考えると,これは"4"の方のみ考えれば良いことがわかる(74と4では1の位が被ってるので)。 よって,goodSuffixe…

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

これは知らなかったので仕方ない… 問題 D: 旅行会社高橋君 - AtCoder Regular Contest 039 | AtCoder 解法 解説(AtCoder Regular Contest 039 解説)の通り。実装について簡単に説明しておきます。最初の方に書いてあるvisitとかbridgeとかはこのページ(Spagh…

ARCに参加しました。結果はABだけ解いて（◞‸◟）でした。 問題 C: 幼稚園児高橋君 - AtCoder Regular Contest 039 | AtCoder 解法 解説(AtCoder Regular Contest 039 解説)の通り実装したつもりです。 毎回自分の位置を更新するたびに4方向の近傍が次にどこに…

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

これは面白い問題だなぁ。 問題 No.210 探し物はどこですか？ - yukicoder 解法 実際に最適な動きをシミュレーションする。具体的には,・現時点で一番ある確率が高い部屋に探しに行く。今までに部屋iにx回通っていたとすると,その部屋でものを見つける確率は…

見た目から動的計画法だろうと思ったけど出題時は☆2で,「もっと簡単な方法があるのかなぁ」とか悩んでしまった。 問題 No.209 Longest Mountain Subsequence - yukicoder 解法 問題設定がちょっと複雑だが,とりあえずという方から考える。 dp[cur][pre] := (…

問題 TopCoder Statistics - Problem Statement 解法 dp[cur][sum][before][de] := (今cur番目の数を見ていて,cur未満の数での総和はsumになっていて,curの直前の数はbeforeで,de個strictに数が減少している時の条件を満たす場合の数) として,適切に漸化式を…

SRM 501の練習会に参加。easyとmed通してそこそこでした。今回のmedは簡単だったしまぁ。 問題 TopCoder Statistics - Problem Statement 解法 あんまり推薦されない方法で解いてしまった感じがあるが,場合分けして通した。無難にやりたいならdp[a][b]=(足し…

こういうのあんまり慣れていないので良い練習問題でした。 問題 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とか全探索してから場合分けとかいろいろやってしまった)。賢くやろうとせずに全探索…

牛ゲーという単語を初めて聞いた。 問題 TopCoder Statistics - Problem Statement 解法 牛ゲーというのは,とある線形計画問題について,制約が d[u] という形で,また最小化したい値が d[t] というようにおける時,この問題の答えは①で表されるそれぞれの制約…