きろく

特筆すべき記録のまとめ

AtCoder 300 点問題

全国統一プログラミング王決定戦本戦:C - Come Together

問題 解法 解答 問題 atcoder.jp 解法 各駒の縦方向・横方向の移動は独立に考えられる. ある x 座標への全ての駒の縦方向の移動量の総和を求めることを考える.ここで,決めた x 座標より小さい座標にある駒の数 cnt_up と座標の値の総和 cost_up を知れれ…

AtCoder Beginner Contest 122:C - GeT AC

問題 解法 解答 問題 atcoder.jp 解法 N, Q <= 10^5 より,各クエリごとに文字列を走査していては間に合わない.そこで,各クエリに O(1) で答えられるようにする. imos_i := i 文字目までに登場する "AC" の数 とおくと,各クエリで求める値は imos_r - im…

AtCoder Beginner Contest 121:C - Energy Drink Collector

問題 解法 解答 問題 atcoder.jp 解法 どの店も1本ごとに値段が決まっているので,1本ごとの値段が安い店から順番に出来るだけ買うのが最適.M 本買えるまで安い順に店を当たっていく.ソートがボトルネックとなり O(NlogN). 解答 atcoder.jp くだらない…

AtCoder Beginner Contest 118:C - Monsters Battle Royale

問題 解法 解答 問題 atcoder.jp 解法 モンスター同士が攻撃しあう様子を見るとユークリッドの互除法の過程をしているだけなので,GCD(A_1, A_2, ..., A_N) を答えにすればよい.これは,ある2体のモンスターが攻撃しあって生き残ったほうの体力は2体のモ…

AtCoder Beginner Contest 117:C - Streamline

問題 解法 解答 問題 atcoder.jp 解法 まず,駒を +1 の方向に動かした後に -1 の方向に動かすのは自明に意味がない.なので,駒を +1 の方向にだけ動かすことを考える.駒が通る距離を最小化したいので,駒が通らない距離を最大化すればよい.一番左・右の…

DISCO presents ディスカバリーチャンネル コードコンテスト2019 本戦:A - レース (Race)

問題 解法 解答 問題 atcoder.jp 解法 雪マスは必ず2つ以上連続するので,1つの雪マスを氷マスに変化させても氷マスの連続する区間が1つの区間になることはない.また,氷マスの区間が最も長い区間の前後どちらかの雪マスを氷マスに変化させるのが最適で…

AtCoder Beginner Contest 116:C - Grand Garden

問題 解法 解答 問題 atcoder.jp 解法 「水やり」の回数を最小化したいので,1回の「水やり」で出来るだけ多くの花の高さを伸ばしたい.なので,あと 1 以上伸ばさなければいけない花の連続する区間は1回の「水やり」で 1 ずつ伸ばす.h_i に達した花がそ…

CODE FESTIVAL 2018 Final:B - Theme Color

問題 解法 解答 問題 atcoder.jp 解法 p = C(N, r_1) * C(N - r_1, r_2) * C(N - r_1 - r_2, r_3) * ... * C(r_M, r_M) / M^N となる.これを愚直に計算すると,途中で数が大きくなりすぎてしまったり小さくなりすぎてしまったりするので,全体に log10 する…

CADDi 2018:C - Product and GCD

問題 解法 解答 問題 atcoder.jp 解法 P の素因数を a_i に分配していくイメージなので,P を素因数分解し,各 a_i に (各素因数の個数 / N) 個ずつ各素因数を分配すれば GCD が最大にできる.O(sqrt(P)). 解答 atcoder.jp かける個数を単純に 1 としてしま…

CODE THANKS FESTIVAL 2018:D - Concatenation

問題 解法 解答 問題 atcoder.jp 解法 文字列を前から見ていき,今構成している部分文字列の先頭の文字より小さいか同じ文字が出てきたら,その箇所で部分文字列を切り,新しいものを始めればよい(シミュレーション).O(|S|). 解答 atcoder.jp

CODE THANKS FESTIVAL 2018:C - Pair Distance

問題 解法 解答 問題 atcoder.jp 解法 絶対値がついているのが厄介というか大変そうなので,x を昇順にソートすることによって各 i について (x_(i + 1) + x_(i + 2) + ... + x_N) - x_i * (N - i - 1) も求め,足し合わせたものが答えになる.O(NlogN). 解…

AtCoder Grand Contest 029:A - Irreversible operation

問題 解法 解答 問題 beta.atcoder.jp 解法 それぞれの W より左にある B の数の合計が答えになる. 解答 beta.atcoder.jp

AtCoder Beginner Contest 114:C - 755

