CODE FESTIVAL 2015 決勝 に参加しました。5 完最下位です。ABCDE で辛い思いをしていたら終わってしまって, あまりおもしろいところに食い込めなかったのが残念です。 問題 code-festival-2015-final-open.contest.atcoder.jp 解法 本番は脳筋遅延評価セグ…

問題 abc014.contest.atcoder.jp 解法 lca 使ってやるだけ。木構造では２つの頂点の距離が一意に決まるのが本質的? class Tree { public: Tree(int V, int root) : V(V), root(root) { T.resize(V); for (int i = 0; i < MAXLOGV; i++) parent[i].resize(V);…

問題 kupc2015.contest.atcoder.jp 解法 配列 B の後ろから順に対応する A の数字を決めていきます。今, B[i] に対応する A[j] を決定したいとすると, j は, まだ配列 B の要素とまだ対応していない j の中で, 一番右側にあるものを選べば良いです。これを高…

問題 kupc2015.contest.atcoder.jp 解法 計算の構文木を作って, その構文木を幅優先探索して得られる文字順を反転させると答えになります。例えば以下のような感じですね。 デバッグ用に計算結果も出力してくれます↓ int calcs(string s) { stack<int> X; int n =</int>…

こどふぇす予選問題全完出来ないのはまずそう。 問題 code-festival-2015-qualb.contest.atcoder.jp 解法 kmjp さんのコードを参考にして書きました。 解説に書いてあった通り, set で黒マスの区間を管理しながら答えを求めていけば良いです。S からスタート…

これは解けるべきだったんや… 問題 kupc2015.contest.atcoder.jp 解法 桁 DP するだけです。dp[n][diff][carry] = (n 桁目までの時点で X+N と X のビットカウントの差が diff で X+N のキャリーが carry となるような X の最小値)としてがんばります。 cons…

嘘解法っぽいけど通ってしまった。正当性あるんですかね。 問題 kupc2015.contest.atcoder.jp 解法 H > W と仮定します。とりあえず, 三角形の一つの頂点は長方形の頂点と一致し, 残りの頂点は長方形の辺と重なるようにあるはずです。 ということで, 以下の…

KUPC2015 に参加しました。 ABCDE 解いて 60 位くらいでした。うーん。 問題 kupc2015.contest.atcoder.jp 解法 方針としては, 最後に滞在する街で場合分けしてそれぞれの場合に得られるお金の最大値を求める, という感じで解きます。そのためには, 街 i に…

問題 abc030.contest.atcoder.jp 解法 python 多倍長最高で通します。 N, a = map(int, raw_input().split()) a -= 1 k = input() b = map(int, raw_input().split()) for i in range(N): b[i] -= 1 used = [-1]*N step = [-1]*N cur = a loop = 0 cnt = 0 w…

問題 dwango2015-honsen.contest.atcoder.jp 解法 dp[n][x][renzoku][f2] = (n 文字目の時点でニコニコ文字列が x 個あり, 25 という文字列が直前に renzoku 個続いていて, 直前の文字が 2 であるかどうかのフラグが f2 である場合に, 全体としてニコニコ文…

本番書いたコードがなぜ通っているのかよくわかってない。でも通れば正義。 今まで見た ARC B 問題の中では一番むずかしい気がします。 問題 arc045.contest.atcoder.jp 解法 解説の通りやってみました。 AtCoder Regular Contest 045 解説 from AtCoder Inc…

ARC 045 に参加しました。途中まで B も解けなくて死ぬかと思いましたがなんとか C まで解けました。 問題 arc045.contest.atcoder.jp 解法 xor の特徴からして, 頂点 v から 頂点 u までのパスにおける xor 和 = (頂点 0 から v までの xor 和) xor (頂点 0…

ぽよ〜 問題 code-festival-2014-morning-hard.contest.atcoder.jp 解法 dp で解けます。dp[n][x] = (n 番目の人が, もとの位置から x 以下だけずれた座標にいるような場合の数) とすると, n 番目の人は, p[n]+x-1 以下の座標にいるか, p[n]+x の座標にいる…

問題 code-festival-2014-morning-middle.contest.atcoder.jp 解法 貪欲法で解きます。右端ができるだけ左にあるものから採用するほうが最適です。ということで, アルゴリズム的には以下のようなことをやります。・a[i] が x[cur] 以下のもののうち, まだ使…

問題 code-festival-2014-qualb.contest.atcoder.jp 解法 stack でがんばります。まず, この問題では「右側に見える範囲」及び「左側に見える範囲」を別々に求められれば良いことがわかります。ということで, 右側に見える範囲を求めてみましょう。それがわ…

本当に Nim だった(grundy 数かもとも思っていたのだけれど) 問題 ttpc2015.contest.atcoder.jp 解法 実は, 「距離が奇数のものからの Nim」ということで解くことが出来ます。距離が奇数のもの全体の状態が (n1, n2, ..., nk) で表されるとしましょう。 まず…

問題 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 とします。 ま…

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

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

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

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

解けなかったけどこれも良い問題。 問題 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 解法 S に 5 種類より多い文字があるとサンプルにある通り奇数を対応…

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

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