mini-notes

競技プログラミングの解法メモを残していきます。

CODE FESTIVAL 2014 Middle C - eject

問題:C - eject 解答:Submission #11256765 - CODE FESTIVAL 2014 Middle 解法:2項係数の問題、なんだけど浮動小数点の取扱いが難しい。 cmathのpowを使う、long doubleにする、でうまくいった。(リテラルちゃんとする、もあるかもしれない。)

Indeedなう(予選B)D - 高橋くんと数列

問題:D - 高橋くんと数列 解答:Submission #11255665 - Indeedなう(予選B) 解法:数字xについて愚直に(l, r)の組を数えることを考える。lごとに該当するrの数を数えるとする。 a[l] = x:r = l からnまでがxを含む部分列になる。 a[l] ≠ x:l' > lかつ a…

DigitalArts プログラミングコンテスト2012 B - Password

問題:B - Password 解答:Submission #11252972 - DigitalArts プログラミングコンテスト2012 解法:aもしくはz*20の場合は同じハッシュ値を持つパスワードがないのでNO。それ以外は次のように生成する。 ①1文字でa以外:1文字をXとすると(X -1)aの2文字と…

CODE FESTIVAL 2015 あさぷろ Middle B - ヘイホー君と削除

問題:B - ヘイホー君と削除 解答:Submission #11251025 - CODE FESTIVAL 2015 あさぷろ Middle 解法:文字列sをある場所を区切って文字列aとbに分割する。aで平方の前半、bで平方の後半を作るとする。このとき作れる平方文字の最大長はaとbのLCS(最長部分…

DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 B - ディスコ社内ツアー

問題:B - ディスコ社内ツアー 解答:Submission #11247515 - DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 解法:見ていく順番は一意に決まるので何周するかを求めればよいが、Nに関するループの繰り返しにするとTLE。 同じ…

DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 本選 B - DDPC特別ビュッフェⅡ

問題:B - DDPC特別ビュッフェⅡ 解答:Submission #11246595 - DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 本選 解法:「時刻tで美味しさの総和がX以上になるか」という二分探索をする。二分探索内の条件判定では、時刻tからさ…

ARC024 C - だれじゃ

問題:C - だれじゃ 解答:Submission #11167793 - AtCoder Regular Contest 024 解法: s[i : j]をsのi+1文字目からj文字目までの部分文字列とする。マッチングをチェックするのは以下の範囲。 s[k : 2k]はs[0 : k]をチェック s[k+1 : 2k+1]はs[0 : k], s[1…

AGC043 B - 123 Triangle

問題:B - 123 Triangle 解答:Submission #11073495 - AtCoder Grand Contest 043 解法:a[i]を-1して各要素を0, 1, 2で考える。各ステップに現れる数字も0, 1, 2のいずれかであり、最終的な数字も0, 1, 2のいずれかである。 ここで、次のような場合分けが…

AGC043 A - Range Flip Find Route

問題:A - Range Flip Find Route 解答:Submission #11068021 - AtCoder Grand Contest 043 解法:DFSしてゆく。白から黒に移動するときにカウントアップする。各マスのカウントの最小値を保持して枝刈りする。

Donutsプロコンチャレンジ2015 C - 行列のできるドーナツ屋

問題:C - 行列のできるドーナツ屋 解答:Submission #11037583 - Donutsプロコンチャレンジ2015 解法:スタックを準備し、数列を前から見てゆく。人iについて出力するのはその人より前でできている狭義単調減少列の長さであり、その単調列をスタックに格納…

CODE FESTIVAL 2014 Easy C - 身体バランス

問題:C - 身体バランス 解答:Submission #11036772 - CODE FESTIVAL 2014 Easy 解法:sからとtからでそれぞれダイクストラし、d1[u] == d2[u]かつd1[u] < INFであるものがあれば、uを出力する。

Donutsプロコンチャレンジ2015 B - Tokyo 7th シスターズ

問題:B - Tokyo 7th シスターズ 解答:https://atcoder.jp/contests/donuts-2015/submissions/11032269 解法:bit全探索で全てのユニットの組み合わせを試せばよい。計算量は216 * 50 * 9 = 29491200で何とか間に合う。

CODE FESTIVAL 2014 予選B C - 錬金術士

問題:C - 錬金術士 解答:Submission #11032114 - CODE FESTIVAL 2014 予選B 解法:まず、各文字種('A' - 'Z')について、S1内の個数とS2内の個数の和がS3内の個数より小さいものがあれば、NOを出力。全ての場合でそうでないなら、「S1から何個、S2から何個…

天下一プログラマーコンテスト2013予選B B - 天下一後入れ先出しデータ構造

問題:B - 天下一後入れ先出しデータ構造 解答:Submission #10994449 - 天下一プログラマーコンテスト2013予選B 解法:Stackされる数とその個数をそれぞれ管理するスタック(snum, scnt)を準備し、Push・Pop命令は1つのクエリをまとめて処理する。

CODE FESTIVAL 2014 予選B D - 登山家

問題:D - 登山家 解答①:Submission #10974270 - CODE FESTIVAL 2014 予選B 解答②:Submission #10977004 - CODE FESTIVAL 2014 予選B 解答③:Submission #10993670 - CODE FESTIVAL 2014 予選B 解法:i番目の山小屋について、その山小屋より左側、右側でそ…

