SRM518の練習会に参加しました。easyとmed通せました。わーい。easyは簡単だと思うので省略します。 問題 TopCoder Statistics - Problem Statement 解法 貪欲っぽい感じで解きました。a[i]とa[i+1]の差をb[i]とします。凸になるためには,bの配列が単調増加…

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

この問題とは関係ないですがカードヒーローってゲーム僕はすごく好きです。 問題 No.200 カードファイト！ - yukicoder 解法 貪欲で解く。Aが勝てるときはAはなるべく小さい値で,Cはなるべく大きい値で勝つ。Aが負けるときもAはなるべく小さい値で,Cはなるべ…

問題 TopCoder Statistics - Problem Statement 解法 注目すべき特徴として, 「ある場所でスワップしたら,もうそこを挟んで数が移動することができなくなる」 ということがあります。例えば,0 1 2 3 4という順列で1と2をswapすると,0 2 1 3 4となりますが,こ…

SRM 517の練習会に参加しました。ゼロ完で悲しみが募る。 問題 TopCoder Statistics - Problem Statement 解法 基本的にtargetがNの素因数ならOKです。ただ,例外として, ・targetがNと同じならOK ・Nがひとつの素因数pのみを持ちかつNがp*p以上の場合は,p*p…

これは良い問題だと思いました。 問題 No.243 出席番号(2) - yukicoder 解法 なんとなく包除原理っぽいです。(0個以上嫌いナンバーが選ばれる場合の数) - (1個以上嫌いナンバーが選ばれる場合の数) + (2個以上嫌いナンバーが選ばれる場合の数) - ...という感…

yukiさんが青コーダーなった記念にyukiさんの動画を覗きに行ったら問題の紹介をしていたので解くことにしました。結構苦戦したしdiv2 hardも練習しても良さそう。 問題 TopCoder Statistics - Problem Statement 解法 ある集合stateの中である人nがどれだけ…

戻すDP,覚えました(あんまり理解していない) 問題 TopCoder Statistics - Problem Statement 解法 こどふぉの解説を参考にしました。 SRM 663 Brief Editorial - Codeforcesways = {1, 3, 6, 2}となっているときに,それに対応する多項式を考えてとします。こ…

昨日のAtCoderのD問題の類題ということで解きました。 問題 No.97 最大の値を求めるくえり - yukicoder 解法 Nがそこそこ小さい時(3000未満)のときはそのまま計算しても間に合うので普通に計算する。Nが大きい時を考える。100003は素数であることに注意する…

これは難しい… 問題 TopCoder Statistics - Problem Statement 解法 左からどういう順番で座るかを決めて,どの人が座ってどの人が座らないかを決めた時に,そのような座り方があり得るかどうかを判定していく。制約式は以下のような感じになる。これを牛ゲー…

SRM663に参加しました。結果はeasyをそこそこ早解きでレートが上がりました。試験期間終わってからずっとレートが下がってたのでとりあえず一安心です。 問題 TopCoder Statistics - Problem Statement 解法 targetからA,Bを取り除いてinitialを作ることを考…

アイデアはそれほど難しくないような？ 問題 No.86 TVザッピング(2) - yukicoder 解法 ぐるっと回ってすべての点を一周するためには,外側から囲うように回っていくしかありません。なので,スタート地点を全列挙して上のルールにしたがって動いていった時,ち…

本番は筋の悪い方法で考え込んでしまった。 問題 Problem - C - Codeforces 解法 最近流行り(?)の包除原理で解けます。解法の流れとしては,障害物をp個以上通る経路の数をf(p)とすると,求める経路の数はf(0) - f(1) + f(2) - ...で求めることが出来るので,そ…

Codeforces Round #313 (Div. 1)に参加しました。 AしかACせずお通夜でした。そろそろ感覚戻ってきたし良い結果も出したい… 問題 Problem - B - Codeforces 解法 ２つの文字列についてある意味「ソート」のようなことをして,それぞれが一致するかどうかを判…

気づかなかった… 問題 TopCoder Statistics - Problem Statement 解法 S(T)は,別の見方をすると,「ある頂点から別の頂点に向かうときに,それぞれの辺を何回通るか,の総和」とみなすことが出来ます(頂点単位でゴニョゴニョ考えるのではなく辺単位で考える)あ…

幾何ライブラリを補充しました。 問題 No.245 貫け！ - yukicoder 解法 「どの端点とどの端点を通るような直線を作るか」で全探索する。直線が線分と交差しているかどうかの判定は基本的には蟻本に書いてあるとおり。ただサンプル4のようなケースは通らない…

これはもっと早く解けるべきだった… 問題 No.247 線形計画問題もどき - yukicoder 解法 dp[c] = 「cを作るx_1, ..., x_nの組の最小値」 とするとdpで解ける。 const int MAXC = 100100; const int MAXN = 101; const int INF = 1e9; int dp[MAXC]; int C, N;…

いやぁこれ結構実装大変だと思うんですけど… なんか一発ACしてる人多いですねぇ。 問題 No.226 0-1パズル - yukicoder 解法 基本的な方針は,「上の行が決まると下の行も決まるんじゃね？」ということです。この予想はある程度正しくて,上の行に少なくともひ…

最近yukicoderやってなかった… 問題 No.15 カタログショッピング - yukicoder 解法 半分全列挙するだけ。 const int MAXN = 32; int P[MAXN]; struct pll { ll first; ll second; }; bool operator<(const pll& lhs, const pll& rhs) { return lhs.first < r…

TCO15 Round 2Cに参加しました。ゼロ完でちーん。 問題 TopCoder Statistics - Problem Statement 解法 一番ポイントなのは,「パスするときに飛ばすカードは,後から決めれば良い」ということです。これに気づくと,dp[今一番上にあるカードの数][ターン数]でd…

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

問題 TopCoder Statistics - Problem Statement 解法 基本的に状態として[持ってる刀の数][時間][どの客が来たかのフラグ]というのを持ってdpすれば大丈夫です。 ただ,客が最高で24人いるわけなので,どの客が来たかのフラグというのは2^24通りになってこれで…

SRM514の練習会にだいぶ昔に参加しました。結果はeasyだけ通すだけでした。medは考え方がほとんど合ってたし惜しい。 問題 TopCoder Statistics - Problem Statement 解法 時計の時刻を順番に全探索して条件にあるのがあったらそれを返す。 string tost(int …

久しぶりに記事書きます。といっても書くことがない… 問題 TopCoder Statistics - Problem Statement 解法 TopCoder SRM 662 Div1 Easy: FoxesOfTheRoundTable - 宇宙ツイッタラーXの憂鬱kenkoooo.hatenablog.com@mayoko_ n+2とn+3を交換するとn+3とn+4が隣…

SRM512の練習会に参加しました。結果はeasyをそこそこ早解きしてmedはいつも通り落としてそこそこでした。SRM509くらいから急にmedの難易度が上がってる気がする。今回はeasyもまぁまぁ難しかった。 問題 http://community.topcoder.com/stat?c=problem_stat…

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

なるほどという感じのdpだった。難しいdpに全く気づかない。 問題 Fox CielとToastmanがゲームをする。 n枚のカードおよび0に初期化された数nowを準備する。各プレイヤーは順番にカードを1枚ずつ取り除いていく。取り除く際,そのカードに書かれた数字をnowに…

SRM練習会に参加しました。easyとmedを提出したんですがmedは落ちました。このころのtopcoderはサンプルが弱い気がする。 問題 ウサギとネコがいて,それぞれの動物に「自分と同じ種族で,自分より背の高い動物が何匹いるか」を質問する(すべての動物は背の高…