ABC 101 (AtCoder Beginner Contest 101) 参加結果 & 解説
参加結果
参加結果は、ABCの3完。
D問題は、かなり粘ったけど力及ばず。
今回のD問題は、いつもより解ける気がしたので悔しい。
レートの上がりが何故か今回良かったので、運が良ければ、次のABCで緑に上がれるかも。
次に期待。
解説
自分で解けたものは、解説。
ABC101 A - Eating Symbols Easy
問題概要
最初、0の数がある。
入力として、'+' か '-' のどちらかの記号を合計で4つ受け取る。
'+' を受け取った場合、数を+1する。
'-' を受け取った場合、数を-1する。
数は最終的にいくらになるか。
解法
string型で入力を受け取り、1文字ずつ確認して答えを求める。
#include <bits/stdc++.h> using namespace std; int main() { string s; cin >> s; int ans = 0; for (int k = 0; k < (int)s.size(); k++) { if (s[k] == '+') ans++; else ans--; } cout << ans << endl; }
ABC101 B - Digit Sums
問題概要
整数 n に対して、n を十進法で表したときの各桁の和を S(n) で表すことにする。
たとえば、S(101)=1+0+1=2 である。
整数 N が与えられたとき、N が S(N) で割り切れるかどうかを判定せよ。
解法
問題としては、各桁の和を求められるかという問題。
各桁の和は、1桁ずつ分割していけばいいので、10で割った余りを足していけば良い。
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; int s = 0, tmp = n; while (tmp > 0) { s += tmp % 10; tmp /= 10; } cout << (n % s == 0 ? "Yes" : "No") << endl; }
ABC101 C - Minimization
問題概要
1〜N の数列が与えられる。以下の操作を最小回数繰り返すことにより、全部 1 にせよ。
* 数列のうち、連続したk個の要素を選択し、選択した要素の中の最小値で置き換える。
最小回数は、いくらか？
解法
この問題は、難しく考える必要がない。
例えば、このような数列が与えられ、k=3と与えられた場合。
1を含んだ3つを選択していき、すべてを1に変えればいい。
最初の選択で、1を含んだ3つを変更すると考え、その後は、1を含んで2つを変更させていくと考える。
この場合だと、最小回数は、3である。
このように、1を1つだけ含むように選択していくと、最小回数が分かる。
#include <bits/stdc++.h> using namespace std; int main() { int n, k; cin >> n >> k; int ans = 0; while (1) { if (n <= 0) { cout << ans << endl; return 0; } if (ans == 0) { ans++; n -= k; } else { ans++; n -= (k - 1); } } }
ABC101 D - Snuke Numbers
問題概要
整数nに対して、各桁の和をS(n)で表す。
正の整数nであって、n < m であるような任意の整数mに対して、n / S(n) <= m / s(m) が成り立つ数を、すぬけ数という。
整数Kが与えられたとき、すぬけ数を小さい方からK個列挙せよ。
解法
自分は、解けなかったが、こちらの解説が分かりやすかった。
分かりやすい解説
自分も、参考にさせて頂いた。
簡単に解説すると、0からすぬけ数を求めていくのではなく、すぬけ数の候補をあらかじめ用意しておき、すぬけ数に当てはまらない数を除いていくというもの。
自分は、0からすぬけ数を求めていこうとしていたので、計算に時間がかかってTLEや要素が足りずWAになったりした。
#include <bits/stdc++.h> using namespace std; long long f(long long n) { long long res = 0; while (n > 0) { res += n % 10; n /= 10; } return res; } double g(long long n) { return (double)(n)/f(n); } int main() { vector<long long> res; long long base = 1; // まずは候補を (1〜150)99999 的なやつを全列挙 for (int k = 0; k < 15; k++) { for (int l = 1; l < 150; l++) { res.push_back(base * (l + 1) - 1); } base *= 10; } sort(res.begin(), res.end()); res.erase(unique(res.begin(), res.end()), res.end()); // ダメなやつを除く for (long long k = 0; k < res.size(); k++) { for (long long l = k + 1; l < res.size(); l++) { if (g(res[k]) > g(res[l])) { res.erase(res.begin() + k--); break; } } } long long num; cin >> num; for (long long k = 0; k < num; k++) { cout << res[k] << endl; } }
反省
そろそろ4完したいなーというお気持ち。
前回と今回のD問題は解ける気がしたが、解けなかったので、過去のD問題を漁る予定。
ただ、いい解説がなかったりするので、どうしようか迷い中＞＜
Hatena Blog始めました
Hatena Blogの開設
今日からHatena Blogを始めることにしました。
始めた理由は、下記の4つになります。
自分の考えを保存しておく場がほしかった
イベントに参加したときや、開発を行ったとき、アイディアを出したときに、その時の考えや、考えに至るまでのプロセス、その考えについて自分がどのように感じたかを保存しておきたいと考えました。
いわゆる日記的な使い方をしようと考えています。
保存しておきたい理由としては、
- 他人に詳細を聞かれた確実なフィードバックを行えるように
- イベントに参加する時のLTなどでの活用
- 就活の時に使いたい
という感じになっています。
自分の考えを言語化する力をつけたい
先日夏季インターンシップの申し込みをする上で、ESの作成を行ったのですが、 自分は言語化する力が、かなり乏しいなと感じました。
そこで、記事を作成することで、自分の考えを言語化する力の向上に繋げたいと考えました。
技術以外のことについてもOutputの場が欲しかった
技術的な話題については、Qiitaにて記事にしています。
ですが、Qiitaにて、日記的な記事であったり、技術以外の趣味の記事は投稿することは難しいとの話です。
そこで、Hatena Blogを始めることで、技術以外に関しても自分の意見をOutputしていきたいと考えました。
有識者のフィードバックが欲しい
特に、AtCoderなどの競技プログラミングについて記事にすることで、アルゴリズムやコーディングについてフィードバックを頂ければありがたいです。
Hatena Blogで記事にしようとしていること
AtCoderの参加記
週に1回のペースでAtCoderのコンテストに参加しているので、その参加結果を、なるべく記事にすることを目標としています。
自分の解答状況、反省、自分のできる範囲で問題の解説を記事にする予定です。
開発について
自分が関わった開発を記事にしていこうと思っています。
目的、目標、対象、設計、実装、運用、使用技術に関して詳しく書いていきます。
イベント参加について
インターンなどへの参加について記事にしたいと思っています。 参加した様子、自分の感想を書く予定です。
趣味について
個人的な趣味についても記事にしたいなと考えています。 これに関しては、頻度は少ないと思いますが、書きたい欲が出れば、投稿するというスタイルにしようと思っています。
今後について
当分の間は、週に一回AtCoderの参加記を記事として投稿することを目標にしていきたいと思っています。もし、読んでくれる方がいれば、フィードバックをして頂けると、とてもありがたいです。余裕ができれば、他のことについても記事にしていければと考えています。
