競技プログラミング/AtCoder

みんなのプロコン2018予選 B: オークション

B - オークション github.com

みんなのプロコン2018予選 A: yahoo

A - yahoo github.com

APC001 D: Forest

apc001.contest.atcoder.jp 解き方 前提 n個の木を連結にするためには、n-1個の辺を追加する必要がある 条件から辺に含まれる頂点は重複しないので、2n-2個の頂点が辺に含まれる 連結にするためには、各木から少なくとも1つは頂点を選ばないといけない 実装 …

APC001: C Vacant Seat

apc001.contest.atcoder.jp 解き方 最初の一回はとりあえず0を聞いて、次に反対側の2点(A, B)を聞く 反対側2点の結果から、[0:A]と[B:N-1]のどちらに空席があるかわかるので、そこからは二分探索 ハマったところ 実装中、CLionがおかしい挙動をした。termina…

APC002: B Two Arrays

apc001.contest.atcoder.jp github.com

ARC090 D: People on a Line

D - People on a Line 解き方 情報をそれぞれ辺としてグラフを作り、DFSしながら条件に当てはまる数字の割当があるかを調べる ハマったところ グラフが連結でないことを想定せず何回かWAした github.com

ARC090 C: Candies

C - Candies github.com

ARC089 D: Checker

D - Checker 解き方 市松模様のパターンはK^2通りあり、どこか1つのパターンを基準に尺取り方のような感じですべて計算すると、O(N+K^2)で計算できる procon-workspace/d.cc at master · HiroakiMikami/procon-workspace · GitHub

ARC089 C: Traveling

C - Traveling procon-workspace/c.cc at master · HiroakiMikami/procon-workspace · GitHub

AGC020 B: Ice Rink Game

B - Ice Rink Game 解き方 ラウンドi (i = N, N-1, ..., 1)での可能性のある最小値と最大値を順々に考える github.com

AGC020 A: Move and Win

A - Move and Win https://github.com/HiroakiMikami/procon-workspace/blob/master/src/atcoder/agc020/a.cc

ABC084 D: 2017-like Number

D - 2017-like Number ハマったところ 1〜nすべてに素数判定して間に合うかが最初判断できなかった 素数判定の計算量を把握していなかったため github.com

ABC084 C: Special Trains

C - Special Trains ハマったところ for loopの回数を一回間違えていた github.com

ABC084 B: Postal Code

B - Postal Code github.com

ABC084 A: New Year

A - New Year github.com

ARC087 D: FT Robot

arc087.contest.atcoder.jp 解き方 以下の2つを前計算する x方向に動ける距離:x_0, x_1, ..., x_n y方向に動ける距離:y_0, y_1, ..., y_n 以下のdpを埋める dp[a] := x座標の絶対値をaとすることができる最大の移動回数 同様にyも埋めて、dp[x] = n, dp[y]…

ARC087 C: Good Sequence

arc087.contest.atcoder.jp 解き方 各数字が何個含まれるか調べて、条件を満たさない数字を条件を満たすように取り除く nがm個ある時、n > mならn-m個除き、n < mならn個除く procon-workspace/c.cc at master · HiroakiMikami/procon-workspace · GitHub

COLOCON 2017: C すぬけそだて――ごはん――

colopl2018-qual.contest.atcoder.jp 解き方 同時に選択してはいけないペアn, mを事前に列挙しておく カードn (A <= n <= B)について、入れるかどうかを場合分けしながら(再帰関数で実装)個数を数え上げ procon-workspace/c.cc at master · HiroakiMikami/…

COLOCON 2017: B すぬけそだて――チュートリアル――

colopl2018-qual.contest.atcoder.jp procon-workspace/b.cc at master · HiroakiMikami/procon-workspace · GitHub

COLOCON 2017: A すぬけそだて――登録――

colopl2018-qual.contest.atcoder.jp procon-workspace/a.cc at master · HiroakiMikami/procon-workspace · GitHub

ARC084 D: Small Multiple

arc084.contest.atcoder.jp 解き方 +1、*10の2つの計算を辺、自然数を頂点としてグラフを作る 自然数全体を頂点にはできないのでmod Kする コストは各桁の和の変化量(それぞれ1, 0) 01BFSで1 mod Kから0 mod Kまでの最短距離を求める ハマったところ 自然数…

ABC079 D: Wall

D - Wall 解き方 iを1にするための最小コストをWarshall Floydで求めてから計算 github.com

ABC079 C: Train Ticket

C - Train Ticket 解き方 opの組み合わせをすべてやっても2^3=8通りなので、全探索 github.com

ABC079 B: Lucas Number

B - Lucas Number github.com

ABC079 A: Good Integer

A - Good Integer ハマったところ 連続する、の条件を見落としていた github.com

ARC085 D: ABS

D - ABS 解き方 本来は2パターンだけ考えれば良いらしい この手の「何個か取り除いてなくなったら終わり」系のゲームってそういうの多い気がする DPを使った方法 Yがa_iを持ってXに手番が回ってきたときの最大値、Xがa_iを持ってY似て番が回ってきたときの最…

ARC085 C: HSI

C - HSI 解き方 1回の試行にかかる時間*試行回数の期待値 本当にこれであっているのか少し疑問だったけどAC github.com

ARC084 C: Snuke Festival

C - Snuke Festival 解き方 中段を決めると、ありえる上段、下段の個数が二分探索で求められる(事前にソートしておく) github.com

ABC076 D: AtCoder Express

D - AtCoder Express ハマったところ cout << fixedしておかないと、浮動小数点数の表記が1e10みたいな表記になってWAになってしまう templateを最初にcout << fixedするように修正済 github.com

ABC076 C: Dubious Document 2

C - Dubious Document 2 解き方 Tが1文字目から始まる場合、2文字目から始まる場合…をそれぞれ考える(埋まらない?にはaを入れると辞書順最小になる) 全体で辞書順最小のものを選ぶ github.com