Code Formula 2014 予選B C - 仲良し文字列

問題:C - 仲良し文字列 解答:Submission #10929382 - Code Formula 2014 予選B 解法:1回のスワップでab間の異なる文字が同じになるのは高々2文字なので、7文字以上異なる場合はその時点でNO。6文字であれば3回スワップしても計算量は66=46636で間に合う。…

Indeedなう(予選B) C - 木

問題:C - 木 解答:Submission #10920720 - Indeedなう(予選B) 解法:dfsで各頂点を探索していく。いったん隣接頂点を全て確認した後、それをpriority_queueに格納しておき、次に探索するのはpriory_queueの中の最小の頂点とする。

天下一プログラマーコンテスト2014予選B B - エターナルスタティックファイナル

問題:B - エターナルスタティックファイナル 解答:Submission #10902648 - 天下一プログラマーコンテスト2014予選B 解法:dp[i]をi文字目までを作るときの作り方の通り数とする。 元の文字列sのi文字目について、全ての文字列の候補でマッチするかどうかを…

Codeforces Round #627 (Div. 3) E. Sleeping Schedule

問題:Problem - E - Codeforces 解答:Submission #73178165 - Codeforces 解法:dp[i][j]をi回目の睡眠で睡眠開始がjであるときのgood睡眠の最大値とする。 このときi回目で睡眠開始がj であるとき、i+1回目の睡眠開始はj + a[i]もしくはj + a[i] - 1なの…

Codeforces Round #627 (Div. 3) D. Pair of Topics

問題:Problem - D - Codeforces 解答:Submission #73177810 - Codeforces 解法:ai + aj > bi + bj ⇔ ai - bi > aj - bj よりci = ai - bi とし、ci > cjとなる(i, j)の個数を探す。 cを昇順ソートする。iとjを逆にし、ci < cj (i < j)を探す。 ci > 0 で…

ARC091 E - LISDL (700)

問題:E - LISDL 解答1(通常座圧):Submission #10767274 - AtCoder Regular Contest 091 解答2(自前計算座圧):Submission #10767259 - AtCoder Regular Contest 091 解法:次のような2次元マトリクスを考える。 このマトリクスから次のようにN個の数…

日立コン2020 C - ThREE (600)

問題:C - ThREE 解答:Submission #10717648 - Social Infrastructure Information Systems Division, Hitachi Programming Contest 2020 解法:piとpjの和または積が3の倍数であることは、「pi, pjが1 (mod 3), 2(mod 3)のそれぞれどちらか」または「pi, p…

ABC158 E - Divisible Substring (500)

問題:E - Divisible Substring 解答:Submission #10651412 - AtCoder Beginner Contest 158 解法:解説AC。 s[i: j]をsのi文字目からj文字目までの部分文字列を評価した整数とする。するとs[i: j] = (s[i: N] - s[j+1: N]) / 10j - i +1であることが重要。…

AGC033 C - Removing Coins (800)

問題:C - Removing Coins 解答:Submission #10579618 - AtCoder Grand Contest 033 解法:木の直径に注目すると、直径の端点を選んだ場合は直径が1減少し、それ以外の点を選んだ場合は直径が2減少する。 よってこのゲームは「木の直径から1または2を交互に…

ARC041 C - ウサギ跳び

問題:C - ウサギ跳び 解答:Submission #10535617 - AtCoder Regular Contest 041 解法:左の壁から連続するLと右の壁まで連続するRについては、壁(もしくは先にいるウサギ)に突き当たるまで進ませる。 R...RL...Lになっている並びのウサギを考える。まず…

CODE FESTIVAL 2016 Final D - Pair Cards (700)

問題:D - Pair Cards 解答:Submission #10528447 - CODE FESTIVAL 2016 Final 解法:mod Mごとに数をグループ分けする。ペアの作り方は下記の3通り。 同じ数同士でペアを作る 同じグループの違う数同士でペアを作る 異なるグループの数同士でペアを作る グ…

AGC022 B - GCD Sequence (600)

問題:B - GCD Sequence 解答:Submission #10499621 - AtCoder Grand Contest 022 解法:解説AC。 aiの和をSとすると、gcd(ai, S) > 1 でgcd(a1, a2, ..., an) = 1を満たすaiの構築をすればよい。 制約がN ≦ 20000、ai ≦ 30000であり、N = 20000の時は30000…

ARC027 C - 最高のトッピングにしような

問題:C - 最高のトッピングにしような 解答:Submission #10481643 - AtCoder Regular Contest 027 解法:今の品物の番目、残りのスペシャルチケットの枚数、残りの通常チケットの枚数を保持しながらメモ化再帰。 遷移は愚直にやるとスペシャルチケットi枚…

ABC157 E - Simple String Queries (500)

問題:E - Simple String Queries 解答:Submission #10469785 - AtCoder Beginner Contest 157 解法: 各アルファベットに対応する長さnのセグ木を作り、s[i]がそのアルファベットなら+1、そうでないなら0とする。 クエリ1は変更前、変更後のアルファベット…

ABC157 D - Friend Suggestions(400)

問題:D - Friend Suggestions 解答:Submission #10448187 - AtCoder Beginner Contest 157 解法:各人について「友達関係のUnionFindの連結数 - 友達数 - ブロック数」を出力する。 ブロック数は友達関係の同一成分のもののみをカウントする。