暑い日々のオーバーキル解法の詳しい説明
（詳しいとか言いながら雑です、質問があったらしてくださると助かります）
私がかけた６日間という長さに比べて、一日/inf時間で解いたアルクカさんはプロです。
本題に入ります
オーバーキル解法の雑解説
字が汚くて申し訳ないですがこんな感じです。
つまり、バウンドの高さが問題になっています。
書き忘れていたのですが、バウンドなしの場合、最大をとっても最小をとってもその間をとっても結果は変わりません。
なので、結局最大または最小をとっていけばいいことが分かります
分かりやすいオーバーキル解法の解説
eiya5498513.hatenablog.jp
あ、あと「イキっているとか思わないでください」
とかいうのは、記事を書き始めたその時は感情が嬉しさによって狂っていて、その結果書いたものなのでそう深く考えないでください（）
というか確かにdpテーブルの次元減らせる。。その発想はなかった
暑い日々AC
※はじめに言っておきますが、皆さんにとってはこの問題は楽勝だというのは知っているので、決してイキリとかそういう風に思わないでください。誰だって自分が解けなかった問題が解けるようになると嬉しいのです。（たとえどんなに簡単な問題であろうと）
感想枠（無駄）
先ほどACしたのですが、泣きそうなくらいうれしかったです。
なぜなら、答えを見ずに最後まで自分で解けたからです（eiyaさんなど他の大先輩からの手は借りさせていただきましたが、直接的な解法は教えてもらってません）
こんなに問題が解けて嬉しいことはなかったので、競技プログラミングのなかで自分にとって最も大きい成功体験だったと思います！
解いている途中は、こんなに時間を無駄にしていいのかとか思っていたのですが、今思えば、そこで解答を見ていた方が時間の無駄だったと思います。
なんか偉そうで申し訳ないのですが、本当に最後まであきらめずに解けて良かったです
はい、偉そうですね（なかったことにしてください）
問題の概要、自分の大まかな考え方
大きな方針
- DP
- その日の最大、最小の派手さを決める
- DPの中でもメモ化再帰
注意するべきところ
それぞれの差の最大値を求めていれば、最適解が求まるとは限らない（何枚目かという違いがあるから）
深さ優先探索は価値はあとで足さないとdpテーブルに入れる時に死ぬ
自分の解答、および方法
Submission #1356472 - 第１２回日本情報オリンピック 予選（オンライン） | AtCoder
変数の説明
- d←日にち k←服の枚数
- maxi,mini←その日に着れる服の派手さの最大値、最小値
- dp←dpテーブル
- n←何日目かを表す
- previous前日の値を入れる
関数DP内の説明および罠
もしn==dの場合0を返すなので、max[d]とかは関数で用いられないので安心
n==0のとき、最初は一個前との差を比べられないのでpreviousに今の値を入れる
ちなみに、previousに今の値を入れることによって、再帰したとき、n+1となるので前の日の値という風になります
手書きですみません。
いろいろ
まず、dpテーブルに計算し終わる前に代入しないこと
dpというのは、基本全探索だっていうことも頭に入れておきます
割と単純なのかもしれないです、ACできて本当に良かったです
ABC64
死にました
Ｄが解けなっかったです。解法はあっていたのに
Submission #1347691 - AtCoder Beginner Contest 064 | AtCoder
はい。vectorの使い道を間違えました。
vector.erase(a,b)
において、eraseされるのは、a以上b未満でした。はい
bのところを１足してやったら通りました
Submission #1348551 - AtCoder Beginner Contest 064 | AtCoder
あと、string.erase(a,2)ってやることでa文字目から２文字消せることを知りました。
知識不足でレートがおちて悔しすぎます。教えて下さったeiyaさん、有難うございます！
暑い日々
まだACしてはいませんが、何がバグっていたかだけは分かったので、それのメモです
自分の答え、方針
Submission #1338473 - 第１２回日本情報オリンピック 予選（オンライン） | AtCoder
方針としては、
- それぞれの温度の最小、最大の派手さをメモる
- そのあと、後ろから差分をとっていき、最大のものをとる
あっ
差分をとっていったら、一日に何枚もの服を着ることになってしまっている。。。
あと、差だけを考えていたら、最適解は求まらない。。
やはり、最小、最大の派手さをメモるのは変えずに、二次元DPでやる必要性があるようです。
しかし、今の自分では実装力が足りないので、他人のコードを見て、勉強することにします。（もちろんそのあと実装してみます）
雑で、すみません（定期）
前回の記事のBFSについて
まず初めに、教えて下さったeiyaさん、arukukaさん、本当に有難うございます（いつもありがとうございます）
eiyaさんのブログです（勝手に引用してしまいました、申し訳ないです）
前回の記事で、TLEとACの解答の差は、どこでメモるかでした。
「実際どこでめもったって同じじゃないの」とか考えていたのですが、実際その点にいってからメモすると、そこにたどり着くまでに作られたキューも全く同じ計算をさせてしまい、死にます。（分かりにくくてすみません）
一番重要だと感じたことは、こういった罠を避けるために
なるべく前にできることはそこでしてしまうことだと感じました。
非常にあたまがすっきりしました。本当にありがとうございます。
ABCの幅優先探索について
今日１０時間以上きょーぷろやってるのにこれ合わせて１ACしかできてない。。。
どうすればいいのか。。
C: 幅優先探索 - AtCoder Beginner Contest 007 | AtCoder
これです
簡単なはずなのに。。。。頭が痛い。。
まずBFSについて
while文の外で、最初の値をqueueで固めておく
中では、最初の値を取り出す、消す
で、どんどんキューに追加していってキューがなくなるor目標が達成されるまで続く
って感じ
頭いたいのでこの辺で
TLE解答とAC解答の違い、質問
この二つの違いは、
retu[nowy + m1[i]][nowx + m2[i]] = false;
というコードがどこに入るかだけで、それ以外の違いがないわけなんです。
どっちでも同じじゃねとか1時間たった今でも思っています。時間を無駄にしている気がする
誰か何が違うのか教えて。。
追記：eiyaさん、arukukaさん、有難うございます！無事理解できました（次のブログに書きます）
とりあえず頭を休めます。雑ですみませんでした
訂正：TLEのことをWAと書いていました。。申し訳ないです。（普段の慣れでWA,かっこよくない）
ABC63のD問題について
今回も今更感満載ですが復習として書きます。
ABCのCまで早解きできてある程度いい成績がとれたのではとか思っています。
Dは最後まで解くことができず、無理やりな法則立ててました。
考察してから、解かないと（これ前も言ってた）
では本題に入ります
問題、自分の解答
WA解答
Submission #1335627 - AtCoder Beginner Contest 063 | AtCoder
AC解答
Submission #1335839 - AtCoder Beginner Contest 063 | AtCoder
解き方
まず、a=a-bをしましょう（すべての要素からbをひき、中心となるやつにはa-bを引けばよくなるから）
それで、n回攻撃するとし、すべての要素からbを引きます
各要素からaを何回引く必要があるのか計算します
それがn回以下ならおけ、大きければ足りないのでダメという感じで
答えをkotaeと置くと、kotae以上の回数行ったらそれはおけで、未満ならたりません
あれ、これってある地点が境になっていません？？
にぶたんです、にぶたん（使ったことないとかナイショ）
自分がWA解答で間違えたところ
b*nを何回も引いてしまいました。。。
あと、掛け算するときに、オーバーフローする可能性があるという事を記憶しておきます。
もうlong longですべて済ませた方がいいのかもしれない
出力するのはokの値でした。。すみません
27行目のhp[i]>0が真だったときにhp[i]から複数回b*countが引かれてしまうところ、出力する結果はok、bが大きいときにb*countがオーバーフローするの3点だと思いますーhttps://t.co/0ABxRqhAus
— フェリン (@ferin_tech15) 2017年6月7日
フェリンさん、有難うございます！
Tips
にぶたんのチェックのところは別の関数で作った方がいい、確かにきれいで見やすくなります。
にぶたんはチェック関数を別にするとコードの見通しが良くなります。参考までに。
— やみとも (@wabisuke2718) 2017年6月7日
やみともさんも有難うございます！
二分探索の方法
【めぐるのアルゴリズム講座】
— 因幡めぐる@競技プログラミング (@meguru_comp) 2016年2月9日
二分探索（整数）の書き方
難しさ：４ pic.twitter.com/LGLbkS0D7l
この方法神ですね、はい
まとめ
実装にいろいろ戸惑ったのが今回の反省点ですが、学ぶことも多かったので、ま、多少はね？という感じです
