前回の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）は引数としてとらないということが大事らしいです。
つまり返すときにコストを足せばいいので引数としてコストを持ってくるのは間違っているということですね。

うーんやはり何が間違っているのかさっぱり
教えて下さい

今回の教訓

無駄なものは引数として取らない方がいいということですね。コストはあとで足せばいいもの。

まあしばらくは型に慣れていこうかなとか思います

打倒！JOIバトンレベル５！！！

あとdiffをしようというアドバイスをいただいたので、早速vimを入れてみます。容量的に大丈夫だと願う。

追記：arukukaさんのことをarurukaと書いていました。。。本当に申し訳ないです。

AGC15のC問題ほんのちょっとメモ

今更感半端なくてすみません。２完でした。
agc015.contest.atcoder.jp
これです。Cが分かりませんでした。

実装は（面倒くさいので（一番駄目な奴））していないのですが、やり方だけメモります。

一番初めの説明について

ぬすけ君は、N×M のグリッドを持っています。行には上から順に 1 から N、列には左から順に 1 から M の番号がついています。 グリッドの各マスは白か青かに塗られており、Si,j が 1 のとき i 行 j 列のマスは青マス、0 のとき白マスです。 青く塗られた任意の二つのマス a,b について、a からはじめて、現在いるマスから辺を共有する青いマスに進むことを繰り返して b に至るような経路のうち、同じマスを 2 度以上通らないようなものは、高々 1 通りです。　

ここの意味さっぱりだったのですが、解説動画みて、要するに

って感じです。一周しないってこと

その次

二次元累積和で青いマスの和をメモリましょう

最重要ポイント

この場合、一周しないということは、木なんですよ。
いや、たくさんあるから森なんですよ。（雑
木の特徴はね、頂点数が辺より一本少ないってことなんですよ
なので、頂点引く辺の数ってやればおけ

その次

辺の数を二次元累積和で求めましょう。
雑とか言わない

最終的に

頂点から辺の数を引きましょう

いや、この問題面白いですね。
ただ実装力的に時間内でできるかな？（なら実装しろ

雑ですみませんでした。
質問があれば気軽にtwitterの方へお願いします

深さ優先探索のテンプレ

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にした方が軽くなると思います
隣接リストを行列に直してやりましたが、遅いらしいのでこれはあまり使えないかもしれません（）