3月21日
まえがき
ウーンなんか書くことあるかな。
あーじゃあまずコンテストの話
今日はAGC043がありましたね〜〜
みなさんどうでしたか？僕はレートが60ぐらい上がりましてホクホク顔です。明日のABCが怖いですね（日付的には今日)
お気持ち.com
アーロンチェアの話最近毎日してるじゃないですか、買うことができそうです。やったね。
自分のお金が10万円あって、残り10万円程度必要なんですけど、母様に一旦払っておらってもいて、毎月の仕送りから返せそうだ！！と説明したことでお金を貸してくれるとの許可が出ました。
元々親の金なのですが、そのへんは気にしないで。
言い訳ですが、僕は大学入るまで親におねだりしてものを買ってもらったことが基本的になく、他の3人の兄弟は結構ものを買ってもらっていた気がするので、それの埋め合わせをしているような気持ちです。
まぁ、親の金を使わないといけないなんて言うルールはないのですが、許してください。
アーロンチェアを買うって言ったけど、嘘だ。
エンボディチェアとアーロンチェアをもう一度視座して決めます。
それと、勉強のお話について。
例えば、本に今日から二週間、これこれをしようみたいなことが書いてあることって結構あるじゃないですか。
で、そういう時たいてい思うんですよ「今モチベ高いからそんなことやってる暇ない。二週間は貴重な時間だ」って。
でもさあああああ
なんやかんや2週間立ってみると気づくんですよね「あれ、なんか二週間会ったけど大して精進出来てなくない？」って。
2週間っていう期間は長いようで短くて、以外と精進出来ないんですよね。
思い返せば春休みに入った頃の僕は、結構目標を立てていたような気がします。
ちょっと過去のブログ漁ってみましょうか。
2月7日の記事これ、一ヶ月と10日くらい前の記事ですね。
今後の活動のところを見てみると、めちゃくちゃいろんなことをやろうとしています。
無謀ですね。
その10日後の記事がこちら
急に気持ちが変わって競プロだけしようとしていますね。
偉い。今のお気持ちはこれです。
かと言って結構不安もあって、本当に今自分が競プロに集中できているのかっていうのがあります。
まぁ、なんとかしたい、なんとかなってほしいですね。
先程読んだ本には、プロフェッショナルになるには1万時間の精進が必要と書いてありました。
そして、さらに1万時間かければ必ずスペシャリストになれるとも書いてあります。
私はこの言葉を信じます。
まぁ、1万時間それに自分が時間を使えるなら、それをおそらくは好きだからきっと上達していることでしょう。逆に1万時間書けれないようなことは本来興味のないことなんでしょうね。
とりあえず人生何もかも上手くいってほしいな。
今ボクは割と幸せでして、なぜかと言うと
- Twitterで知り合った沢山の人と現実で出会うことができている
- バイトをしないで生きていけている
- 親も自己投資することについて何も文句をいってこない
コンな感じの要因があるからです。
インターンしたいですね。勉強してお金稼ぎたい。
いや、お金は稼がなくてもやっていけるなら稼がなくていいのですが、インターンで社会に出て色々教えてもらいたいです。
そしてさらに、せっかくインターンに行くならタダ働きはしたくない。よって勉強してお金稼ぎたいという言葉が出てきました。
今日解いた問題
ABC075 C-Bridge
[橋、連結無向グラフ]
橋の問題です。他人の記事からうばってAC
昨日の記事にも載せた問題ですね。
今日はこの問題をDFSじゃなくてBFSを使って解いてみました。
それがこのコード
なんてことはない。ただDFSの部分をBFSにしただけです。
ところでこのコーど、どうして元はDFSだったのかって考えてみたんですが、特に思いつきませんでした。
とはいってもまあ、思いつきませんでしたってだけでは味気ないので、DFSとBFS見比べてみましょうか。
DFSを用いたコード
const int limit = 50; int n, m; int a[limit], b[limit]; bool graph[limit][limit]; bool visited[limit]; void dfs(int v){ visited[v] = true; for (int v2 = 0; v2 < n; v2++) { if (graph[v][v2] == false) continue; // vとv2をつなぐ辺が無いよ if (visited[v2] == true) continue; dfs(v2); } }
BFSを用いたコード
ll graph[50][50]; bool visited[50]; queue<int> que; void bfs(int v){ while(!que.empty()){ int node = que.front(); que.pop(); for(int i = 0; i < 50; i++){ //for(auto x:graph[node]){ bool x = graph[node][i]; if(x == false) continue; if(visited[i] == true) continue; visited[i] = true; que.push(i); } } }
個人的には、再起を用いないのでBFSの方が好きです。
この問題の名前で調べて出てきた記事が深さ優先探索のほうが多かったんで、何か深さ優先探索のほうが書きやすいのかな…っておもったのですが、こう見比べてみてもやはり違いがわかりませんね。
残念。
見比べれば何かがわかると思ったのですが…
AGC043 A- RAnge Flip Find Route
[BFS,動的計画法,幅優先探索,DP]
この問題の重要な、僕でも解ける原因となった要素は右か下にしか移動できないってことですかね。
これのおかげで、黒から黒に移動するときはまとめて1回だけの操作で白にできることが分かりました。
黒から黒に動く時、最初踏んだ黒から最後に踏む黒を囲むように長方形で通ったマスを囲んでみて、そこを白にするようにしてみると、なんと通る必要がある白いマスは必ず長方形の外にあるようになっているんです！！
そういうわけで、白いマスから黒いマスへ行く時だけ必要な操作回数が+1されるのだ！！
コンな感じのを幅優先探索の迷路へのゴールの最小手数と同じように実装したら解けました。
コンテスト後のTLを見てみるとDPDDPDPDPPEDPDPP!! ってDP!!って言葉がたくさん見られたのでもしかしたら僕のコードもDPかもしれません（本人は幅優先探索のつもりでときました。)
コード置いておきます
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } const int dy[2] ={1,0}; const int dx[2] ={0,1}; const int limit_h = 105; vector<string> field(limit_h); int h, w; int cost[110][110]; queue<pair<int,int>> que; void bfs(void) { while(!que.empty()){ int y = que.front().first; int x = que.front().second; // こいつらから1手すすめる que.pop(); bool IS_BLACK = false; if(field[y][x] == '#') IS_BLACK = true; // 白で次行く場所が黒なら +1; rep(i,2){ int ny = y + dy[i]; int nx = x + dx[i]; int n_cost = cost[y][x]; if(IS_BLACK == false && field[ny][nx] == '#'){ // 1つ前が白で、次行くのが黒ならcost + 1 n_cost ++ ; } if(chmin(cost[ny][nx],n_cost)){ que.push(make_pair(ny,nx)); } } } } int main() { cin >> h >> w; rep(i,h) cin >> field[i]; bool is_black = false; rep(i,h) rep(j,w) cost[i][j] = 100100; if(field[0][0] == '#') is_black = true; if(is_black) cost[0][0] = 1; else cost[0][0] = 0; que.push(make_pair(0,0)); bfs(); cout << cost[h-1][w-1] << endl; }
まあ読みたきゃ読んで
