ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

AtCoder

ABC122 D - We Like AGC

D - We Like AGC 解法 問題文の条件を満たすためには、具体的にどのような部分文字列が含まれていてはダメでしょうか。NGパターンを列挙してみましょう。 3文字のNGパターン もちろん AGC はNGです。また、隣り合う2文字を入れ替えて AGC となる GAC と ACG …

AGC031 C - Differ by 1 Bit

C - Differ by 1 Bit 解法 コンテスト本番で私が考察・実装した方針を書いていきます。公式解説とは実装の方針が異なっていて、公式解説のほうが恐らく楽な実装だとは思いますが、ACを得るまでの1つの過程として参考になればと思います。 YES/NO判定 まずは…

AGC031 B - Reversi

B - Reversi 解法 まず、1つ性質を確認しておきます。それは「石の色を塗り替える操作について、両端と同じ色を間にも含むような区間に対する操作は考えなくても良い」ということです。具体的には以下の図の上側に示すような操作です。このような操作は下側…

早稲田大学プログラミングコンテスト2019 I - Ramen

I - Ramen 解説を見て通したけど、実装にけっこう手こずったので記録。 解法 距離の2乗をコストに持つDP、といえばCHTです(?)。CHT(Convex-Hull Trick)が使えるように、価格 の計算式を と変形します。 が についての一次式群から最小値を求める形式に…

早稲田大学プログラミングコンテスト2019 F - RPG

F - RPG 解法 「全ての頂点に対し、頂点 からのパスと、頂点 へ向かうパスが存在する」「閉路がない」という制約から、無駄な辺/頂点はないということが分かります。具体的には全ての パスを考えた時、全ての辺/頂点についてそれを通る パスが存在し、さらに…

早稲田大学プログラミングコンテスト2019 E - Artist

早稲田大学プログラミングコンテスト2019 - AtCoder 解法 まず気付くべき点は、行の区切り位置と列の区切り位置を独立に考えられることです。行・列ともに、それぞれの区切り位置を境として黒いマスの個数が反転します。 そのためまずは行(列も同様)ごとの…

早稲田大学プログラミングコンテスト2019 D - Choose Your Characters

D - Choose Your Characters 解法 条件を満たしている区間はさらに伸ばしても必ず条件を満たすので、しゃくとり法が使えます。上手くしゃくとり法ができるように工夫をしましょう。 しゃくとり法では自キャラのほうを区間に入れたり出したりするので、それに…

早稲田大学プログラミングコンテスト2019 C - Permutation City

C - Permutation City 解法 木にする まずはグラフの形を簡単にします。距離に関する条件が「1または2である」ということ、そして「条件を満たす順列は必ず存在する」と書かれていることから、 連結性を保ったままいくつかの辺を削除しても、変化後のグラフ…

ABC121 D - XOR World

D - XOR World 解法 「 について○○を計算した合計を求めよ」という問題で使える実装テクニックとして、代わりに「 について○○を計算した合計」から「 のうち○○を計算した合計」を引いたものを求めると考えると、変数が減る上に同じ処理を2回すれば良いだけに…

ABC120 D - Decayed Bridges

D - Decayed Bridges 解法 グラフの連結性を考えるのに便利な道具として Union-Find木 があります。Union-Find木では「辺を追加して頂点同士を連結にする」という操作が可能ですが、対して今回の問題は「辺を削除して頂点同士を分断する」という操作になって…

みんなのプロコン2019 決勝 A - Affiches

A - Affiches オンサイトで解けなかった問題…ザ・数学。 解法 公式解説と少し違う方法で考えたので、その解法を書きます。 大きな長方形の中にある1点 を考えます。この点が2つの小さな長方形両方に入っている確率を考えます。 小さな長方形の置き方は1枚目…

AtCoder World Tour Finals 2019 B - Multiple of Nine

B - Multiple of Nine 解説ACしたので、自分の理解のためにも公式解説よりも少し詳しい解説を書いていきます。 区間の条件を累積和の条件に落とし込む 「非負整数を9で割った余りは10進数での桁和を9で割った余りと等しい」という基本的な事実は前提とします…

全国統一プログラミング王決定戦本戦 解説(C~E)

今回はオンサイト参加でした! 成績は200人中46位。なかなか健闘したんじゃないでしょうか。 参加記はまた気が向いたら別記事で書きます。この記事ではいつものように問題解説を。 現在Eまで書いていますが、Fは後日追記したいと思っています。G以降はまだ通…

みんなのプロコン2019 参加記録&解説

今回は5完!かなり健闘したとは思いますが、それでも赤パフォは取れず。厳しい世界。 問題数が多いので、Cから解説します。 C - When I hit my pocket... C - When I hit my pocket... 解法 まず、ビスケットを「普通に叩いて増やす」のと、「円を介して増や…

Xor Sum Editorial解法の「解説の解説」

D - Xor Sum 重み付き配点のABCで出された問題としては最強候補の1つと言われている「Xor Sum」。ビット単位のXOR演算と整数の足し算の密接な関係を利用した問題で、様々な解法が考えられています。こちらの記事ではいくつかの解法がまとめられています。 Xo…

