ARMERIA

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

AtCoder

AtCoder Beginner Contest 126 F - XOR Matching

F - XOR Matching 解法 結論を書いてしまうと、以下のような数列がもし作れれば答えになります。 アイデアとしては、まず を挟んで 以外の数字を鏡写しに並べます。こうすることで 以外のどの数字を選んでも、2つの位置の間(両端を含む)にあるものは「 1個…

AGC033 B - LRUD Game

B - LRUD Game 解法 まず気付くべき点は、縦と横は独立に考えられることです。これは今回のゲームのルールが 盤外に落ちる条件が「縦座標が の範囲から外れること」または「横座標が の範囲から外れること」であること 縦座標と横座標が互いに影響し合わない…

diverta 2019 Programming Contest D - DivRem Number

D - DivRem Number 解法 この問題は「割り算して切り捨て」と「余り」の関連性に気付くととても考えやすくなります。実際、割り算して切り捨てたときに捨てられる部分は割った余りそのものです。 具体的に数式で表すと、 を で割った余りを とすると が成立…

AtCoder橙になりました

5月4日のAGCで、ついに橙になることができました!!! 初めてratedに参加したのが昨年の4月上旬なので、およそ1年と1ヶ月での到達となりました。今年中には橙になりたいと思っていたので、予想より遥かに早くてびっくりしています。 ということで記事を書き…

いろはちゃんコンテスト Day1 L - をあ ぷろぶれむ

L - をあ ぷろぶれむ 解法 初手は二分探索 この問題のように、 与えられた数列などから、列挙しきれない個数の要素(入力 個に対して 個など)を計算する。それらをソートしたときの 番目の値を求めよ。 という形式の問題では、二分探索が有効なことが多いで…

Tenka1 Programmer Contest 2019 F - Banned X

F - Banned X 気合いで数える問題。ARC-FやAGC-Dあたりの数え上げをやりまくったおかげで解けたかな…と思います。 解法 まず、全要素の合計が 未満かどうかで場合分けをします。 合計が 未満である場合 要素の合計が 未満である場合はどのように数を並べても…

Tenka1 Programmer Contest 2019 D - Three Colors

D - Three Colors 解法 三角形の成立条件は、3辺すべてについて「その辺の長さが、他の2辺の長さの合計より小さい」ことです。ただこれをそのまま扱おうとすると3辺全部の長さを管理しながらDPなどをする必要があり、難しそうです。 逆に三角形が成立しない…

AGC022 D - Shopping

D - Shopping この記事を書いている時点で、AGC-Dの中で配点が最も高い問題。私自身AGC-Dを全問通しましたが、ダントツで一番難しい問題だと感じました。解説ACをするのにも非常に苦労しました… この回は解説放送のアーカイブがなくて、解説記事も全然書かれ…

エクサウィザーズ 2019 E - Black or White

E - Black or White 解法 答えを定式化する 番目のチョコレートを食べ終わった直後に、 黒が残っている確率: 黒白どちらも残っている確率: とします。このとき黒だけが残っている確率は です。 番目に食べるチョコレートが黒であるパターンは、 番目のチョ…

エクサウィザーズ 2019 D - Modulo Operations

D - Modulo Operations 解法 単調減少列を考える まず気付くべき点は、「ある値 で余りを取ったあと、それより大きい値 で余りを取っても値は変化しない」ということです。 で余りを取った時点で黒板に書かれた値 は 以下になっていて、その より大きい値で…

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…