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

問題 https://www.facebook.com/hackercup/problem/1640119959603837/ 解法 まず, はしごを座標順にソートして, よくある stack のアレを使います。 mayokoex.hatenablog.com この記事のテクニックを使えば, O(N) であるハシゴからどこまで蛇が繋がれるのか…

問題 https://www.facebook.com/hackercup/problem/1627951250755660/ 解法 まず, C[n][k] = (n 枚のコインを投げた時 k 枚表が出る確率) を求めます。これはコンビネーションの nCr を求めるのと同じような dp で出来ます。 問題で必要になるのは C[n] = (n…

Facebook Hacker Cup 2016 Round 2 に参加しました。Round 3 に進めないのは仕方ないですが T シャツもらえないのは残念。 問題 https://www.facebook.com/hackercup/problem/424794494381569/ 解法 左側と右側, どこで区切るかで場合分けします。i 番目まで…

なんか早解き出来ない… 問題 TopCoder Statistics - Problem Statement 解法 問題の条件を考えると, 例えば k = 2 の時は, 0, 3, 6, 9, ... 番目の preference に関連性があり, 1, 4, 7, 10, ... 番目の preference に関連性があり, 2, 5, 8, 11, ... 番目の…

SRM 488, やたらと boring が出てくるけど競プロer が「頭悪い」って言うのと似た空気を感じる。 問題 TopCoder Statistics - Problem Statement 解法 以前に似たような問題を解いています。 mayokoex.hatenablog.comB の 2 つの連続部分文字列 C, D では, C…

