水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

AtCoder 300 点問題

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 進数表記を全列挙…