ARMERIA

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

プログラミング

ABC122 D - We Like AGC

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

yukicoder No.803 Very Limited Xor Subset

No.803 Very Limited Xor Subset - yukicoder 解法 AtCoderに「Limited Xor Subset」という問題があります。この問題の想定解法は今回のyukicoderの問題とは全く違うものですが、この問題に対するこちらの別解がとても参考になります。私もコンテスト本番は…

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回すれば良いだけに…

Educational Codeforces Round 61 D. Stressful Training

Problem - D - Codeforces 問題概要 コンテスト参加者が使う 台のPCがある。 番目のPCの初期電池残量は で、消費速度は毎ステップ である。 初めに充電器の充電速度として非負整数 を決め、以下の処理を ステップ行う。 各ステップごとに、どのPCを充電する…

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で割った余りと等しい」という基本的な事実は前提とします…

Codeforces Round #540 F2. Tree Cutting (Hard Version)

Problem - F2 - Codeforces コンテスト単位の記事がなかなか書けずにこどふぉの記事をサボってしまっているので、比較的楽に書ける1問単位の記事も書いていこうと思います。ちょっと方向性模索中。 解法 同じ色の頂点を繋ぐ もし直接辺で繋がっていない頂点…

全国統一プログラミング王決定戦本戦 解説(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 解法 最大値については、新聞 を取る人をなるべく被らせたいので が答えです。 最小値については、新聞 を取る人をなるべく被らせたくない…

Educational Codeforces Round 59 参加記録&解説(A~D)

しばらくこどふぉの記事をサポってますね… A. Digits Sequence Dividing Problem - A - Codeforces 問題概要 以下の問題 個に答えよ。 からなる 文字の文字列が与えられる。この文字列を2つ以上の連続部分文字列に分解し、「それぞれの文字列を10進数の数値…

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 解法 縦の位置が 通り、横の位置が 通…

Hello 2019 (Codeforces) 参加記録&解説(A~D, F)

Dashboard - Hello 2019 - Codeforces 2019年最初のコンテストはABCDFの5完で111位!幸先いいですね。 A. Gennady and a Card Game Problem - A - Codeforces 問題概要 2文字の文字列でトランプのカードを表す。1文字目がランク、2文字目がスートに対応する…

AGC030 B - Tree Burning

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

Educational Codeforces Round 57 参加記録&解説(A~F)

猛プッシュ回。その真意はG問題にありましたが、私は解けませんでした… ※2019/01/16 E問題を追記。 A. Find Divisible Problem - A - Codeforces 問題概要 以下の問題 個に答えよ。 整数 が与えられる。 かつ かつ が の約数であるような整数 を1組求めよ。 …

Codeforces Round #529 参加記録&解説

Dashboard - Codeforces Round #529 (Div. 3) - Codeforces だいたい1時間で全完。平和なDiv3でした。 A. Repeating Cipher Problem - A - Codeforces 問題概要 ある文字列 に対して、各文字を「1文字目を1個、2文字目を2個…」と並べた文字列 が与えられる。…

Codeforces Round #528 参加記録&解説(A~D)

Dashboard - Codeforces Round #528 (Div. 1, based on Technocup 2019 Elimination Round 4) - Codeforces 配点の高いDを通し、なんとDiv1で81位!これはそうそう出るものじゃないですね。レートも爆上げ。 A~Dを振り返ります。Div2ではC~Fに対応します。…