2017-01-01から1年間の記事一覧
D - 2017-like Number ハマったところ 1〜nすべてに素数判定して間に合うかが最初判断できなかった 素数判定の計算量を把握していなかったため github.com
C - Special Trains ハマったところ for loopの回数を一回間違えていた github.com
B - Postal Code github.com
A - New Year github.com
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.contest.atcoder.jp 解き方 各数字が何個含まれるか調べて、条件を満たさない数字を条件を満たすように取り除く nがm個ある時、n > mならn-m個除き、n < mならn個除く procon-workspace/c.cc at master · HiroakiMikami/procon-workspace · GitHub
colopl2018-qual.contest.atcoder.jp 解き方 同時に選択してはいけないペアn, mを事前に列挙しておく カードn (A <= n <= B)について、入れるかどうかを場合分けしながら(再帰関数で実装)個数を数え上げ procon-workspace/c.cc at master · HiroakiMikami/…
colopl2018-qual.contest.atcoder.jp procon-workspace/b.cc at master · HiroakiMikami/procon-workspace · GitHub
colopl2018-qual.contest.atcoder.jp procon-workspace/a.cc at master · HiroakiMikami/procon-workspace · GitHub
arc084.contest.atcoder.jp 解き方 +1、*10の2つの計算を辺、自然数を頂点としてグラフを作る 自然数全体を頂点にはできないのでmod Kする コストは各桁の和の変化量(それぞれ1, 0) 01BFSで1 mod Kから0 mod Kまでの最短距離を求める ハマったところ 自然数…
D - Wall 解き方 iを1にするための最小コストをWarshall Floydで求めてから計算 github.com
C - Train Ticket 解き方 opの組み合わせをすべてやっても2^3=8通りなので、全探索 github.com
B - Lucas Number github.com
A - Good Integer ハマったところ 連続する、の条件を見落としていた github.com
競技プログラミング ABC079 結果 140th Aでしょうもないミスをしてペナルティ食らったが、概ね順調
D - ABS 解き方 本来は2パターンだけ考えれば良いらしい この手の「何個か取り除いてなくなったら終わり」系のゲームってそういうの多い気がする DPを使った方法 Yがa_iを持ってXに手番が回ってきたときの最大値、Xがa_iを持ってY似て番が回ってきたときの最…
C - HSI 解き方 1回の試行にかかる時間*試行回数の期待値 本当にこれであっているのか少し疑問だったけどAC github.com
競技プログラミング ARC085 結果268th, 1693->1701 (Perf: 1764) Dで手間取ったものの、2完でギリギリ1700超え その他 jlenvのissue対応
C - Snuke Festival 解き方 中段を決めると、ありえる上段、下段の個数が二分探索で求められる(事前にソートしておく) github.com
D - AtCoder Express ハマったところ cout << fixedしておかないと、浮動小数点数の表記が1e10みたいな表記になってWAになってしまう templateを最初にcout << fixedするように修正済 github.com
C - Dubious Document 2 解き方 Tが1文字目から始まる場合、2文字目から始まる場合…をそれぞれ考える(埋まらない?にはaを入れると辞書順最小になる) 全体で辞書順最小のものを選ぶ github.com
B - Addition and Multiplication github.com
A - Rating Goal github.com
競技プログラミング ABC076 結果 145th 浮動小数点数の扱いでDを落とした ARC084 結果141st, 1624->1693 (Perf: 2139) 1完だったものの、Cで手間取らなかったので解答時間で順位を上げたっぽい その他 Julia周りをいくつか
code-festival-2017-qualc.contest.atcoder.jp 解き方 O(n)の前計算で、s[i:j]が入れ替えて回文になるかどうかを計算できるようにする s[0:i]の最小の分割数でDPを構成する(O(n^2)) hash値に対するDPとすることでO(n)に高速化 ハマったところ 前計算→DPの流…
code-festival-2017-qualc.contest.atcoder.jp 解き方 両端から調査していく(xが片方に見つかったらxをもう一方に足す) ハマったところ 最初、奇数回出現する文字があるかないかで場合分けなど不要に複雑にしていた github.com
code-festival-2017-qualc.contest.atcoder.jp 解き方 a_m...a_nと似ていて、積が偶数である数列b_m...b_nとしてあり得る数列の個数を、m=n, n-1, ..., 1の順序で考える |a_i - b_i| <= 1より、b_iとして考えられる数字は3つ github.com
code-festival-2017-qualc.contest.atcoder.jp github.com
ddcc2017-qual.contest.atcoder.jp 解き方 南北、東西に対称となる4点それぞれについて場合分け 以下の2パターンのどちらかが答えとなる 東西方向に揃える→南北・東西両方に揃える→0個になるまで取り除いていく(最大となるように) 南北方向に揃える→南北・…
競技プログラミング AtCoder CodeFestival Qual C 結果 590th, 1640->1624 (perf: 1492) Cを無駄に複雑に考えたのがもったいなかったな その他 jlenv, VirtualEnv.jlが一通り安定して動くようになった