AtCoder
問題 jag2015summer-day2.contest.atcoder.jp 解法 見た目からわかるように bitDP で解きます。dp[state] = (今暗い部屋のうち state で表される部屋にいる可能性がある場合の, 最小移動距離) とします。すると, 各部屋から i 番目の部屋に移った時の次の状…
問題 jag2015summer-day2.contest.atcoder.jp 解法 逆からたどっていく感じでやります。"ABC" という文字列を見つけたら, それを "A" "B" "C" のいずれかに変換する, ということを繰り返して, 最終的な文字列が "ABC" になったら勝ちです。ただし, 例えば "A…
問題 jag2015summer-day2.contest.atcoder.jp 解法 二分探索をします。ok(x) = (x 以下の数のうち, N 回目の操作で選ばれる数があるか) という判定をします。この判定ができると, 結局のところ求めたい x というのは ok(x) が true になるような数の中で最小…
問題 arc044.contest.atcoder.jp 解法 せっかくなので部分点解法も載せておきます。d[t][x][y] = (時刻 t に座標 x, y にいるときの最短距離) というようにすると, d[0][x][y] = 0 をスタートにしてダイクストラすれば答えが求まります。で, 満点解法です。…
ARC 044 に参加しました。 B が難しかったせいか, C の部分点取るだけで結構上位にいけました。いや上位とっても解けないと意味無いですけど。 D は言われてみるとかなり簡単だったので C 捨てて考えても良かったかも。 問題 arc044.contest.atcoder.jp 解法…
問題 tenka1-2015-final-open.contest.atcoder.jp 解法 kmjp さんの解説を参考にしました。kmjp.hatenablog.jp 得た知見 「全部やる」みたいな問題で実際に全部やるのは無理なので, 問題を小分けにする 今回の場合は「全部やる」 = 「すべての順列を試す」, …
問題 tenka1-2015-final-open.contest.atcoder.jp 解法 LCA とオイラーツアーを使えば解くことが出来ます。まずオイラーツアーしてそれぞれの頂点が最初に現れる場所(下のソースコードで言うと BEGIN)を覚えておきます。すると, クエリで与えられる M 個の頂…
SRM div1 med っぽい雰囲気。 問題 D: 引っ越し - AtCoder Regular Contest 043 | AtCoder 解法 スライド通り。 AtCoder Regular Contest 043 解説 from AtCoder Inc. www.slideshare.net const int MAXM = 1010; const ll INF = 1ll<<60; int P[MAXM]; int …
本番中解法全く思い浮かばなかったのは問題だけど, 朝からちょくちょくデバッグして 15 時にようやく AC する程度に実装力がないので解けなかった気がする。 問題 C: 転倒距離 - AtCoder Regular Contest 043 | AtCoder 解法 スライド通りです。 AtCoder Reg…
満点解法書いてみてなんとなく理解したので書きます。ソースコードは解説コードに少し説明を加えただけです。 問題 G: おおきなかずを作った (I made a huge number) - 技術室奥プログラミングコンテスト | AtCoder 解法 基本的な方針は以前書いたものと変わ…
技術室奥プログラミングコンテストに参加しました。ABCDEだけ解くという普通の人でした。 蟻本の chapter 4 (上級編)まともに読んでないので suffix array とか言われてもさっぱりで, 満点解法を紹介するのは時間がかかりそうなのでとりあえず部分点解法だけ…
倍々ゲームからバイバイ(激寒)。 問題 C: 倍々ゲーム - AtCoder Beginner Contest 027 | AtCoder 解法 スライドと言っていることは本質的に同じですが, 試行錯誤の仕方は違ったのでそっちを紹介したいと思います。2 倍とか言っているところがビットっぽいの…
ぐぬぬ… 問題 D: ロボット - AtCoder Beginner Contest 027 | AtCoder 解法 スライドがわかりやすいのでほとんどそのままです。 abc027 from AtCoder Inc. www.slideshare.net一応すこし補足すると,最終的な答えがソートした際の(後半そのまま) - (前半その…
解説(http://tenka1.klab.jp/2015/explain/quala_d.html)微妙に違うような…「葉」の解釈にもよるけど。 問題 D: ハシポン - 天下一プログラマーコンテスト2015予選A | AtCoder 解法 概ね解説のとおりなのですが,「葉」と書いてあるところは「次数1の頂点」と…
天下一プログラマーコンテスト2015予選Aに参加しました。天下一完でした。別に予選通過できるとは思ってないけどもうちょっと解けないかなぁ… 問題 C: 天下一美術館 - 天下一プログラマーコンテスト2015予選A | AtCoder 解法 基本的に,AとBで一致している部…
これは知らなかったので仕方ない… 問題 D: 旅行会社高橋君 - AtCoder Regular Contest 039 | AtCoder 解法 解説(AtCoder Regular Contest 039 解説)の通り。実装について簡単に説明しておきます。最初の方に書いてあるvisitとかbridgeとかはこのページ(Spagh…
ARCに参加しました。結果はABだけ解いて（◞‸◟）でした。 問題 C: 幼稚園児高橋君 - AtCoder Regular Contest 039 | AtCoder 解法 解説(AtCoder Regular Contest 039 解説)の通り実装したつもりです。 毎回自分の位置を更新するたびに4方向の近傍が次にどこに…
部分点解法はできたはずなのにもったいない。 問題 D: 有向グラフと数 - AtCoder Regular Contest 038 | AtCoder 解法 基本的にこれを参考にしました。 http://www.slideshare.net/chokudai部分点解法は,ターン数がたかだか2*Nでも結果が変わらないのでゲー…
AtCoder Regular Contest 038に参加。B問題までしか解けませんでした…辛い… 問題 C: 茶碗と豆 - AtCoder Regular Contest 038 | AtCoder 解法 基本的なアイデア(grundy数とか)はこちらを参考にしました。 http://www.slideshare.net/chokudai 104点解法がよ…
問題:D: Big Bang - AtCoder Beginner Contest 022 | AtCoder解法:問題のような変換をしても重心から最遠点までの距離の比はPのままであるのでそれを計算して比べる。 以下ソースコード const int MAXN = 100100; int Ax[MAXN], Ay[MAXN], Bx[MAXN], By[MAXN…
ABC #022に参加。途中で抜けたとはいえABしか解けなかったのはひどい。問題:C: Blue Bird - AtCoder Beginner Contest 022 | AtCoder解法:0から出発して0に帰ってくるような閉路は, 0->a->...->b->0 というように0からaに出て行って何かを経由してからbに来…
良い問題だなぁ。TopCoderのMedに出題されそう。問題:D: Chaotic Polygons - AtCoder Regular Contest 037 | AtCoder解法:kmjpさんの解法(AtCoder ARC #037 : D - Chaotic Polygons - kmjp's blog)を参考にしました。の定義の仕方は同じです。 とりあえず場…
ARC037に参加。Bでバグらせてちょっと時間食いましたがいつも通りCまで通してまぁOKという感じでした。「いつも通り」とか言ってるけど最近Cが簡単だからじゃないですかね…問題:C: 億マス計算 - AtCoder Regular Contest 037 | AtCoder解法:まずAとBをソート…
データ構造の良い練習。問題:C: 山登り(Mountain Climbing) - KyurideKagamizProgrammingContest(Remixed by ryunosuKe & Kensuke) | AtCoder解法:各頂点ごとに,その頂点がグラフの葉であるなら山の頂点(頂点0)までの距離を格納しておき,セグメント木を使っ…
学校始まってだんだん解けなくなってきてますね…とりあえず1日2問目標にします。問題:D: 偶数メートル - AtCoder Regular Contest 036 | AtCoder解法:各頂点1つごとに2つずつ頂点を用意し,それぞれ赤色と青色とする。で,頂点aと頂点bの間に道を作る時, ・道…
解けなかったの悔しい。問題:C: 偶然ジェネレータ - AtCoder Regular Contest 036 | AtCoder解法:dp[pos][diff0][diff1]=(posの文字を見ている時点で(0の数-1の数)の最大値がdiff0,(1の数-0の数)の最大値がdiff1であるような場合の数)とすると,次の数が0か1…
たまによく見る。問題:E: Line up! - Indeedなう（オープンコンテストB） | AtCoder解法:目的の形にするためにはとにかく小さい数から順に左に詰めていかなければならない。それをBITとか使ってシミュレーションすれば良いだけ。 以下ソースコード const int…
本番何もわからずに通したけど,しっかりプリム法書いてて面白かった。問題:D: Game on a Grid - Indeedなう（オープンコンテストB） | AtCoder解法:すべてのマスが非負なので,点数を最大化するならとりあえずすべてのマスを通るのが良い。これで盤面に書いて…
回文判定はなんか浮いたことしちゃったのかも。問題:C: Palindrome Concatenation - Indeedなう（オープンコンテストB） | AtCoder解法:dp[n]=(n文字目までの最小コスト)とすると,dp[n]=min(dp[k]+(n-k文字の回文のコスト))という感じになる。これを高速で実…
問題:F: チェックディジット - 東京大学プログラミングコンテスト2014 | AtCoder解法:条件を満たすような関数を考えるために,f(s)=(文字列sについて,s[j] 以下ソースコード set<string> S, SS; int main() { int T; cin >> T; for (int i = 0; i < T; i++) { string </string>…
