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

ABC076 B: Addition and Multiplication

B - Addition and Multiplication github.com

ABC076 A: Rating Goal

A - Rating Goal github.com

活動記録(2017/10/23-2017/11/5)

競技プログラミング ABC076 結果 145th 浮動小数点数の扱いでDを落とした ARC084 結果141st, 1624->1693 (Perf: 2139) 1完だったものの、Cで手間取らなかったので解答時間で順位を上げたっぽい その他 Julia周りをいくつか

CODE FESTIVAL 2017 qual C D: Yet Another Palindrome Partitioning

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 qual C C: Inserting 'x'

code-festival-2017-qualc.contest.atcoder.jp 解き方 両端から調査していく(xが片方に見つかったらxをもう一方に足す) ハマったところ 最初、奇数回出現する文字があるかないかで場合分けなど不要に複雑にしていた github.com

CODE FESTIVAL 2017 qual C B: Similar Arrays

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 qual C A: Can you get AC?

code-festival-2017-qualc.contest.atcoder.jp github.com

DDCC2017 Qual D: 石

ddcc2017-qual.contest.atcoder.jp 解き方 南北、東西に対称となる4点それぞれについて場合分け 以下の2パターンのどちらかが答えとなる 東西方向に揃える→南北・東西両方に揃える→0個になるまで取り除いていく(最大となるように) 南北方向に揃える→南北・…

活動記録(2017/10/16-2017/10/22)

競技プログラミング AtCoder CodeFestival Qual C 結果 590th, 1640->1624 (perf: 1492) Cを無駄に複雑に考えたのがもったいなかったな その他 jlenv, VirtualEnv.jlが一通り安定して動くようになった

CODE FESTIVAL 2017 qual A D: Four Coloring

D - Four Coloring 解き方 45度回転してマンハッタン距離の代わりにチェビシェフ距離を使えるようにして、d*dの正方形ごとに色をかえる ハマったところ 45度回転する考えがそもそもなかった 要するにチェビシェフ距離が扱いやすいので、できるだけこれに変換…

活動記録(2017/9/25-2017/10/15)

競技プログラミング DDCC予選 Dがあと一歩解けずダメだった ABC075 全完。Cで無駄に時間を食ってしまった。 その他 Juliaを多少無理してでも使おうと心がけつつ、jlenvとVirtualEnv.jlを実装中

ABC075 D: Axis-Parallel Rectangle

D - Axis-Parallel Rectangle 解き方 長方形の頂点のx座標、y座標はいずれかの点のx座標、y座標と等しいと考えて問題ないので全探索 ハマったところ 全体でO(N^5)だったのでいけるか不安だったが、TLEはしなかった。 github.com

ABC075 C: Bridges

C - Bridge 解き方 DFSして橋を数える ハマったところ bridgeを見つけるアルゴリズムを忘れていたので、一から書いてたらデバッグに時間かかった github.com

ABC075 B: Minesweeper

B - Minesweeper github.com

ABC075 A: One out of Three

A - One out of Three github.com

DDCC2017 Qual C: 収納

ddcc2017-qual.contest.atcoder.jp 解き方 最長の鉛筆をまず箱に入れて、もし入るなら最短の鉛筆も入れる。これを繰り返して個数を求める ハマったところ 最長の鉛筆と入れられる最長の鉛筆を入れるようにしたら、TLEした 後者を求める時に、配列の要素削除…

DDCC2017 Qual B: 鉛筆

ddcc2017-qual.contest.atcoder.jp github.com

DDCC2017 Qual A: DDCC型文字列

ddcc2017-qual.contest.atcoder.jp github.com

Tenka1 Programmer Contest 2017 D: IntegerS

tenka1-2017.contest.atcoder.jp 解き方 選んだ整数のorとしてありうる数字を列挙し、それらを満たす整数の集合を探索する ハマったところ xorとorを見間違えて最初苦戦した bit演算を使う場合、bitに対してfor文をまわすのを避けるべきではない github.com

Tenka1 Programmer Contest 2017 C: 4/N

tenka1-2017.contest.atcoder.jp 解き方 h,nを1から3500の範囲で全探索する。h, nが決まればwは求まる github.com

AOJ 0009: Prime Number

Prime Number | Aizu Online Judge github.com

CODE FESTIVAL 2017 qual A C: Palindromic Matrix

code-festival-2017-quala.contest.atcoder.jp 解き方 回文を作るのに必要な同じ文字の数を計算 各アルファベットの出現回数を計算 必要な文字数が多い場所から順に、条件を満たす最小のアルファベットを入れる貪欲 ここが嘘解法っぽさがある github.com

CODE FESTIVAL 2017 qual A B: fLIP

code-festival-2017-quala.contest.atcoder.jp 解き方 行、列を入れ替える順番は無視して良いので、何列、何行入れ替えるかで全探索 ハマったところ +=の副作用を見逃してた github.com

CODE FESTIVAL 2017 qual A A: Snuke's favorite YAKINIKU

code-festival-2017-quala.contest.atcoder.jp github.com

活動記録(2017/9/18/-2017/9/24)

競技プログラミング Code Festival 予選 結果 894th, 1679 -> 1640 (パフォーマンス:1287) 体調不良の時にratedなコンテストに出てはいけない。 その他 メンタルと体調がどっちも死んでた

AOJ0005: GCD and LCM

GCD and LCM | Aizu Online Judge 解き方 ユークリッドの互除法 LCMは効率の良いアルゴリズムがあるらしいがよくわからない github.com

AOJ2224: Save your cats

Save your cats | Aizu Online Judge 解き方 pileを頂点、fenceを辺としたグラフを考えると、その双対グラフの最小全域木(コストは、fenceの長さ)を求めれば良い 双対グラフを求めるためには、最短閉路の列挙などする必要があり面倒 元の平面グラフの全域…