問題 解法 解答 問題 beta.atcoder.jp 解法 3 を 0,5 を 1,7 を 2 として考えると3進数を列挙して考えればよいと分かる.この通り数は 3^9 なので十分間に合う.O(3 ^ log2(N)). 解答 beta.atcoder.jp 実装で少してこずったが一発 AC.

CODE FESTIVAL 2018 Final (Parallel):C - Telephone Charge

問題 解法 解答 問題 beta.atcoder.jp 解法 「全てのプラン ii に対して、通話時間が AiAi 分の場合には他のどのプランよりも通話料金が 11 円以上安くなることが保証され」ているので,A が T を超えるプランと超えないプランの2つについて料金を計算し,m…

CODE FESTIVAL 2018 Final (Parallel):A - 2540

問題 解法 解答 問題 beta.atcoder.jp 解法 頂点ごとに各長さの辺が何本生えているかを数えておき,2つの辺の中間の頂点を全通り試し,それぞれ何通りのペアができるかを計算し,足していく.O(NlogN). 解答 beta.atcoder.jp 実装ミスで 8 WA した.

AtCoder Beginner Contest 113:C - ID

問題 解法 解答 問題 beta.atcoder.jp 解法 (誕生した年,所属する県の番号,入力時の index) で二重 std::pair を作り,素直にソートし,県ごとに誕生した市ごとに番号を割り振っていけばよい.O(MlogM). 解答 beta.atcoder.jp C 問題にしては良心的な問題…

SoundHound Programming Contest 2018 Masters Tournament 本戦 (Open):A - Feel the Beat

問題 解法 解答 問題 beta.atcoder.jp 解法 好きな曲の BPM の範囲は,[140, 170), [280, 340), ... と両端の数値が2倍ずつ増えていき変化する.よって,BPM の範囲を全て列挙し,それぞれの範囲と [L, R) の共通範囲の個数を計算し,それらの和を求めれば…

技術室奥プログラミングコンテスト #3:C - 新入生歓迎数列 - Easy

問題 解法 解答 問題 beta.atcoder.jp 解法 ある連続する区間積が P になればよいので,この連続する区間が数列 A にあるかどうかを判定すればよい.尺取り法を使って考えると,区間積が P より大きくなったら左端を縮める,P より小さくなったら右端を伸ば…

AtCoder Grand Contest 028:A - Two Abbreviations

問題 解法 解答 問題 beta.atcoder.jp 解法 まず,「よい文字列」が存在するときその長さは lcm(N, M) になるのは自明.なぜなら,lcm(N, M) の倍数で考えても見るべき X の場所の組は変わらないから. 長さを固定できたので,あとは構成した X が条件に当て…

九州大学プログラミングコンテスト2018:B - Tapu & Tapi

問題 解法 解答 問題 beta.atcoder.jp 解法 1円,10 円,100 円の順番に分ける枚数を決めていく.この時,各硬貨の枚数が偶数になれば条件を満たす.ここで,各硬貨の枚数に mod 20 をとる.なぜならば,1つ上の硬貨に位上げしても,位上げの枚数は必ず偶…

AtCoder Regular Contest 103:C - /\/\/\/

問題 解法 解答 問題 C - /\/\/\/ 解法 数列の奇数個目と偶数個目で新しく数列を2つつくり,それぞれの中で最も多く登場する要素の数を N / 2 から引いたものが答えになるが,これだと,それぞれ同じ数字が当てはまってしまう場合が考えうる.そのため,「…

AtCoder Beginner Contest 110:C - String Transformation

問題 解法 解答 問題 C - String Transformation 解法 S -> T になるように各文字を置き換えるとき,S_i が T_i に対応するように1対1の関係になれば一致させることが出来る.逆に,1対1にならなければ一致させることは出来ない(1つのアルファベットを…

AtCoder Regular Contest 101:C - Candles

問題 解法 解答 問題 N 本のろうそくが x 軸上に並んでいて,K 本のろうそくをつけたい.最初,座標 0 にいるとき,移動するための最小コストはいくつか求める問題. 解法 x 座標が正のろうそくを i 本,負のろうそくを N - i 本つけると考えて,0 <= i <= N…

AtCoder Beginner Contest 105:C - Base -2 Number

問題 解法 解答 問題 C - Base -2 Number 整数 N を -2 進数に変換した結果を求める問題. 解法 2^(2k) (0 <= k <= 16) の位は +,2^(2k+1) の位は - になるので,それぞれ独立して考える(bit を1こ飛ばし).前者と後者で考えられる 10 進数表記を全列挙…