はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミング

1 or 2 [AtCoder Beginner Contest 126 E]

https://atcoder.jp/contests/abc126/tasks/abc126_e 前提知識 Union Find 解説 https://atcoder.jp/contests/abc126/submissions/5476491入力には矛盾が無いということが使える。 あるiについて、Axi+Ayi+Ziが偶数であることが分かるとき、xiとyiに辺を張る…

Even Relation [AtCoder Beginner Contest 126 D]

https://atcoder.jp/contests/abc126/tasks/abc126_d 解説 https://atcoder.jp/contests/abc126/submissions/5477114以下のルールで着色していく。 辺の長さが偶数なら2つの頂点は同じ色で着色する。 辺の長さが奇数なら2つの頂点は異なる色で着色する。 こ…

Dice and Coin [AtCoder Beginner Contest 126 C]

https://atcoder.jp/contests/abc126/tasks/abc126_c 解説 https://atcoder.jp/contests/abc126/submissions/5476041シミュレーションしながら、答えを導いていこう。 サイコロで[1,N]のどれが出るかを全探索しよう。 そこから、コインを振って、得点が倍に…

YYMM or MMYY [AtCoder Beginner Contest 126 B]

https://atcoder.jp/contests/abc126/tasks/abc126_b 解説 https://atcoder.jp/contests/abc126/submissions/5475422上2つを数値にしたものをa, 下2つを数値にしたものをbとする。 この変換は数字-'0'をすると、文字を数値化できることを利用する。 あとは、…

Changing a Character [AtCoder Beginner Contest 126 A]

https://atcoder.jp/contests/abc126/tasks/abc126_a 解説 https://atcoder.jp/contests/abc126/submissions/5474925Aをaに変換することを考える。 A + x = a x = a - A という感じにAにxを足すとaにできる。 この関係はBからb, Cからcも同様であるため、こ…

Last Stone Weight II [LeetCode 1049]

https://leetcode.com/contest/weekly-contest-137/problems/last-stone-weight-ii/N個の石があり、それぞれの重さがわかっている。 2つの石を選んでぶつけるという操作をできなくなるまで行う。 ぶつけると、 同じ重さであれば、2つとも消滅 差があれば、差…

Longest String Chain [LeetCode 1048]

https://leetcode.com/contest/weekly-contest-137/problems/longest-string-chain/N個の文字列がある。 文字列Aのどこかにちょうど1文字加えることで文字列Bになる → AはBのpredecessorと言う。 N個の文字列から何個か取って並べるとする。 それが、S1, S2,…

Remove All Adjacent Duplicates In String [LeetCode 1047]

https://leetcode.com/contest/weekly-contest-137/problems/remove-all-adjacent-duplicates-in-string/文字列Sが与えられる。 隣り合う文字が等しければその2文字を消すという操作をできなくなるまで行う。 最終的にできる文字列はどうなるか。 なお、最終…

Last Stone Weight [LeetCode 1046]

https://leetcode.com/contest/weekly-contest-137/problems/last-stone-weight/N個の石があり、それぞれの重さがわかっている。 最も重い2つの石をぶつけるという操作をできなくなるまで行う。 ぶつけると、 同じ重さであれば、2つとも消滅 差があれば、差…

AB Substrings [diverta 2019 Programming Contest C]

https://atcoder.jp/contests/diverta2019/tasks/diverta2019_c 解法 https://atcoder.jp/contests/diverta2019/submissions/5348793文字列中にABがあれば順番にかかわらず含まれるので、そこを最初に数えておこう。 そのついでに先頭がBの個数topB、末尾がA…

RGB Boxes [diverta 2019 Programming Contest B]

https://atcoder.jp/contests/diverta2019/tasks/diverta2019_b 解説 https://atcoder.jp/contests/diverta2019/submissions/5345023b=N-r-gであるため、r,gが決まればbも決まる。 よって、r,gを全探索することで、候補となる(r,g,b)を列挙できる。 候補が条…

Consecutive Integers [diverta 2019 Programming Contest A]

https://atcoder.jp/contests/diverta2019/tasks/diverta2019_a 解説 https://atcoder.jp/contests/diverta2019/submissions/5345104若干実験するとN-K+1が答えであると分かるので、答える。 int N, K; //-------------------------------------------------…

ox Concatenation [CPSCO2019 Session4 E]

https://atcoder.jp/contests/cpsco2019-s4/tasks/cpsco2019_s4_e 解説(部分点解法) https://atcoder.jp/contests/cpsco2019-s4/submissions/5285574以下に疑似満点解法もあるが、こちらも紹介。 まずは、自明なNoパターンを弾いておこう。 「ox,xo,o,xの…

Boring Sequence [CPSCO2019 Session4 D]

https://atcoder.jp/contests/cpsco2019-s4/tasks/cpsco2019_s4_d 前提知識 二分探索 解説 https://atcoder.jp/contests/cpsco2019-s4/submissions/5285258二分探索で解く。 二分探索系は、二分探索に気づくまでが長くて大変だが、頑張ってとしか言えない。 …

Make a Team [CPSCO2019 Session4 C]

https://atcoder.jp/contests/cpsco2019-s4/tasks/cpsco2019_s4_c 前提知識 しゃくとり法 解説 https://atcoder.jp/contests/cpsco2019-s4/submissions/5285187まず入力がソート可能なので、とりあえずしておこう。 どこから考えていこうかという感じだが、…

