Atcoder Beginners Contest 088 : D - Grid Repainting
最近、蟻本を買ったので、この記事に貼られている問題を練習としてやっています。
qiita.com
今日は幅優先探索 (BFS) の問題をやりました。
D - Grid Repainting
迷路があって、通れないマスをどれだけ増やしても、すぬけ君はゴールに辿り着けるのか、という問題です。すべてのマスから、初期の通れないマスの数とゴールまでの最短経路から引いてやればOK。なので、最短経路を普通の BFS でも止めたら終了です。
#include<bits/stdc++.h> using namespace std; typedef pair<int, int> P; int main(){ int H, W, i, j, d = 0; vector<int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1}; cin >> H >> W; vector<vector<char>> s(H, vector<char>(W)); vector<vector<int>> checked(H, vector<int>(W, 0)); for (i = 0; i < H; i++){ for (j = 0; j < W; j++){ cin >> s.at(i).at(j); if(s.at(i).at(j) == '#') d++; } } P pos = P(0, 0); queue<P> quepos; quepos.push(pos); while(quepos.size()){ pos = quepos.front(); quepos.pop(); for(i = 0; i < 4; i++){ int x = pos.first + dx.at(i), y = pos.second + dy.at(i); if(x >= 0 && x < W && y >= 0 && y < H && s.at(y).at(x) == '.' && checked.at(y).at(x) == 0){ checked.at(y).at(x) = checked.at(pos.second).at(pos.first) + 1; quepos.push(P(x, y)); if(y == H - 1 && x == W - 1){ cout << H * W - d - checked.at(y).at(x) - 1 << endl; return 0; } } } } cout << -1 << endl; }
まとめ
少しずつ、自力で BFS を実装できるようになってきた。
AtCoder Beginner Contest 169 (ABC169) ふりかえり
二週間ぶりのABCでした。今のレートが300ちょいくらいなので、後数回、うまくいけば今回で茶色になってやろうと闘志を燃やしていたのですが、結果はB問題で"WA"を連発し、C問題も解けず、2完に終わりました。
結構 "WA" を出しやすいような問題が多く、出題者への苛つきを感じずにはいられませんでした。一方で、オーバーフローや浮動小数点型の誤差など、プログラミング言語そのものをしっかりと理解していればスラスラ解けたであろう問題だったので、とても勉強になったとも言えます。
A - Multiplication 1
ただの掛け算だったのでイージーでした。
#include<bits/stdc++.h> using namespace std; int main(){ int A, B; cin >> A >> B; cout << A * B << endl; return 0; }
B - Multiplication 2
最初にゼロ判定を行う。ゼロが出たらゼロを出力して終了。
次に、順々にかけていって10^18を超えたら - 1、オーバーフローしてしまうので、割り算の形にしておかないといけない。
#include
using namespace std;
int main(){ long long N, i, a; bool flag = false; cin >> N; vector<long long> A(N); for (i = 0; i < N; i++){ cin >> A.at(i); if(A.at(i) == 0){ cout << 0 << endl; return 0; } } long long Asum = A.at(0); for (i = 1; i < N; i++){ if(Asum > 1000000000000000000ll/A.at(i)){ cout << -1 << endl; return 0; } Asum = Asum * A.at(i); } cout << Asum << endl; return 0; }
C - Multiplication 3
できなかった。めちゃくちゃ悔しい。少数の部分で誤差が出ているので、100をかけて整数同士で計算してから、100で割るという戦略をとった。これが大間違いで、100をかけて整数型にするときにも、誤差の影響が出る場合があるようです。文字列として扱った後に計算するか、微小な数字を足してやることで解決できるそうです(下記リンク参照)。知らなかった。。。
まとめ
非常に悔しい。レートは変動無しでした。次こそはっ!
Atcoder Beginners Contest(A. Fifty-Fifty / B. Ordinary Number / C. Divide the Problems)
解答
A. Fifty-Fifty
map で文字の数を数えた。map のサイズと一つの要素の数が 2 であれば、"Yes" になります。
#include<bits/stdc++.h> using namespace std; int main(){ char c; map<char, int> S; for(int i = 0; i < 4; i++){ cin >> c; S[c]++; } if(S.size() == 2 && S[c] == 2){ cout << "Yes" << endl; return 0; } cout << "No" << endl; return 0; }
B. Ordinary Number
普通に for 文でカウントしました。
#include<bits/stdc++.h> using namespace std; int main(){ int n, i, cnt = 0; cin >> n; vector<int> p(n); for(i = 0; i < n; i++) cin >> p.at(i); for(i = 1; i < n - 1; i++){ if((p[i - 1] < p[i] && p[i] < p[i + 1]) || (p[i + 1] < p[i] && p[i] < p[i - 1])){ cnt++; } } cout << cnt << endl; return 0; }
C - Divide the Problems
真ん中の数字の差分が取りうる K の数になります。配列をソートして、真ん中の要素を引き算。
#include<bits/stdc++.h> using namespace std; int main(){ int N, i; cin >> N; vector<int> d(N); for(i = 0; i < N; i++) cin >> d.at(i); sort(d.begin(), d.end()); cout << d.at(N / 2) - d.at(N / 2 - 1) << endl; return 0; }
まとめ
A と B にしてはわりと時間がかかった。
AtCoder Beginner Contest 168 (ABC168) ふりかえり
こんばんは、日曜日に AtCoder Beginner Contest 168 がありました。
問題の名前が好きでした。作者は点々が好きなのだと思います。
結果は可もなく不可もなくといった感じです。欲を言うともう少し早く C 問題をときたかった。
軽くおさらいしていきます。
A - ∴ (Therefore)
atcoder.jp
普通に条件分岐で解きましたが、swich-case の方がスマートでした。
#include<bits/stdc++.h> using namespace std; int main(){ string N; cin >> N; if(N.at(N.size() - 1) == '3'){ cout << "bon" << endl; return 0; }else if(N.at(N.size() - 1) == '0' || N.at(N.size() - 1) == '1' || N.at(N.size() - 1) == '6' || N.at(N.size() - 1) == '8'){ cout << "pon" << endl; return 0; }else{ cout << "hon" << endl; return 0; } return 0; }
B - ... (Triple Dots)
atcoder.jp
これも条件分岐でちょちょいのちょいですね。テストの出力が "nikoand..." になったのは少し面白かったです。
#include<bits/stdc++.h> using namespace std; int main(){ int K; string S; cin >> K; cin >> S; if(S.size() <= K){ cout << S << endl; return 0; }else{ for (int i = 0; i < K; i++){ cout << S.at(i); } cout << "..." << endl; return 0; } return 0; }
C - : (Colon)
atcoder.jp
あまり見ないタイプの問題だという印象。自分はそれぞれの針先の x 座標と y 座標を求めてからピタゴラスの定理(三平方の定理)を使って長さを求めました。終わってからTLを見ているとどうやら余弦定理を使う解法が最もスマートなようです。Twiter でトレンド入りしてて笑いました。
#include<bits/stdc++.h> using namespace std; int main(){ double A, B, H, M, x1, x2, y1, y2, L; double PI = 3.141592653589793238; cin >> A >> B >> H >> M; x1 = A * sin(H * 2 * PI / 12 + M * 2 * PI / 60 / 12); y1 = A * cos(H * 2 * PI / 12 + M * 2 * PI / 60 / 12); x2 = B * sin(M * 2 * PI / 60); y2 = B * cos(M * 2 * PI / 60); L = pow(pow((x1 - x2), 2) + pow((y1 - y2), 2), 0.5); printf("%.11f\n", L); return 0; }
まとめ
C問題をもっと早く解きたかった。あと、グラフ理論についてそろそろちゃんと勉強しようかと思う。
AtCoder Beginner Contest 135 (A - Harmony/B - 0 or 1 Swap/C - City Savers)
酒飲みながらでも C 問題まで解けるようになった。
解答
A - Harmony
平均ととったやつが答えで、整数にならないやつが "IMPOSSIBLE" になる。
#include<bits/stdc++.h> using namespace std; int main(){ long long A, B; cin >> A >> B; if((A + B) % 2 != 0 || (B + A) % 2 != 0){ cout << "IMPOSSIBLE" << endl; return 0; } if(A > B){ cout << (A + B) / 2 << endl; }else{ cout << (B + A) / 2 << endl; } return 0; }
B - 0 or 1 Swap
atcoder.jp
ソートして、下の配列と比べる。異なる部分が 0 個か 2 個なら "YES"。酔っぱらいおじさんだから "Yes"・"No" にしてしまって "WA” 連発した。
#include<bits/stdc++.h> using namespace std; int main(){ int N, i, a; cin >> N; vector<int> p(N), _p(N); for (i = 0; i < N; i++) { cin >> p.at(i); _p.at(i) = p.at(i); } sort(_p.begin(), _p.end()); int count = 0; for (i = 0; i < N; i++){ if(_p.at(i) != p.at(i)) count++; } if (count == 2 || count == 0){ cout << "YES" << endl; }else{ cout << "NO" << endl; } return 0; }
C - City Savers
atcoder.jp
1の街のモンスターは1の勇者しか倒せないので、勇者はまず 1 の街に向かう。残った倒せる回数で 2 の街に向かう。次に 2 の勇者が 2 の街に残っているモンスターを倒しにいく。っていうのを繰り返す。
#include<bits/stdc++.h> using namespace std; int main(){ long long N, i, b1, b2, count = 0; cin >> N; vector<long long> A(N + 1), B(N); for (i = 0; i < N + 1; i++) cin >> A.at(i); for (i = 0; i < N; i++) cin >> B.at(i); for(i = 0; i < N; i++){ b1 = B.at(i); //勇者が倒せる人数 B.at(i) = max(0ll, b1 - A.at(i)); //iの街で討伐作業を行った後の勇者の討伐可能数 count += min(A.at(i), b1); A.at(i) = max(A.at(i) - b1, 0ll); //討伐された後の、iの街のモンスターの数 b2 = B.at(i); count += min(A.at(i + 1), b2); A.at(i + 1) = max(A.at(i + 1) - b2, 0ll); } cout << count << endl; return 0; }
まとめ
できる問題をいくら "AC" しようが成長しねえんだよ、ばーかばーか(反省しています)。
ひとり酒とはこんなにも素晴らしいものだったのか(A - Transfer and B - Uneven Numbers)
こんばんは、連日投稿できておりいい感じです。
学生時代は一人でお酒をあまり飲まなかったのですが、最近、ひとり酒のご利益を理解しつつあります。
研究の方が確実にしんどかったのですが、社会人の方が自分の時間も頭の中がグルグルしています。
研究より、人間関係の方がゴールが無い。
で、酒飲んだら頭の中のグルグルが無くなったというだけです。すごいですね、酒。
ちなみに、オンライン飲み会の時に余ったウイスキーと炭酸水を飲んでいました。
一人で酔っ払っているってなんなんですかね、よくわからないけどきもちいいです。
きもちいいついでにAtCoderの問題を解いていたのですが、頭回らなさすぎでイライラしました。
でも酒飲みなおしたらきもち良くなりました。すごいですね、酒。
atcoder.jp
Cの水が全部無くなるケースにだけ注意したら、普通の引き算。
#include<bits/stdc++.h> using namespace std; int main(){ int A, B, C; cin >> A >> B >> C; cout << max(0, C - A + B) << endl; return 0; }
atcoder.jp
桁数を数えて、for文で奇数判定をして足していく。各桁に存在する数字は9に10の累乗をかけたものになります。求めた桁数については N - 10^? + 1 を足してやり終了。
#include<bits/stdc++.h> using namespace std; int main(){ int N; cin >> N; int Keta = 0, _N = N, Sum = 0; while(_N != 0){ _N /= 10; Keta++; } for(int i = 1; i < Keta; i += 2) Sum += 9 * pow(10, i - 1); if(Keta % 2 != 0){ Sum += N - pow(10, Keta - 1) + 1; } cout << Sum << endl; return 0; }
終わりに
社会人やっていけるのだろうか。技術だけ磨いておいて評価されると嬉しいのですが。。
あと、クソ記事でもとりあえず毎日続けていくのでよろしくお願いいたします。
コロナ騒動下、ホテル暮らしの時短・健康食生活()
みなさんいかがお過ごしでしょうか。
私は4月の途中くらいから新人研修でホテルに詰め込まれ生活をしています。
ホテルに引っ越しをして最初の一週間くらいはカップ麺をすすっていたのですが、
お腹の調子やらお肌の調子やらが急激に悪化して、「これはいかん。少しでもマシな食生活をしなければ」と思い始めました。
ただ、調理はできないし、新しい環境でなるべく食事に時間を割きたくないという思いもあります。
最近は少しずつ栄養バランスとやらを考えて色々買い物をしていますが、栄養へのリテラシーが低い現状です。
今回は、自分自身の現状把握も兼ねて最近の私の食生活について書いていこうかなと思います。
ちなみに、ホテルの部屋についている備品は冷蔵庫と電気ケトルのみです。
フルーツとシリアルと牛乳
フルーツは、とにかくビタミンなんちゃらと食物繊維とかが含まれているので最強だと思っています。フルーツグラノーラも同じです。加えて栄養に詳しい人たちが多分頑張っているのでもっと最強ですね。アホみたいにバナナとフルーツグラノーラを食っています。正直、こいつらいっぱい食べといたら健康面は大丈夫と過信している。
炭水化物はご飯・餅・パン
米に関してはサトウのご飯を代表格として、電子レンジやお湯で温めるタイプのものがありますね。部屋には電気ケトルがあるので、僕はそこにぶち込んでいます。日本国民として、このような状況でもコメが食べられるのは幸せですね。電気ケトルからすると、たまったもんじゃないと思いますが。
餅に関しては、タッパーにお湯を注いでいます。電子レンジやお湯で茹でたときと比べると柔らかさは微妙ですが、普通に醤油かけて食えます。
パンは単体でメシとして成立するのがすばらしいです。特に調理がいらないので、最近は餅とか米よりパンが多くなりがちです。ただ、賞味期限が短いのがあまり良くない点です。備蓄などには向きません。
レトルトカレー
めちゃくちゃいいです。カレーって栄養バランスもうまさも両方兼ね備えた最強の食材だと思うんです。しかも、いろいろな種類が売っているので飽きにくい(?)。電気ケトルがあるのでそれにぶち込んで温めています。ご飯と合わせてもいいですが、最近は調理時間が少ないという理由から食パンにつけて食べています。
ウインナー
ガッツリ肉が食べたいけど焼く設備がないので、代替案としてウインナーを食べています。熱を入れて食べたことしかありませんでしたが、生でも食べられるって最近知りました。普通に美味しい。ちなみに、お気に入りは香薫です。パリッとするウインナーのなかではお財布に優しいので。
話は変わるのですが、ウインナーってソーセージの一種らしいですね。
www.ucoop.or.jp
発酵食品
上記のような健康食材(?)があるのですが、やはりカップラーメンやお菓子も食べてしまうので、腸内環境は少し心配です。なので発酵食品にも注目しています。そう、納豆とヨーグルトです。最近パン主体になってしまったので、納豆に関してはあまり買わないようになったのですが、米派の人からすれば最強の食材の一角ですよね(記事書いてたら食べたくなってきた)。ヨーグルトに関しては手軽に食べられることはもちろん、バナナやグラノーラとのコンボも可能なので買ってしまいがちです。
最後に
カップ麺生活からは少しマシになりました。栄養バランスに関してはなんとなくで考えているので、一度しっかりと計算してフィードバック記事を書いて、この記事をボコボコに批判する記事を書く予定。目指せ、栄養ますた〜〜。