ABCの幅優先探索について
今日10時間以上きょーぷろやってるのにこれ合わせて1ACしかできてない。。。
どうすればいいのか。。
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日
二分探索(整数)の書き方
難しさ:4 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)は引数としてとらないということが大事らしいです。
つまり返すときにコストを足せばいいので引数としてコストを持ってくるのは間違っているということですね。
うーんやはり何が間違っているのかさっぱり
教えて下さい
AGC15のC問題ほんのちょっとメモ
今更感半端なくてすみません。2完でした。
agc015.contest.atcoder.jp
これです。Cが分かりませんでした。
実装は(面倒くさいので(一番駄目な奴))していないのですが、やり方だけメモります。
一番初めの説明について
ぬすけ君は、N×M のグリッドを持っています。行には上から順に 1 から N、列には左から順に 1 から M の番号がついています。 グリッドの各マスは白か青かに塗られており、Si,j が 1 のとき i 行 j 列のマスは青マス、0 のとき白マスです。 青く塗られた任意の二つのマス a,b について、a からはじめて、現在いるマスから辺を共有する青いマスに進むことを繰り返して b に至るような経路のうち、同じマスを 2 度以上通らないようなものは、高々 1 通りです。
ここの意味さっぱりだったのですが、解説動画みて、要するに
って感じです。一周しないってこと
その次
二次元累積和で青いマスの和をメモリましょう
最重要ポイント
この場合、一周しないということは、木なんですよ。
いや、たくさんあるから森なんですよ。(雑
木の特徴はね、頂点数が辺より一本少ないってことなんですよ
なので、頂点引く辺の数ってやればおけ
その次
辺の数を二次元累積和で求めましょう。
雑とか言わない
深さ優先探索のテンプレ
AOJの深さ優先探索の入門的な問題を解いて、いちいち書くのが面倒と思ったのでテンプレ作ります(ほぼ使えないかもしれないが)
説明は下手です、すみません()
ちなみに、AOJの方のコードはこちら
AIZU ONLINE JUDGE: Code Review
#include<iostream> #include<vector> #include<string> #include<stack> #include<cstdio> #include<algorithm> #define WHITE 0 #define GRAY 1 #define BLACK 2 using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) int n, m[100][100] = { 0 }, nt[100] = { 0 };//ntはその頂点から他の頂点を探索するときに重ならないようにするための物 int color[100] = { WHITE }; int next(int u) { FOR(i, nt[u], n) { nt[u] = i + 1; if (m[u][i]==1){ return i;//もし何かつながる頂点があれば返す } } return -1;//なければ-1を返す } int dfs(int r) { stack<int>S; S.push(r); color[r] = GRAY; while (!S.empty()) { int u=S.top(); int v = next(u); if (v != -1) { if (color[v]==WHITE) { S.push(v); color[v] = GRAY; } } else { S.pop(); color[v] = BLACK; } } return 0; } int main() { cin >> n; REP(i, n) { int u, k; cin >>u >> k;// u--;// REP(j, k) { int muki; cin >> muki;// muki--; m[u][muki] = 1; } } REP(i, n) { if (color[i] == WHITE) { dfs(i); } } return 0; }
ちなみにGRAYとBLACKは分ける必要ないです
boolにした方が軽くなると思います
隣接リストを行列に直してやりましたが、遅いらしいのでこれはあまり使えないかもしれません()