精進記録: ABC9 - ABC16 C問題
ABC9「辞書式順序ふたたび」に手こずったのといろいろ忙しかったのとであまり進んでない。
ABC9については、とりあえずヒントに頼らずにやってみたがWAが一個だけ残ってしまった。嘘解法なのかバグなのかはまだ調べていない。
計算量の感覚がもっとついてくれば、計算量を犠牲にしてでも実装のしやすさ&バグりにくさを優先するという動きが積極的にできるようになるはず。
いろいろやってきた感じ、ループの終了判定 & 再帰抜けを間違えてバグるケースが多い。
以下、解答時メモ
ABC16 317点
制約がチョロいので、ワーシャルフロイドして距離2のものを集めればよい。
-> 一発AC
ABC15 347点
この問題、以前どこかで見た気がする。
5個の質問に5通り解答なので高々5^5 = 3125通り。
全部調べても問題ない。
K^0 … K^{N}-1で全列挙 -> 一発AC
解説はdfsで調べていくというもの。
それまでに答えた質問数が同じで、かつそこまでのxorの値が等しいものを既に調べてあればその先はスキップでき、計算量をK^NからKNにできる。
K^Nでの全列挙だとこれはやりづらいので、制約が厳しい場合を考えると再帰によるコードの方がベター。
dfsの場合は以下のようなコード
for(inti = 0;i<K;i++){
}
returnfalse;
}
変なフラグ用の変数を使わずにdfsを書くには、上記のようにbool型を返して発見されたところから一直線に再帰を抜けられるようにしておくのがよい。
ABC14 348点
前にも使った方法でいける。
領域の左端に+1, 右端+1に-1を入れて最後に総和。
こういうのをimos法と呼ぶらしい？
-> 謎のWAに苦しめられる。
col[b+1] -= 1;
とすべきところが
col[b+1] =-1;
になっていた。
自分でもテストケースを作るのが大事。
難易度自体は過大評価な気がする。
ABC13 452点
基本的にコスパのいい食事だけ取ったほうがよいはず。
値が全体的におおきいのでint溢れ警戒。
食事を取る日数をMとすると、
B m_b + D m_d + H - (N-M)E >= 0
m_b + m_d = M;
一度も下回らなければ良いので、食事を取るタイミングを前に寄せてしまえば良い。
コスパの悪い方の食事をとることはあるか？
コスパが良いのが質素な食事であればひたすらそれだけでok
普通の食事の場合、満腹度の減少を抑えるためだけに使うという選択がある(サンプルケース1)。
処理が面倒。むしろ貪欲法か？
翌日を乗り切るための最安の選択をし続ければ良い？
この場合も、終わりのタイミングが難しい。
高い方のコスパが良いときに安い方を選ぶことがあるとすれば、
安い方を選べば残り生きていけることが確定するとき。
H(day) + B >= (N-day-1) * Eになったときを考えれば良い。
つまり、その日普通の食事を取ることで生きていけることが確定するタイミング。
このとき、選択肢として、
普通の食事を取る or 質素な食事でEの減少を抑える
の２つがでてくる。
-> 入力例3で破綻している。
普通の食事のほうがコスパは良いが、正解は普通 + 質素 * 4
もっとシンプルな問題な気がする。
普通の食事の日数を固定した時、N日目の満腹度は質素な食事の日数に対して単調増加 -> 二分探索
これなら N log Nで計算できる。
d_c D - (N-d_c)Eの配列 X を予め作っておいて、
given なd_aについて、
H * d_a E + d_a B + X[i] >= 0になる最小のiを求める。
つまり、Xの -(H * d_a E + d_a B)のlower_bound
-> 「0 以下にならない」なのでupper_boundが正しい。
一発ACしたものの、間違った考察で時間を吸われてしまった。
本来は10分ぐらいで解けないといけない問題。
よく読んでなかったが、100点を取るには N<=1000なので思考停止ループでよかった。
ABC12 222点
入力例から、正しい総和は2025
2025-Nを積に分解する。
ループでやるのが楽。 -> 一発AC
癒やし。
ABC11 332点
NGに衝突するまでは3を引けば良い。
衝突したら、衝突しない限りで最も小さい値に移動。
結局、NGが３つ並んでいない限りは、飛ぶ回数が残っている限りok
ループの終了判定を間違えていたのと、 N<=3の場合の処理ができていなくてWA。
単純に、
合法手の中でもっとも小さい値に行けるものを選んでいき、
100ステップ以内に0に到達できたらYES、合法手がなかったらNO
という方が実装がシンプル & ミスしづらいコードになったはず。
簡単な問題でも、いきなり書き始めると結果的に遅い or ミスすることに繋がる。
ABC10 275点
start -> house ->goal
の距離を全てのhouseについて計算し、それをVで割った値がT以下ならアウト。
->一発AC
ABC9 667点
100_C_50は不可能。
K = 1
先頭文字を、もっとも右側にある辞書順最小の文字と入れ替える。
K = 2
K = 1のときの操作のあと、二番目の文字に対して同じことをする。
一般にこれを繰り返せばよさそうだが、667点が不気味。
-> 一つだけWAのケースがある。
randomでやられているのでコーナーケースではなさそう。たぶん嘘解法?
ヒントどおりにやってみる -> AC
順序固定でのstring比較
順序自由な文字集合の比較
の２つが必要。後者の実装でミスって誤判定->TLEを連発した。
