ABC189 参加記

AtCoder Beginner Contest 189

お久しぶりです．Nafmoです．Nafmoって名乗る回数も減りましたね...
さて，久しぶりに参加記を書きたくなったので書きます．理由としてはアウトプットしてミスを減らそうという流れですね．

A:Slot

これはstringで受け取ってS[0]==S[1]==S[2]を判定するだけです．

B:Alcoholic

これです．教訓ですが...

小数を小数のまま扱わない でしたね．

割り算は誤差を生みます．主に2ⁿ以外で割ると厳しいはずです(ほんまか？)そのため割るのではなくすべての値に掛け算をします．すると大小関係は保持されるので問題なく処理できます．今回の場合は，%で表示されているため，100で割らずに残りの値(上限X)に100を掛けてあげれば問題なしです．後は単純にシミュレーションをすればいいだけです．

C:Mandarin Orange

これは全探索をします． 二重ループを使って，1重目で範囲の始点を決め，その要素を持ちます．そこから2重目で範囲の終点を決めます．その際に，先の保持している要素と比べ小さい方を持ちます．こうして範囲をスライドしながら最小値を更新します．要素数は1でも問題ないです．範囲の数とその最小値の値をかけたものの最大値が答えです．

範囲の中にある最小値✕範囲 がその領域をいっぱいいっぱい使うときの最善のはずだからです．

D:Logical Expression

これはメモ化再帰を使いました． DP(n,y)という関数としたときに，n個目までで，yが1(true) or 0(false)になるときの{x1,x2...xn}のパターン数を返す関数としました．

• n個目のyがtrueのとき
  • ANDのときはn-1個目のyがtrueでなくてはならない
  • ORのときはn-1個目のyがtrueなら2パターン，falseなら1パターン存在する
• n個目のyがfalseのとき
  • ANDのときはn-1個目のyがtrueなら2パターン，falseなら2パターン存在する
  • ORのときはn-1個目のyがfalseでなくてはいけない のような形で掛け算をしてメモ化をするとできます．

E以降

復習がんばります......

目標は水色！頑張るぞい！