問題 TopCoder Statistics - Problem Statement 解法 よくわからないので, とりあえずいろいろ実験するためのコードを書きます。 ll bag[5]; int main() { cin.tie(0); ios::sync_with_stdio(false); ll N; cin >> N; bag[0] = N; bag[1]++; ll cnt = 1; whi…

だいぶ頭悪かったかも… 問題 TopCoder Statistics - Problem Statement 解法 やるだけなんですが, だいぶ頭が悪かったです。map を作るところまでは良いと思いますが, あとは vector<string> ones = {"","I","II","III","IV","V","VI","VII","VIII","IX"}; vector<string> te</string></string>…

問題 TopCoder Statistics - Problem Statement 解法 1 ラウンドの終わり方は 9 種類あります。(F が J を kill した後 B に kill される… etc)それぞれの回数を p1, p2, ..., p9 とすると, scoreJ, killedJ, ... がその値によって一意に決まります。p1 〜 p…

問題 TopCoder Statistics - Problem Statement 解法 pekempey さんの解法を参考にしました。 pekempey.hatenablog.com凸多角形は上側と下側に分けることができ, 上側の頂点では, 座標を時計回りに見ていった時, 今見ている頂点 p と次の頂点 q について, (p…

問題 TopCoder Statistics - Problem Statement 解法 dp[n][m] = (退屈な人が n 人, そうでない人が m 人である際に, すべての人が 退屈になるのにかかる時間) とすると, 以下のような漸化式が成り立ちます。dp[n][m] = ((1+dp[n][m]) + (1+dp[n+1][m-1]) + …

問題 TopCoder Statistics - Problem Statement 解法 まず, t9 の各文字列の k 文字目までを作るのにかかるコストを計算します。 これには, t9 の各文字列 s について, s の k 文字目以下の番号(問題文の D というやつ) が一致しているやつを列挙し, それら…

問題 TopCoder Statistics - Problem Statement 解法 問題の制約から, x 方向, y 方向にずらす候補 dx, dy はそれぞれ -80 から 80 までしかありません。dx, dy としてあり得るものをすべて調べて, それぞれの場合に重なる線分の長さがどれだけになるかを調…

問題 TopCoder Statistics - Problem Statement 解法 count[i][j] から, cnt[i][j] = (別のバッグから j というカードを取り出した時, バッグ i から あるカード k を取り出して j + k が Good な数になるような場合の数) を作ります。j+k の候補がたかだか …

SRM 679 に参加しました。easy がめっちゃ簡単だったんですが英弱パワーを発揮して点数が低かったです。 問題 木構造になっている社員関係が与えられる。各社員 v は, productivity[v] - salary[v] だけの利益を挙げられる。利益を最大化するために社員を首…

問題 TopCoder Statistics - Problem Statement 解法 実際の迷路は無限に縦に続いていますが, 入力で与えられる一つの迷路のことを「パターン」と呼ぶことにします。まず, r1 と r2 が同じパターンに属する場合を考えます。一つ注意というか, そこがこの問題…

問題 codeforces.com 解法 適当に書いたら通ってしまったという感じ(解説を見ると writer もいろいろ解法ありそうと思っていたようです)なので証明も何もないんですが, やったことを書きます。素数の limit 番目まで使う, と決めた時, どのような整数集合が…

問題 codeforces.com 解法 集合 A から, D 円以内で交換できる品の集合 B があるなら, 集合 A から集合 B にシフトしていく, というのを貪欲にやっていけば良いです。集合 A と集合 B に同じ品の集合 C がある可能性がありますが, その場合は, A\C, B\C を交…

問題 codeforces.com 解法 長方形 (x, y, z, t) における要素の和は, (s の x, y における和) * (s の z, t における和) となります。なので, あらかじめ s の和が合計 b になるような場合の数を列挙して, a != 0 の時は, a = b*c となる b, c の候補を列挙…

IOI 問題 TopCoder Statistics - Problem Statement 解法 IOIString でない string の数を数えることにします。まず, 全部 O で構成されているような string は IOIString ではないです。 また, I がひとつだけ存在する string も IOIString ではないです。 …

問題 TopCoder Statistics - Problem Statement 解法 roads[i][j] == 'Y' だったら頂点 i と頂点 j の間に辺を貼ってみます。すると, それによっていくつかの連結成分が出来ます。その連結成分の中に, 次数が 3 以上の頂点 v があると, v に 2 回以上通らな…

問題 TopCoder Statistics - Problem Statement 解法 石を置く場所を o, 置かない場所を x とすると, ooxxooxxoo ooxxooxxoo xxooxxooxx xxooxxooxxのように, 2 マスおきに見た時市松模様っぽくなるようにするのが最適です。理由を考えてみます。単純な問題…

問題 https://www.facebook.com/hackercup/problem/798506286925018/ 解法 dp[now][num] = (now 個目の問題がコンテストの num 問目で使われる時の追加すべき問題の最小値) という dp をやります。D[now] > 100-(3-num) だと, コンテスト最後の問題の難易度…

問題 https://www.facebook.com/hackercup/problem/1424196571244550/ 解法 制約が 2^K となっていますが, この制約により, この問題のトーナメント方式は, 普通のトーナメント方式と同じであることがわかります(下図)。 そうすると, dp[state][i] = (選手 i…

Yattaze。 問題 https://www.facebook.com/hackercup/problem/512731402225321/ 解法 ある区間 [a, b] における余りが [c, d] となるとすると, あまりの期待値は (c+d)/2 で, 区間の幅 b-a と掛け算すると, (b-a)*(c+d)/2 となります。この掛け算した値のこ…

Facebook Hacker Cup 2016 Round 1 に参加しました。結果は x-oo で, 今回は 30pt 以上あれば良いらしいので Round 2 に行けるみたいです。やったぜ。 問題 https://www.facebook.com/hackercup/problem/1611251319125133/ 解法 貪欲にやっていきます。まず,…

問題 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) に変換します。すると, ある点からのマンハッ…

問題 TopCoder Statistics - Problem Statement 解法 ある整数集合 S について, S の任意の要素 el がすべての実験で同じ switch の入力をするとすると, それらのスイッチはどうやっても区別することは出来ないので, 「すべての実験で同じスイッチの入力をす…

450pt だったけど確かにこれは簡単。 問題 TopCoder Statistics - Problem Statement 解法 二分探索でやります。ok(x) = (C 回カットした後の K 番目の数が x 以上になるような切り方が存在するか) というチェック関数を作れればハッピーです。sticks[i] が …