ABC117 参加記録&解説(C, D)

2WAを出して169位…今回は良くなかったですね。 取り急ぎC, Dの解説を。あとで書き直すかもしれません。→書き直しました(02/04) C - Streamline C - Streamline 解法 ※訪れるべき地点 のことを「目的地」と書くことにします。 コマ数 が訪れるべき目的地の…

NIKKEI Programming Contest 2019 参加記録&解説(A~E)

Dまでがまずい感じでしたが、無事Eを通して予選突破! A~Eの5問を振り返ります。 A - Subscribers A - Subscribers 解法 最大値については、新聞 を取る人をなるべく被らせたいので が答えです。 最小値については、新聞 を取る人をなるべく被らせたくない…

ABC116 解説

AtCoder Beginner Contest 116 - AtCoder こどふぉと被っていたので参加しませんでした… A - Right Triangle A - Right Triangle 解法 三角形の面積は(底辺長)×(高さ)÷2ですね。直角三角形の場合、底辺長と高さは直角を挟む2辺の長さと考えることができ…

DDCC2019 参加記録(コード部門)&解説(A, B, D)

今回はオンサイト参加でした! コード部門以外のもろもろ参加記はまた別途書こうかなと思っています。この記事ではいつものように問題の解説を。 本番はAB2完でしたが…A, B, D問題について書きます。 A - レース (Race) A - レース (Race) 解法 連続した氷マ…

KEYENCE Programming Contest 2019 参加記録&解説

まあまあの速度で4完。Eは解きたかった… 本番後に通したEも含めて5問解説します。→Fも書き足しました。 A - Beginning 解法 ソートして 1479 になるかどうかチェックするのが一番楽です。 ACコード (Ruby)Submission #3998262 - KEYENCE Programming Conte…

AISing Programming Contest 2019 参加記録&解説

AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019 - AtCoder 全完! 2000未満ratedコンテストだったのでパフォーマンスは付かず、ちょっと残念。 A - Bulletin Board A - Bulletin Board 解法 縦の位置が 通り、横の位置が 通…

AGC030 B - Tree Burning

B - Tree Burning 今回は私自身がAB2完で実質的にこの1問しか解説を書けないのと、この1問だけでかなり説明が長くなりそうなので、単独記事にします。 Twitter見ていると微妙に色々違う解法があるようで…?私が本番で考察した内容をベースに書きます。他の人…

CADDi 2018 参加記録&解説(C~E)

2問速解きでレート微増。悪くはないけど良くもない。 C - Product and GCD C - Product and GCD 解法 各素因数ごとに考えてみます。 ある素数 について、各 ごとに「 には素因数としていくつ が含まれているか?」を考えます。その個数の最小値を とすると、…

AGC029 参加記録&解説(A~D)

AtCoder Grand Contest 029 - AtCoder 今回は4完!完答数で言うと自己ベストです。配点が低めでペナルティ込みの時間がかなり遅いので、パフォーマンスはそんなに高くないですが… A~Dを振り返ります。 A - Irreversible operation A - Irreversible operati…

ABC115 参加記録&解説

19分台全完で25位。20分切れたのは良いですね。 A - Christmas Eve Eve Eve A - Christmas Eve Eve Eve 解法 入力が4通りしかないので全部ifで分岐してもよいのですが、まず Christmas を出力して、 回だけ [半角スペース]Eve を出力するとスマートです。 AC…

ABC114 参加記録&解説

CもDも手間取ってしまい54位… A - 753 A - 753 解法 ifや3項演算子などで場合分けしましょう。 ACコード (Ruby)Submission #3700911 - AtCoder Beginner Contest 114 (C++)Submission #3708253 - AtCoder Beginner Contest 114 B - 754 B - 754 解法 の…

HACK TO THE FUTURE 2019 本選オープン 参加記録

HACK TO THE FUTURE 2019 本選オープン - AtCoder オープンコンテスト3位! 解説というほどのものは書けないので、「こんな感じのことをしました」というのをつらつら書いていく感じになります。 最初に考えたこと 中盤まではスキルに投資することが重要だが…

CODE FESTIVAL 2018 Final (Parallel) 参加記録&解説(A~F)

オープンコンテスト8位でした。 A~Fについて書きます。この記事を書いている時点で解説が公開されていないため、Twitterなどで見た他の参加者さんの解法を大いに参考にしながら書いています。 A - 2540 A - 2540 解法 長さが と の2本の辺で、ちょうど1つの…

ABC113 参加記録&解説

AtCoder Beginner Contest 113 - AtCoder 22分台全完で21位でした。 A - Discount Fare A - Discount Fare 解法 を計算して出力すればよいです。 ACコード (Ruby)Submission #3531033 - AtCoder Beginner Contest 113 B - Palace B - Palace 解法 個の地点…

ARC091 F - Strange Nim

F - Strange Nim 面白い問題だったので記録。公式解説とはちょっと違う解法。 考察・解法 実験と観察 山同士は相互に干渉しないので、それぞれの山のGrundy数を求めることが目的になる。 注目している1つの山について、残っている石の数を 、その山が持つパ…