競技プログラミング

SRM 701 Div 2 Easy, Medium

https://apps.topcoder.com/wiki/display/tc/SRM+701 Easy シミュレート public class SquareFreeString { public String isSquareFree(String s) { for (int i = 0; i < s.length(); ++i) { for (int j = 2; i + j <= s.length(); j += 2) { String left = …

AtCoder Regular Contest 052 B : 円錐

arc052.contest.atcoder.jp 解法 典型的なRMQ問題(足すやつもMinimumっていうんでしょうか・・・)円錐を高さ1ごとにぶつ切りした体積を配列に持たせて、 それをSegmentTreeに入れてあげて更新作業をすれば、 あとはクエリーに答えていくだけ。計算量も事前…

AtCoder Regular Contest 052 A : 何期生?

arc052.contest.atcoder.jp 解法 数字の部分を取り出してくればよさそうなので、 JavaのStream機能を利用して解く。 String ans = sc.next().chars(). filter(a -> '0' <= a && a <= '9'). mapToObj(a -> Integer.toString(a - '0')). reduce("", String::co…

CODE FESTIVAL 2016 qual C : E - 順列辞書 / Encyclopedia of Permutations

code-festival-2016-qualc.contest.atcoder.jp予選落ちたのが大変悔しかったので、 ちょっと背伸びして普段じゃ絶対に解けないだろう、 最後の問題を解いてみた。 当初の方針 ちんぷんかんぷん 解法を見て ????自分に理解できるように噛み砕いていく。 …

CODE FESTIVAL 2016 qual C : D - Friction

code-festival-2016-qualc.contest.atcoder.jp 当初の方針 Cが解けなくてこちらに来る 部分点解法を狙おう うーん、O(H^4)にしかならない・・・ cost[i][y1][y2]はcost[i][y1-1][y2-1]の一番下しか違いがないことに気づく 再利用すればO(H^3)になるぞ でも実…

CODE FESTIVAL 2016 qual C : C - 二人のアルピニスト / Two Alpinists

code-festival-2016-qualc.contest.atcoder.jp青木君が東からやってくるの見落として 問題の意味を理解するまでとても時間がかかった 当初の方針 意味分からん。間違いがあればどのデータも信用ならないし、 答えが出ないのでは? 青木くんの存在に気づき、…

CODE FESTIVAL 2016 qual C : A B

code-festival-2016-qualc.contest.atcoder.jpこの人の出す問題嫌いついでにいうと人柄も嫌い A 前からのCの位置と、後ろからのFの位置を取得してチェックSubmission #943435 - CODE FESTIVAL 2016 qual C | AtCoder B 紙に書いてみると、毎回前のとは違う、…

AtCoder Beginner Contest 033 D : 三角形の分類

abc033.contest.atcoder.jp 当初の方針 幾何は苦手意識・・・。サンプルみたいに、直角と鋭角の数をカウントして、 全体から引けばいい?(うまくだまされました)グリッド上に配置されるから、直角になるには、 x座標かy座標かが一緒になる? (大嘘。(0,0)…

AtCoder Beginner Contest 033 A B C

abc033.contest.atcoder.jp A setに突っ込んで、1つだけかどうか判定Submission #937773 - AtCoder Beginner Contest 033 | AtCoder B 言われた通りにチェックSubmission #939333 - AtCoder Beginner Contest 033 | AtCoder C 一瞬「うげっ、構文解析?!」…

AtCoder Regular Contest 053 B : 回文分割

arc053.contest.atcoder.jp 解法 回文になるには、 偶数個のみで構成される文 偶数個と、1つの1文字で構成される文 であることが分かる。なので、まず文字ごとの出現回数をカウントし、 奇数を1と残った偶数に分解してあげる。 すると、1の個数と偶数の合計…

AtCoder Regular Contest 053 A : ドミノ色塗り

arc053.contest.atcoder.jp 解法 それぞれで、長さ-1コ分が連なっており、 重複はない。タテ:w * (h-1) [コ] ヨコ:h * (w-1) [コ]この2つを足せばいい。A: ドミノ色塗り - AtCoder Regular Contest 053 | AtCoder

AtCoder Regular Contest 054 B : ムーアの法則

arc054.contest.atcoder.jp 解法までの道のり 二分探索? → 普通に違う → やざてんさんより二分探索で解けるとご指摘いただきました! ページ下部で補足します。 3 が入力されるケースで、1e-9刻みでやってみると、下に凸な関数であることが分かる 最急降下…

AtCoder Regular Contest 054 A : 動く歩道

arc054.contest.atcoder.jp 解法 時計回りのときの距離は、c := (D - S + L) % L反時計回りのときの距離は、cc := (L - D + S + L) % Lで、それぞれX + Y[1/s]、Y - X[1/s]の速度で移動するので、 割って上げて、小さいほうを出力すればいい。X >= Y の場合…

AtCoder Regular Contest 055 B : せんべい

arc055.contest.atcoder.jp 当初の方針 ちょっと前に友達と一緒に学校で解いていた思い出が蘇る。そのときはさっぱりで、解説放送を見てもさっぱり。今もさっぱり。 解説を読んで ??????コードが書けるようになるまで丸一日費やした。他のブログでは独…

AtCoder Regular Contest 057 B : 高橋君ゲーム

arc057.contest.atcoder.jp 当初の方針 DP? →考えたDP:dp[N][K] Kが10^9ほどあるので無理 先頭から最小の勝利数で勝率が上がるような貪欲? 実装中に全部使い切らないと行けないケース ()でうまくいかない。 諦め 解法を読んで のケースは特殊化して省く…

AtCoder Regular Contest 057 A : 2兆円

arc057.contest.atcoder.jp 解法 K = 1のときは、n回試行するとになるので、 K >= 1のときは、シミュレーションしても間に合う(O(log 2兆)=12log 20)。K = 0のときは、n回試行すると、A + nになるので、 2兆円にするためには、2兆-A回試行する必要がある(O…

AtCoder Beginner Contest 034 D : 食塩水

abc034.contest.atcoder.jp 当初の方針 DP? でもwが大きいし・・・。分からない。 解説を読んで 二分探索。なるほど。その通りに実装してAC。Submission #935434 - AtCoder Beginner Contest 034 | AtCoderでも、なんでそれが正しいか分からない。 なぜ基準…

AtCoder Beginner Contest 034 A, B, C

abc034.contest.atcoder.jp A 比較して出力Submission #935373 - AtCoder Beginner Contest 034 | AtCoder B 偶数の人は一つ手前の人と、奇数の人は一つ後の人とペアになる。Submission #935372 - AtCoder Beginner Contest 034 | AtCoder C 整数論を用いる…

AtCoder Beginner Contest 046 D : AtCoDeerくんと変なじゃんけん / AtCoDeer and Rock-Paper

解法までの道のり DPかな? pを出す回数はたかだかn/2 ぎりぎり10^9を下回りACできそう 試しに配列を確保してみる → メモリエラー 他にいい方法がありそう。 ここまでで、サンプルケースを紙に書いてみる。gを出した回数だけpが使えるので、 pは最大n/2回(…

AtCoder Beginner Contest 035 D : トレジャーハント

abc035.contest.atcoder.jp 当初の方針 満点解法を狙いにいく。結局、どこかの節に最短で行って、できるだけ長く居て、最短で戻ってくればいい。 途中で寄った先に居る必要はない。ダイクストラ法で1から各節まで、逆順のリンクから各節から1までの最短経路…

Codeforces Round #377 (Div. 2) A, B, C, D

codeforces.com A kを足していって、10で割った余りが0かrになればいい。Submission #21523193 - Codeforces B 2つを足して、足りない分を後ろに足せばいい。n = 1のケースのときは、何もしなくていいらしい。これが分からない。出したやつがそういう実装に…

AtCoder Beginner Contest 046 C : AtCoDeerくんと選挙速報 / AtCoDeer and Election Report

abc046.contest.atcoder.jp 当初の方針 ううーん、難しそうだけど、式変形していけば良さそう。・・・詳細は省くが、整数論を持ち出してやっている途中で、 が素数でないと成立しないことに気づく。何故なら、モジュロ演算を行うときに逆元が必要になるのだ…

AtCoder Beginner Contest 046 A, B

abc046.contest.atcoder.jp間違えてABCに参加登録をしていたみたいで、 ARCに出られなかった。けど、Cが解けなかったのである意味助かった・・・。 Dまでくらい余裕で解けるようになりたいね。 A setに突っ込んで、sizeを出力Submission #928767 - AtCoder B…

AtCoder Beginner Contest 035 A, B, C

abc035.contest.atcoder.jp A 幅を4で割ってみて、その商を使って高さを割って3かどうかチェックSubmission #924362 - AtCoder Beginner Contest 035 | AtCoder B '?'のときは最大の場合、離れていき(マンハッタン距離+1)、 最小の場合、近づいていく(マ…

AtCoder Beginner Contest 036 D : 塗り絵

abc036.contest.atcoder.jp 当初の方針 DPだろうなあ・・・(定義が分かるとは言っていない2回目) 木だから、木の嬉しい性質を利用するのかな まず全探索。白か黒で遷移してチェック。これは2^10^5なのでダメ 両端が黒になるものを列挙して、残りの組み合わ…

AtCoder Beginner Contest 036 C : 座圧

C: 座圧 - AtCoder Beginner Contest 036 | AtCoder 解法 omuさんにJAG夏合宿のとき教えてもらったので余裕です!順序付きのSetを利用して、それをMapに落とし込む(0からカウントアップしていく)。このような典型テク(?)が出てくるのは嬉しい。Submissi…

AtCoder Beginner Contest 037 D : 経路

abc037.contest.atcoder.jp 当初の方針 DPだと思うけど、きれいな(for文で書けるような)漸化式が思いつかない。PriorityQueueを使えばトポロジカル順序ソートできるかな・・・? →重複除去とか、dp[i][j]に値を入れる方法が分からない・・・。 解説を見て …

AtCoder Beginner Contest 037 A, B, C

abc037.contest.atcoder.jp A 小さいほうをたくさん買えばいい。Submission #923925 - AtCoder Beginner Contest 037 | AtCoder B 言われた通りに書いて出力。Submission #923930 - AtCoder Beginner Contest 037 | AtCoder C 言われた通りに書く。しゃくと…

AtCoder Beginner Contest 038 D : プレゼント

abc038.contest.atcoder.jp 当初の方針(WA) ふつうにDPしたらO(N^2)になりそう。きっとO(N log N)解法。ソートして大きいやつから取っていけば良さそう → WASubmission #923373 - AtCoder Beginner Contest 038 | AtCoder 3 1 9999 1 1 2 2 のケースで落ち…

AtCoder Beginner Contest 038 A, B, C

abc038.contest.atcoder.jp A 最後の文字だけみて判定Submission #923339 - AtCoder Beginner Contest 038 | AtCoder B 全探索。頭が回らなくててこずるSubmission #923340 - AtCoder Beginner Contest 038 | AtCoder C ひとつずつ考えないで、増加した部分…