競技プログラミング

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 ひとつずつ考えないで、増加した部分…