きろく

特筆すべき記録のまとめ

AtCoder 500 点問題

AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019:D - Nearest Card Game

問題 解法 解答 問題 atcoder.jp 解法 2人の操作後の各カードの所属は,N が偶数のとき「TATA...TAAA...ATT...T」のように高橋君と青木君が交互になっている区間(区間1)・青木君の区間(区間2)・高橋君の区間(区間3)となっている.また.区間2と区…

KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019:D - Double Landscape

問題 解法 解答 問題 atcoder.jp 解法 各マス (i, j) に書くことが出来る数字の最大値を max_(i, j) とする.また,数字 i が書くことが出来る数字の最大値になっているマスの個数を cnt_i とし,数字 i を書く時点で書くことが出来るマスの総数を avail_i …

COLOCON -Colopl programming contest 2018-:D - すぬけそだて――トレーニング――

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := i 番目の候補の時刻から先で j 回起動するときの解の最大値 と DP をおく.このとき,愚直に全ての候補を選んでいては O(N^3) になってしまう.ここで,「今の時刻 + X を超える時刻のうち一番早いもの」と…

DISCO presents ディスカバリーチャンネル コードコンテスト2017 本戦:B - GCDロボット

問題 解法 解答 問題 atcoder.jp 解法 求める整数は gcd(a_1, Z), gcd(a_2, Z), ... , gcd(a_N, Z) の公倍数である必要があるので,この公倍数のうち最小のものを求めるので,答えは lcm(a_i, Z) になる.O(N). 解答 atcoder.jp

Tenka1 Programmer Contest:D - IntegerotS

問題 解法 解答 問題 atcoder.jp 解法 K を2進数表記したとき,「0 ~ 2^(k - 1) の位が 1,2^k の位が 0,2^(k + 1) ~ 2^30 の位は K のそれぞれの位と同じ」数を考える.この数を OR で超えない中で整数を出来るだけ選べばよいので,各 k についてそれぞれ…

codeFlyer (bitFlyer Programming Contest):D - ハンコ

問題 解法 解答 問題 atcoder.jp 解法 紙の (N + 1) 行目~ (H - N) 行目,(M + 1) 列目~ (W - M) 列目 はそれぞれ同じ模様になるので,この2つの区間を座標圧縮することが出来る.また,ハンコの1つ1つの黒マスが紙を黒くする領域は長方形になるので,…

CADDi 2018:D - Harlequin

問題 解法 解答 問題 atcoder.jp 解法 答えは「全ての色の個数が偶数であれば "second",そうでなければ "first".」になる. 相手に全ての色の個数を偶数で渡すことが出来れば,相手が任意の色の個数を奇数にしてきたとしても,こちら側で奇数にされたとこ…

codeFlyer (bitFlyer Programming Contest):C - 部分文字列と括弧

問題 解法 解答 問題 atcoder.jp 解法 '(' を +1,')' を -1 として累積和 imos を取った時,当てはまる (i, j) の組は imos[i] == imos[j] - 1 imos[k] >= imos[j] - 1 (i <= k <= j) を満たしていればよい.1つ目の条件にあてはまる (i, j) の組を std::m…

「みんなのプロコン 2018」:C - 駆引取引

問題 解法 解答 問題 atcoder.jp 解法 dp1(b, i) := 今残っている商品が b で,財宝を i 個売却した時に商品を買って取引を終了する場合,得られる最大のスコア dp2(b, i) := 今残っている商品が b で,財宝を i 個売却した時に得られる最大のスコア の2つ…

第4回 ドワンゴからの挑戦状 予選:C - Kill/Death

問題 解法 解答 問題 atcoder.jp 解法 A チームでの総 kill 数は B チームでの総 death 数になり,その逆もそうなる.チーム内で同じ kill 数を1グループとしてみると,グループ内で death 数を分割すると考えられるので,分割数のアルゴリズムを使える.あ…

CODE FESTIVAL 2018 Final:D - Three Letters

問題 解法 解答 問題 beta.atcoder.jp 解法 各文字列ごとにある場所 p より左右それぞれに文字 c があるかどうかを前計算しておき,各場所 p ごとに考えられる略称を全探索していき,数えておく.考えられる略称のうち最も数えた数が多いものが答えになる.O…

CODE FESTIVAL 2018 qual B:C - Special Cake for CODE FESTIVAL

問題 解法 解答 問題 beta.atcoder.jp 解法 以下のように X を配置するのがよい. 背景黒文字白の X 以外の X の配置場所には規則性があるので簡単における.背景黒文字白の X は規則性に基づいておいたけれども食べられるマスに配置する.O(N^2). 解答 bet…

Mujin Programming Challenge 2018:E - 迷路

問題 解法 解答 問題 beta.atcoder.jp 解法 ダイクストラ法を使う.この中で,あるマスである方向に動けるようになるまでずっとループを回していると O(NMKlogNM) になり間に合わないので,時刻 0 ~ K - 1 のそれぞれの時,次に上下左右に動ける時刻を O(1) …

