ferinの競プロ帳

競プロについてのメモ

バグ記録

AOJICPCを解いてたら思ったより手こずったのでその反省

AOJ2904 GuruGuru

RLLLRRR みたいなのを数えて1WA
問題文に書かれていることをちゃんと書く

AOJ2846 Slimming Plan

1週目だけで達成できるパターンを忘れてた
二分探索の結果が oxxxxxoooooo みたいなとき,境界をちゃんと決める

AOJ1315 Gift from the Goddess of Programming

こういうのは最小単位(分とか秒)で扱う
time[j] と time[id[i]] を間違えて1WA

AOJ2166 Erratic Sleep Habits

貪欲書いたら嘘で1WA
DPにしたら通った

AOJ1380 Medical Checkup

これふつうにむずくない?
x/y (xが負) を場合分けして考えないといけないのを見落として1WA

AOJ2847 Ninja Map

角4点の配置と隅に隣り合ってる辺を1点決めたら残りは一意に定まる
全部試してokなのを出力
角4点の配置何通りか試さないとだめなのに気づかなくて1WA
配列外参照で1WA
n=2で1WA
カス

AOJ2906 Santa's Gift

定数倍軽めの108は余裕

AOJ2912 Sum of QQ

割り切れない場合は数えちゃいけないのを忘れてサンプル合わないなあって言ってた

ここまでが~300

AOJ2178 Futon

1点を頭か足か決めたら残りは全部決まる
非連結なのに頂点0からだけdfsをして1WA
checkし忘れたケースがあって1WA
REP(i, idx) if(val[i]==-1) dfs(0,0) って何? 1WA
ひどい

AOJ1379 Parallel Lines

傾き一つ決め打てばいいのかと最初勘違いした

AOJ2555 Everlasting Zero

普通に難しかったんだけど・・・
スキルポイントの下限/上限を見ればいいのかと思ったが順序が関係ある
依存関係があるのでグラフにしてトポソ?
 → 孤立点がいっぱいとかでもDAG
全頂点をたどる(同じ頂点を何回使ってもいい)パスが存在するか判定?
 → iからj,jからkに移動できてもi→j→kと移動できるとは限らない
最初に使える頂点は他の全ての頂点に移動できる必要がある
同様にある頂点に訪れるときはまだ訪れていない他の全ての頂点に移動できる必要がある
次数が条件を満たすなら移動できる頂点の候補に追加とトポソの要領でやる
同じ頂点を2回削除してWA
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4066274#1

ちゃんと推移律があるか確認!

AOJ2723 Surface Area of Cubes

x,y,zの3方向それぞれから見て独立に数える
端が消えているときの数え方ミスって1WA
a,b,c間違えて(は?)1WA

AOJ2858 Prime-Factor Prime

区間篩はじめてかいた
r未満の素数でない数を素因数分解することを考える
sqrt(r)以下の素数で割っていって,残った数が1より大きいならそれも素数
これを区間篩の要領で実装すると素因数の個数がわかる
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4068135#1

AOJ2684 RLE Replacement

BがAの中に存在しない場合を忘れてRE
B.size()=1のときを忘れて1WA
B.size()=1のときbreakじゃなくてcontinueして1WA
idxとi間違えて1WA(?????)

ここまでが~350

AOJ1243 Weather Forecast

適当に読んだら斜めに進んじゃいけないの読み飛ばした(は?)

AOJ1244 Molecular Formula

構文解析するだけ
珍しく一発で通った

ここまでが~400

AOJ2538 Stack Maze

二次元区間DP
そもそもDP遷移がおかしくてWA
到達性判定が必要なの忘れててWA
if文の順番はscoreが悪い方からする 順番間違えてWA
到達性判定のdfsでメモ化忘れてTLE(は?)
カス

ここまでが~550