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
この方法神ですね、はい
まとめ
実装にいろいろ戸惑ったのが今回の反省点ですが、学ぶことも多かったので、ま、多少はね？という感じです
前回のDPの問題について
前回のブログでわからないとか言ってた自分ですが、ついに第二の神が現れました！
正直再帰DPの流れちゃんと追えてないんですが…return dp[n] = dp(〜〜)...のところで再帰して一気に一番最後の方まで進んじゃうじゃないですか。でそこまでのcostが加算された値が奥のほうのDPテーブルに入っちゃうわけですが、その経路が最短かはまだ確定してない（続
— htkb (@htkb_) June 4, 2017
ですよね？なのにdpテーブルに書き込まれたら再計算はしない（dp[n]に値があったらすぐreturnしてる）ので、最短ではないコストが書き込まれていってしまうんだと思います。説明下手でわけわかめでごめんなさい＞＜AC→https://t.co/NHOziAYEls
— htkb (@htkb_) June 4, 2017
htkbさん、最後まで本当に有難うございます。
これからまとめていきます。
前回やらかした点について
僕の前回のコードは、はじめに探索した結果だけをdpテーブルに代入するという結果になってました。。
Submission #1322248 - AtCoder Beginner Contest 040 | AtCoder
このコードの場合、すべて一つ飛ばしでいれたときの場合にdpテーブルに代入するという形になっています。
しかしそれだと最小値は求めることができません（全探索どころかほとんど探索できていないから）
それを解決及び理解するために
自分が理解するのにつっかかった点を挙げておきます
- 関数が一回呼ばれるごとに、dp[num]に数値が代入される
- たとえそこまでの行き方が何通りあろうとも、numはnumで一つ（日本語力）
- こういう場合、合計で見てしまっては全体を見るために二つの値では比較できないので、最後から徐々にのぼっていく感じでreturn文で返す。
こんな感じですね。これが自分の間違いです。
こんな考え方で差分のみをとって比較、そして返すを繰り返し、return文ではcostが足されて帰ってくるので、これでACできます。
ちなみにこの写真がもっとも分かりやすいかと
考えのお手伝いになれば幸いです pic.twitter.com/XkhqEz0XQ4
— htkb (@htkb_) June 4, 2017
htkbさん神です。debugの仕方も最高にうまいです。勉強になります。
ただ、htkbさんによるとこの写真はもしかしたら間違いが含まれているかもしれませんがそこのところはご了承ください、だそうです（いや、間違い多分ないけど、htkbさんプロだし）
最後に
コードは自分で明日書いてみます。
深さ優先探索みたいな感じでDPをするときは、最初にたどり着いたところで代入すると間違えますね。
returnするときにどんどん足していって、解を出すことが必要ですね。
このこと知れてよかったとか思う問題でした。
forで解いた方が簡単かもなぁ
atcoderのバチャコンの振り返り
バチャコン開きました。難易度がバラバラですみません。
abc040.contest.atcoder.jp
この問題解けなかったんですよ。恥ずかしすぎる。
Submission #1322248 - AtCoder Beginner Contest 040 | AtCoder
これが私の答えです。WA!!!
おそらくdpに入れている値の持ち方が悪いのだと思います。dp[i] := iからゴールまでの最小コスト と持つようにすればACすると思います(帰宅後やってみます)
— arukuka (@arukuka) 2017年6月3日
arukukaさんという神が表れまして、hackしてくださいました。arurukaさん、有難うございます！！
arukukaさんのコードはこちら
Submission #1322451 - AtCoder Beginner Contest 040 | AtCoder
DP歴4日間の私には、詳しくはわからないのですが、とりあえず価値（この問題の場合はcost）は引数としてとらないということが大事らしいです。
つまり返すときにコストを足せばいいので引数としてコストを持ってくるのは間違っているということですね。
うーんやはり何が間違っているのかさっぱり
教えて下さい