Tenka1 Programmer Contest:D - Crossing

問題 解法 解答 問題 beta.atcoder.jp 解法 図を書いてみると,1 ~ N の数字を三角形状に並べられるものがよいと気づくので,N が三角数であれば Yes,そうでなければ No となる. どのように部分列を構成するかというと, N = 15 の場合では,三角形の三辺…

square869120Contest #4:C - Calendar 2

問題 解法 解答 問題 beta.atcoder.jp 解法 lcm(7, m) のマスは 0 のマスと塗られているかどうかは同じになるので,lcm(7, m) - 1 のマスまでマス目を塗るシミュレーションをすれば十分.縦 lcm(7, m) / 7 マス,横 7 マスの表を S と置く.S の下に新しく S…

square869120Contest #5:C - Two Parentheses

問題 解法 解答 問題 beta.atcoder.jp 解法 A, B の "(" , ")" の数がそれぞれ |S| / 4 になっていればよい.S を先頭から見ていくとき,S を真ん中で半分にして考える. 前半分のとき, S_i == "(" で A の "(" が不足しているとき:A += "(" S_i == "(" で…

九州大学プログラミングコンテスト2018:E - Treeone

問題 解法 解答 問題 beta.atcoder.jp 解法 ある要素を inf にした場合,答えは2つに分けられた数列のそれぞれの中で完結する要素の総和が0である部分列の数の和になる.そこで,2つに分ける箇所を全探索し,それぞれについて前後の数列に当てはまる部分…

九州大学プログラミングコンテスト2018:D - Novelist

問題 解法 解答 問題 beta.atcoder.jp 解法 王都から各都市に行ったならばすぐに王都に戻るのが最適であるので,M 個の依頼からすぐにまた王都に戻ってくる時刻を1つに定められる.なので,2種類の依頼を1つにまとめてしまうことで,最大スケジューリング…

技術室奥プログラミングコンテスト #3:E - デフレゲーム

問題 解法 解答 問題 beta.atcoder.jp 解法 何回目に操作が終了するかで場合分けをする.k 回目に操作が終了する確率は (n / n) * ( ( n - 1 ) / n) * ( ( n - 2 ) / n) * ... * ( ( n - ( k - 2 ) ) / n) * ( ( k - 1 ) / n) になる.k 回目までのさいころ…

CODE FESTIVAL 2018 qual A : C - 半分

問題 解法 解答 問題 C - 半分 解法 「dp(i, j, f) := i 番目までで j 回操作するときの通り数(f := 今までの要素を 0 にしたかどうか)」で DP をする.f が true のとき,操作の回数が余ったとしても,どこか 0 である要素で余った回数を消費すれば良いの…

codeFlyer (bitFlyer Programming Contest)オープンコンテスト : C - 部分文字列と括弧

問題 解法 解答 問題 C - 部分文字列と括弧 ( と ) で構成される文字列 S の中で括弧の対応が取れている部分文字列の数を求める問題。 解法 まず、括弧が対応している最小の部分文字列を列挙したい。S の最初から ( なら +1 、) なら -1 という基準で累積和…

AtCoder Regular Contest 099 : D - Snuke Numbers

問題 D - Snuke Numbers 「S(n) := 10 進数表記での n の桁和」としたとき、m > n である任意の正の整数 m に対して n / S(n) <= m / S(m) が成り立つような n を「すぬけ数」と呼ぶとき、「すぬけ数」を小さい方から順に K 個求めよ、という問題。 解説 コ…

AtCoder Regular Contest 064 : D - An Ordinary Game

問題 D - An Ordinary Game 端っこと左右が同じ文字の位置にある文字以外を2人が最適に取り除いていくときの勝敗を求める問題。 解法 S の両端が同じならば、終わった時の文字列の長さは奇数になる。一方、S の両端が異なれば、終わった時の文字列の長さは…

AtCoder Regular Contest 060 : D - 桁和 / Digit Sum

問題 D - 桁和 / Digit Sum 10 進法で N を b 進法に直したとき、その桁和が S になるような最小の b を求める問題。 解法 b をとりあえず 1~√N まで試す。b が √N を超えると、N の b 進法での桁数は2桁になるので、以下のような式が成り立つ。 N = αb + β…

AtCoder 第4回 ドワンゴからの挑戦状 予選 : C - Kill/Death

問題 C - Kill/Death A, B 両チームのそれぞれのプレーヤー(それぞれ N, M 人)の Kill 数が分かっているとき、各プレーヤーの Death 数の通り数を求める問題。 解法 両チームの中で同じ Kill 数のプレーヤーごとに区切り、何人グループかを調べる。A チー…

AtCoder codeFlyer (bitFlyer Programming Contest) : D - ハンコ

問題 D - ハンコ HW のマスに NM のハンコをひたすらおし、押されたマスの合計を求めよ、という問題。 解法 H,W <= 10^9 であるため、HW の二次元配列は用意できない。しかし、N,M <= 10^3 であるため、なんかできそうだなあと思った。考えると、 ハンコのマ…