問題 tdpc.contest.atcoder.jp 解法 普通に dp[k][i] = (i が k 回戦まで勝ち抜く確率) とやれば良いんですが, 微妙に遷移で迷ったので書いておきます。i が k 回戦で戦う可能性がある競技者を考えます。p = 1= med であるとすると, いままでは [med, maxi) …

問題(というかトップページ) snuke21.contest.atcoder.jp 解法 t を作って, そこから s を作ることを考えます。例えば t が 11001 とかだったとすると, s は, (0...0)1(0...0)1(1...1)0(1...1)0(0...0)1(適当な文字列) というようにして構成できます。t[i] =…

解法 bitDP します。dp[s] = (s で表される集合は既に優先順位が上になることが決まっていて, 新しく別の種類の食品を食べることが出来ないと決まっている月である時, まだ追加することの出来る食品の種類の数) とします。mask[i] = (食品 i が売られている…

問題(というかトップページ) snuke21.contest.atcoder.jp 解法 's' を消せるので, 's' が連続した部分文字列の直後の文字 c が c 's' を満たすなら, なるべく消したくないですが, 消さないといけないとしたら, 辞書順に影響を与えにくい後ろから消していくの…

問題 discovery2016-qual.contest.atcoder.jp 解法 入力文字列 s の長さを N とします。もし s の中に N-K 個以上 a がある場合は, N-K 個の a を最終的な文字列にするのが最強です。別の場合は, a のみを残す, という戦略は出来ないので, a をなるべく手前…

DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選に参加しました。なんとなく早解きコンテストになるんじゃないかと思っていましたが面白かったです。非競プロ勢には厳しかったような気がしますが。 問題 discovery2016-qual.con…

問題 s8pc-1.contest.atcoder.jp 解法 半分全列挙 + 平面走査 で解きます。半分の要素について, 残す食品が e 個あるという前提での残りの食品のわけかたを全列挙します。 square1001とE869120の合計値段の差を x 軸に, square1001とうさぎの合計値段の差を …

問題 dwango2016-prelims.contest.atcoder.jp 解法 二分探索します。ok(x) = (時間 x 以下で目的地にたどり着けるか) を判定する関数を作ります。そのために, ダイクストラのようなことをしますが, ある頂点 v に時間 t にたどり着けることがわかったとして,…

第2回 ドワンゴからの挑戦状 予選 に参加しました。結果はあんまり良くなかったですが 17 卒パワーで予選通過したと思います。 問題 dwango2016-prelims.contest.atcoder.jp 解法 まず考察です。memox[x1][x2] = (長方形の x1 〜 x2 を使うと決めた時, y1, y…

問題 arc047.contest.atcoder.jp 解法 まず, X 番目の順列がどのような順列になるのか, という問題を考えてみます。並べる数が 0-index であるとすると, 一番最初の数は X/(N-1)! で与えられます(X これは N-1 最初の数を決めて残りの N-1 個の数の並べ方が …

問題 arc047.contest.atcoder.jp 解法 ある点からのマンハッタン距離が等しい頂点というのは, こんな感じ(◇)の形をしています。これでは考えにくいので, 45 度回転させるイメージで, 座標 (x, y) を (x+y, x-y) に変換します。すると, ある点からのマンハッ…

「ナップサック問題か〜どのナップサックかな〜 多分半分全列挙？」「全部です」「はい」 問題 abc032.contest.atcoder.jp 解法 蟻本に載ってるナップサック問題の解法を試せば良いです。蟻本第二版での話ですが, 半分全列挙 -> p148 w[i] p52 v[i] p60に書…

問題 arc046.contest.atcoder.jp 解法 完全に解説がわかりやすいのでそちらを見ましょう。 AtCoder Regular Contest 046 from AtCoder Inc. www.slideshare.net const ll MOD = 1e9+7; ll fact[1000100]; ll rfact[1000100]; // extgcd ll extgcd(ll a, ll b…

問題 arc046.contest.atcoder.jp 解法 貪欲にやっていきます。男性を年収が低い順, 女性を希望年収が低い順に並べておきます。 で, 男性の年収が低い順に以下のことを調べます。1. 今考えている男性を man とする。 2. man の年収で OK な女性を set に詰め…

問題 code-thanks-festival-2015-open.contest.atcoder.jp 解法 まず前計算として, (y0, x0, y1, x1) で決まる長方形内にある数字の合計, および 長方形内にある各数字の数, を求めておきます。そのあとはしゃくとり法です。問題文にあるように c と d を決…

問題 code-thanks-festival-2015-open.contest.atcoder.jp 解法 基本的な方針は(頂点, 色)の組でまとめた頂点に対するグラフについてダイクストラやるだけです。ただ, 少し工夫しないと計算量やメモリが大変なことになるので少し工夫します。工夫1: (頂点, …

問題 code-thanks-festival-2015-open.contest.atcoder.jp 解法 ここでは「勝つ」というのは「実 1 を食べる」ということを指します。また, 「実(み)」と「頂点」はしばしば同じ意味です。まず, 頂点 1 の次数が 1 なら A さんは速攻で食べれば良いので A が…

問題 code-thanks-festival-2015-open.contest.atcoder.jp 解法 文字列 S の start 以降の部分文字列を使うと, 文字列 T が表現できるとしましょう。このとき, S の start 以降の文字列は, T に現れる文字(例えば T = "abc" だったら a, b, c) を飛ばすこと…

あさプロの時はものすごく混乱してて結局解けなかったんだけど, 今やったらめっちゃあっさりだった。 問題 code-festival-2015-morning-middle.contest.atcoder.jp 解法 N は奇数なので, 最後にすべてのコマが同じ色になる時コマは絶対に白色になっています…

いつ追加されるんだろうとずっと思ってたけどやっと追加されたので解きます。 問題 code-festival-2015-morning-middle.contest.atcoder.jp 解法 繰り返す文字列は左側と右側に分かれるので, 左からの i 文字と残りの右側 n-i 文字でなるべく長い, 一致する…

この問題好き(だけどプロの人は典型とか言いそう)。 問題 jag2015autumn.contest.atcoder.jp 解法 考えやすくするために「1年生の集合」「2年生の集合」「3年生の集合」という集合を表した頂点(これらを A, B, C とする)を考えます。すると, 求めるべきなの…

問題 jag2015autumn.contest.atcoder.jp 解法 長さが短いものから順に処理していきます。 処理するときは, その手前のファイル, それより後のファイルをどれだけ消せるかを確かめていけば良いです。要するに貪欲法ですが, 小さい順に消していけば, 「消せる…

問題 jag2015autumn.contest.atcoder.jp 解法 各場所よりも右にある "" の数を数えると, 最終的にどちら側にたどり着くかがわかります。 例えば >>> という文字列を考えた時, 左から 4 番目にある文字 "" の数は 2 つで, これより右側にある " こんな感じで,…

問題 jag2015autumn.contest.atcoder.jp 解法 N! 通りの全探索をするだけです。 ll calc(const string& s, const string& t) { int n = s.size(); ll p = 1; for (int i = 0; i < n; i++) p *= 10; ll S = stoll(s), T = stoll(t); ll tmp = abs(S-T); retur…

問題 jag2015autumn.contest.atcoder.jp 解法 S からは交互に文字を取っていくことになるので, 要するに焦点となるのは, 「S から 1 つおきに文字を取っていったもの(s とする)と, T の部分文字列とで, 最長共通部分文字列が s に一致するかどうか」というこ…

問題 abc031.contest.atcoder.jp 解法 n 番目の v, w の対応では各数字がどのような文字列に対応しているか, というのを深さ優先探索すれば OK です。具体的な実装は, dfs(m, num, cur, S) = 「n 番目の v, w の対応を調べているが, v の方は num 番目の数字…

全然自力で解けないんですが, それは… 問題 code-festival-2015-final-open.contest.atcoder.jp 解法 まず, 区間が 3 つ以上重なっている必要はないことがわかります。3 つ以上重なっている場合, それらを合わせた区間で左端にも右端にもならないものはある…

問題 code-festival-2015-final-open.contest.atcoder.jp 解法 やっぱり解説がわかりやすいと思いますね…前準備として, depth[i] = (i 番目の頂点の高さ), maxDepth[i] = (i を根とする部分木に属する頂点の高さの中で最大のもの) という値を簡単な木 DP で…

問題 code-festival-2015-final-open.contest.atcoder.jp 解法 解説見るのがわかりやすいと思いますが一応こっちでも書きます。まず問題を言い換えます。頂点を通った回数だとわかりづらいので, ド⇔レ の辺を通った回数, レ⇔ミ の辺を通った回数, ..., シ⇔ド…

問題 code-festival-2015-final-open.contest.atcoder.jp 解法 絵がないと険しいので解説に丸投げします(ごめんなさい)。 CODE FESTIVAL 2015 解説 from AtCoder Inc. www.slideshare.net木 -> オイラーツアー -> 区間ごとに分けることが出来るじゃん, とい…