Meeting [CPSCO2019 Session4 B]

https://atcoder.jp/contests/cpsco2019-s4/tasks/cpsco2019_s4_b 解説 https://atcoder.jp/contests/cpsco2019-s4/submissions/52850482日を選んで会議をするが、その選び方を全探索する。 a日目とb日目の少なくともいずれかに出席可能な社員の人数が知りた…

Swimming [CPSCO2019 Session4 A]

https://atcoder.jp/contests/cpsco2019-s4/tasks/cpsco2019_s4_a 解説 https://atcoder.jp/contests/cpsco2019-s4/submissions/5284961まず、一周2Lメートルなので、X mod 2Lを考えることにしよう。 X mod 2LはXを2Lで割ったあまりのことで、X=a*2L+bと書け…

総神童数 [yukicoder No.827]

https://yukicoder.me/problems/no/827 解説 https://yukicoder.me/submissions/345150全探索対象を変えて数え上げるテクを使おう。 問題では順列をN!通り考えて、順列で神童数をそれぞれ数えて総和を取っている。 これを頂点をN通り考えて、その頂点が神童…

連絡網 [yukicoder No.826]

https://yukicoder.me/problems/no/826 前提知識 BFS 解説 https://yukicoder.me/submissions/345147BFSをして、到達可能性を判定していくやつをやろう。 まず状態はN個でいいとして、問題が遷移数である。 N≦10^6なので、下手にやるとTLEしそうな感じがある…

賢いお買い物 [yukicoder No.825]

https://yukicoder.me/problems/no/825 解説 https://yukicoder.me/submissions/345142不確定な要素を全て全探索しよう。 不確定な要素は「商品の金額」「使った1G硬貨枚数」「使った10G硬貨枚数」であり、 これを全て全探索してもTLEせずに間に合う。 お釣…

Darker and Darker [AtCoder Grand Contest 033 A]

https://atcoder.jp/contests/agc033/tasks/agc033_a 前提知識 幅優先探索 解説 https://atcoder.jp/contests/agc033/submissions/5269426シミュレーションをしよう。 効率的にシミュレーションをするために幅優先探索として行う。 操作では「隣接のマスに黒…

通学路 [いろはちゃんコンテスト Day2 G]

https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_g 前提知識 ダイクストラ 解説 https://atcoder.jp/contests/iroha2019-day2/submissions/5215078ダイクストラをやる。 (到達している駅, 手にしている花)を状態として、コストは使ったお…

連呼 [いろはちゃんコンテスト Day2 E]

https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_e 解説 https://atcoder.jp/contests/iroha2019-day2/submissions/5214793数えやすい方を数えよう。 AAAを連続する部分文字列に持つ組み合わせではなく、持たない方の組み合わせを考えてみ…

EllysPearls [2019 Topcoder Open Algo 1B Hard]

N個の真珠がある。 i番目の真珠の色はpearls[i]であり、1~Mである。 ある真珠を抜き出して、ある箇所に差し込むという操作を行う。 同色の真珠は連続して並んでいる状態にしたい。 操作の最小回数は?1≦N≦50 1≦M≦15 解説 問題を少し読み替える。 今回の問題…

EllysSki [2019 Topcoder Open Algo 1B Easy]

N個の山がある。 高さは順にH[i]である。 ある山からスタートして、左か右かにスキーで降りていく。 高さが同じか低いなら降りられる。 途中で方向は変えられないとき、一回の滑降で最高何個の山を通れるか。1≦N≦50 1≦高さ≦1000 解説 全探索する。 自分は+1…

楽しすぎる家庭菜園 [いろはちゃんコンテスト Day2 D]

https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_d 前提知識 最小全域木 解説 https://atcoder.jp/contests/iroha2019-day2/submissions/5214486これは一般的な話だが、ある問題を見たときに今まで解いた類題が思い出せれば、 そこから似…

陽気な妖姫 [いろはちゃんコンテスト Day2 C]

https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_c 前提知識 座標圧縮 解説 https://atcoder.jp/contests/iroha2019-day2/submissions/5214368大小関係を維持したまま、配列の数字を変えて総和を最小化する問題。 これは座標圧縮をすれば…

わたのはら [いろはちゃんコンテスト Day2 A]

https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_a 前提知識 動的計画法 解説 https://atcoder.jp/contests/iroha2019-day2/submissions/5214346問題を読み替えよう。 どの長さqの部分列も、他の歌の部分列でない。 つまり、最長の共通部…

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

https://atcoder.jp/contests/iroha2019-day1/tasks/iroha2019_day1_l 前提知識 二分探索 SparseTable 解説 https://atcoder.jp/contests/iroha2019-day1/submissions/5197060ソートしてK番目の数がなんであるかという問題なので、いつもの二分探索をやる。 …

ルーレット [いろはちゃんコンテスト Day1 K]

https://atcoder.jp/contests/iroha2019-day1/tasks/iroha2019_day1_k 解説 https://atcoder.jp/contests/iroha2019-day1/submissions/5196729まず、各円盤では独立に確率が決められている。 真面目に計算するのではなく、線形性などをうまく利用するのだろ…