問題 arc008.contest.atcoder.jp 解法 large だと N の制約が 10^12 とかになっててビビりますが, よく考えると ai = 1, bi = 0 となっているところは無視しても良いので, 結局注目しなければならないところは M 個のみです。 ということで, まず最初に出て…

最近 Splatoon の病に陥っているので「たこ焼きを投げる」と言われるとイカがボムを投げてる姿が思い浮かぶ。 問題 arc008.contest.atcoder.jp 解法 問題の様子を見ます。点(x0, y0) の人を 0, 点(x1, y1) の人を 1, ..., 点(xn, yn) の人を n とします。 ま…

本番いいところまでいったと思ってたけど全く的はずれだったらしい。 問題 TopCoder Statistics - Problem Statement 解法 MST かつ line であるようなものとして, 0-1-...-(n-1) というのだけ抑えておけば, あとはそれを (n!)/2 倍することとで答えが得られ…

問題 TopCoder Statistics - Problem Statement 解法 とーらすさんが完全に解説してるのでそれを参考に。torus711.hatenablog.com解説見るとわかるように priority_queue とやっているところは単に queue で良いですね。 int S, M; bool ok(int x) { priorit…

問題 codeforces.com 解法 よく考えると, 長方形を並べるパターンは, サンプル 1 のように長方形を縦に並べるパターンか, サンプル 2 のようにひとつの長方形が上に来て残りの長方形がエリアを分け合う感じのいずれかしかないことがわかります。うまいこと場…

問題 arc023.contest.atcoder.jp 解法 まず少し考察です。区間 [s, t] にある最大公約数は, s が t から 0 に動くにつれて単調減少します。そして, その最大公約数の減少の仕方は, 素因数が 少しずつ減少していくことで生じます(例えば 6 -> 3 -> 1 と最大公…

かみぺさんがまとめていたので解いてみることにしました。 良問，教育的問題リスト - Google スプレッドシート 問題 abc005.contest.atcoder.jp 解法 各クエリごとに計算するのではなく, データが与えられた時点で計算して, 各クエリには前計算した値でその…

SRM 656 に参加した時 med で同じ解法を使ったんですが, いい復習になりました。 問題 TopCoder Statistics - Problem Statement 解法 包除原理を使います。例えば, N 個のうち, 2 つだけ p[k] 「区切りごとに p[k] ① 1 つ目の区切りまで単調減少, 1 つ目の…

CODE FESTIVAL 2015 予選A に参加しました。なんとか全完, 29 位で予選通過できそうです。良かった… D 問題は過去のこどふぉに(全く同じと言っていいほど)似た問題が出てますねD問題はCodeforcesで見たからなぁ: http://t.co/8uQT9tWrKv— kmjp (@kmjp_pc) 20…

いよいよ明日がCODE FESTIVAL2015予選A本番ですよ！むっちゃドキドキしてきた…。コンテスタントの皆さん、今日くらいは勉強は休んで明日に備えますよね？あと 5 分です 問題 TopCoder Statistics - Problem Statement 解法 2^9 と 5^9 について余りが 0 にな…

SRM の div2 hard は考察が少し難しいか解法自明でめんどくさい問題, という感じがします。今回は解法自明ですが実装が難しかったです。 問題 TopCoder Statistics - Problem Statement 解法 りんごの位置は貪欲に決まります。すなわち, 「直前の K 個を見て…

去年の予選 D 問題解いてなかったので解いてみました。結構苦戦したので予選通れるか心配になってきた。 問題 code-festival-2014-quala.contest.atcoder.jp 解法 桁 DP 的に解きます。dp[keta][state][lt][gt] = (keta 目の桁までで, 0〜9 の数字のうち sta…

すぎむ先生からオススメされた問題があるのでそれを解こうと思ってるのですが, 難しくて考え中なのでお茶濁しにこの問題を解きました。 問題 TopCoder Statistics - Problem Statement 解法 i^(2^k-1) というのは, i^1 * i^2 * i^4 * ... * i^(2^(k-1)) で表…

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

問題 No.282 おもりと天秤(2) - yukicoder 解法 奇偶転置ソートというアルゴリズムを利用します。 奇偶転置ソート - Wikipedia bool cmp[505][505]; int C[505]; bool comp(int a, int b) {return cmp[a][b];} int main() { int N; cin >> N; vector<int> ans(N);</int>…

問題 No.281 門松と魔法(1) - yukicoder 解法 まず d = 0 の場合は, 現在の高さの配分が上手くいってるかどうかだけで 0 か -1 かを判定できます。それ以外の場合は, 真ん中を一番高くするか, 一番低くするかで場合分けすれば良いです。 int H[3]; const ll …

解けなかったけどこれも良い問題。 問題 ttpc2015.contest.atcoder.jp 解法 実は答えとしてあり得る多角形は三角形か四角形しかありえません。なぜかというと, n 多角形は一般に n-2 個の三角形に分割することが出来ますが, 基本的には三角形内部に原点があ…

問題 ttpc2015.contest.atcoder.jp 解法 貪欲で解けます。s を逆から読んでいき, "hcetit" という文字列のうちある部分まで確定している文字列がそれぞれいくつあるかを, state という配列でまとめていきます。 例えば, tititechtech という文字列を考えます…

コンテスト中最後まで満点取れなかった問題。 問題 ttpc2015.contest.atcoder.jp 解法 dp[rest][ok] = (残り人数が rest 人で, すでに K 人での巡換を作ったかのフラグが ok であるような, 場合の数)とします。dp[rest][ok] から, rest 人中選ぶ人数 k のル…

これほんと感動しました。 問題 ttpc2015.contest.atcoder.jp 解法 右端から揃えていく感じでやります。例えば, 4, 2, 5, 3, 1 という順列があったとします。右端は 5 にしたいですが, 5 になっていないので右端の 1 を動かします。ルールにより, 1 の場所か…

問題 ttpc2015.contest.atcoder.jp 解法 桁 DP します。dp[keta][kuriage] = (keta 目の桁において, 繰り上げが kuriage の時の, 揃えられる桁の最大値) とします。 A+B = X の X を求めようとするのでなく, B を求めていこうとすることで, この dp を更新し…

想定解とは別の方法で解いてしまったっぽいです。 問題 ttpc2015.contest.atcoder.jp 解法 K 個の塗り直されたパネルを特別パネルということにします。この K 個の特別パネルのうち, いくつのパネルを使うかで 2^K 通りの場合分けをします...というのが大ま…

東京工業大学プログラミングコンテストに参加しました。 かなり良い問題ばかりでとても楽しかったです。できればもうちょっと良い順位を取りたかった… 問題 ttpc2015.contest.atcoder.jp 解法 S に 5 種類より多い文字があるとサンプルにある通り奇数を対応…

1 位の人 4 分弱で解いてますが早すぎでしょさすがに… 問題 abc029.contest.atcoder.jp 解法 桁 DP で解きました。dp[keta][num][sf] = (keta 目の桁を見ている時点ですでに num 個の 1 を持っていて, N より小さいというフラグが sf であるような数字の個数…

問題 codeforces.com 解法 まず, 数列 a の weakness の値 w(x) は x に関する凸関数になることを把握します。 これは, w(x) が abs(S-x) (S は区間ごとの和) の最大値を取るような感じになっていることからわかります。よって, この問題では w(x) の値をあ…

問題 codeforces.com 解法 一回 x を掛け算すると x は 2 以上なのでビットは 1 以上左にシフトします。よって, 一つの数に集中的に x を掛け算するのが良いです(もしバラバラに x を掛け算すると, 左にシフトする数が少なくなるので不利)。ということで, す…

Codeforces Round #320 (Div. 1) [Bayan Thanks-Round] に参加しました。A, B を解いたんですが dynamic な scoring のせいでクソみたいな点数になって悲しかったです。 問題 codeforces.com 解法 まず, a 他の場合は, 必ず解があります。その証明も, 次の最…

問題 TopCoder Statistics - Problem Statement 解法 この問題では閉路が重要なポジションを占めています。例えば, サンプル 1) を見てみましょう。このグラフでは, (0, 1) という閉路と, (0, 1, 2) という閉路があります。この閉路の長さ 2 と 3 の最大公約…

SRM 668 に参加しました。結果は easy 正解 + challenge 3 回成功で 38 位という良い順位を取れました。 嬉しいんですが, med はほぼ正解にたどり着いていたので med を落としたのが残念です。今度は med も正解したい… 問題 R*C のグリッドを考える。スター…

問題 jag2015summer-day2.contest.atcoder.jp 解法 与えられたグラフを二重辺連結成分分解した際, 例えば頂点数が 2 以上で同じ連結成分になっている場合 (多重辺がないので今回の場合は 3 以上ですが)は, ある連結成分から移ってくる -> その連結成分内の点…