Union Findの練習及び、テンプレ
//llとはlong long の略です ll parent[100000],depth[100000] ll init(ll n){ REP(i,n){ parent[i]=i; depth[i]=0; } } ll find(ll x){ if(par[x]==x){return x;} else{return par[x]=find(par[x]);} } void merge(ll x,ll y){ x=find(x);y=find(y); if(x==y){return;} if(depth[x]>depth[y]){ par[y]=x; } else{ par[x]=y; if(depth[x]==depth[y]){ depth[y]++; } } } bool same(ll x,ll y){ if(find(x)==find(y)){ return false; } return true; }
ごめんなさい、復習のために直接打ち込んだので、汚いです。。
チーズ
joi2011yo.contest.atcoder.jp
あと少しでAGCなので雑に書きます
割と気力なさげな感じで解きました。もちろんバグ出ました
@Keidaroo
— eiya@受験競プロC++ (@eiya5498513) 2017年6月18日
・問題文をよく読む
・関数分けする
・コメントを書く
・一文字変数をやめる
・要らないものは消す
・コンパイラの警告を見る
あたりをやりましょう（割と適当に言っています）
プロからの助言です、以後バグにひっかかったらこうします
あとVSのエラーの度合い見たいなやつを設定できたというのも進捗の一つ（途中からなぜか表示されなくなったのは気のせい、多分もうすでにその時には治っていたのか（は？））
バグの原因
工場があったとき、そこを通り抜ける場合を入れ忘れていた（数字があっても、条件が満たされない場合、そこから移動する）
あと、別の道で通ったときでチーズ食った時も、countとして足されてしまうので、それぞれにqueueを足さないとだめ
Submission #1359274 - 第１０回日本情報オリンピック 予選（オンライン） | AtCoder
はいよ（雑
しっかりとコメント書いて行ったり、丁寧に解くことがバグ解決のためになるようです
最近バグ直すのが昔より速くなった気がして多少の喜びを感じています（たまたまの模様
暑い日々のオーバーキル解法の詳しい説明
（詳しいとか言いながら雑です、質問があったらしてくださると助かります）
私がかけた６日間という長さに比べて、一日/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の解答の差は、どこでメモるかでした。
「実際どこでめもったって同じじゃないの」とか考えていたのですが、実際その点にいってからメモすると、そこにたどり着くまでに作られたキューも全く同じ計算をさせてしまい、死にます。（分かりにくくてすみません）
一番重要だと感じたことは、こういった罠を避けるために
なるべく前にできることはそこでしてしまうことだと感じました。
非常にあたまがすっきりしました。本当にありがとうございます。
