#2 - 文系出身エンジニアが競プロをやる

ABC085B - Kagami Mochi

下から順に大きい鏡餅だけ積み上げられるから、最大で何枚積めるかを問う問題です。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
   int n;
   int stairs = 0;
   scanf("%d", &n);
   vector<int> m(n);
   for (int i = 0; i < n; i++) {
       cin >> m[i];
   }
   sort(m.begin(), m.end());
   for (int j = 0; j < m.size(); j++) {
       if (m[j] > m[j - 1]) {
           stairs++;
       }
   }
   cout << stairs;
   return 0;
}

algorithmめちゃくちゃ便利ですね。sortをかけて大きい順にしてからサイズが小さいものだけを積んでいくようにします。無事正解。

ABC085C - Otoshidama

わざわざお年玉の金額を嘘ついて友達に吹聴するクソガキのお年玉の金額と札束の枚数があっているかを問う問題です。これ多分探索量が多いので、全探索とかすると時間かかりそう。

#include <iostream>
using namespace std;
int Amount(int x, int y, int z) {
   return (10000 * x) + (5000 * y) + (1000 * z);
}
int main() {
   int n, yen;
   cin >> n >> yen;
   int x10 = -1, x5 = -1, x1 = -1;
   for (int i = 0; i <= n; i++) {
       for (int j = 0; j <= n - i; j++) {
           if (yen == Amount(i, j, (n - i - j))) {
               x10 = i, x5 = j, x1 = (n - i - j);
           }
       }
   }
   cout << x10 << " " << x5 << " " << x1 << endl;
   return 0;
}

結構時間かかりましたが、無事正解。x10とx5の枚数が分かれば、x1の枚数は自ずとわかるので固定してあげればよいですね。

ABC049C - 白昼夢 / Daydream

英小文字からなる文字列 Sが与えられます。
Tが空文字列である状態から始め、以下の操作を好きな回数繰り返すことでS=Tとすることができるか判定してください。

・Tの末尾に 'dream' 'dreamer' 'erase' 'eraser' のいずれかを追加する。

これ多分愚直にやればすぐ正解できたと思うんですが、良いコードを書こうとしてめっちゃ時間かかっちゃいました。そして最終的なコードもクソコードでした。変数名も最悪ですね、反省。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool ssEql(string &s, string &t) {
   if (s.substr(0, t.length()) != t) {
       return false;
   } else {
       return true;
   }
}
void rev(string &s) {
   reverse(s.begin(), s.end());
}
int main() {
   string d5 = "dream", d7 = "dreamer", e5 = "erase", e6 = "eraser";
   rev(d5);
   rev(d7);
   rev(e5);
   rev(e6);
   string s;
   bool answer = true;
   cin >> s;
   rev(s);
   vector<string> reverses = {d5, d7, e5, e6};
   string ts = s;
   while (ts.length() != 0) {
       if (!ssEql(ts, d5) && !ssEql(ts, d7) && !ssEql(ts, e5) && !ssEql(ts, e6)) {
           answer = false;
           break;
       }
       for (string &r: reverses) {
           if (ts == r) {
               ts.erase(0, r.length());
           }
       }
       for (string &r: reverses) {
           if (ssEql(ts, r)) {
               ts.erase(0, r.length());
               if (ts.length() == 0) {
                   break;
               }
           }
       }
   }
   if (answer) {
       cout << "YES" << endl;
   } else {
       cout << "NO" << endl;
   }
   return 0;
}

文字列を反転して一致したらターゲット文字列から一致部分を削除しています。反転しないと、erが被ってめちゃくちゃ面倒臭い感じでした。正攻法でやってみたほうが良いかなあ…。

あと一問（ABC086C - Traveling）残っているんですが、手強そうなので今週か来週解こうと思います。

あとがき

物欲がフツフツと湧いてきて気がついたらギターを買っていたんですが、やっぱメロディを弾けるのは楽しいですね。今までベースばっかりだったので時間がめっちゃ溶けます！音楽は最高の遊びです！

なのでプログラミングする時間が露骨に減ってます。うーん、何か削らなきゃ…。