みずまずぷろぐらみんぐ日記

日々学んだことや頭に浮かんだことを、そこはかとなく書き連ねます

競プロ的おはなし

競プロ

こんにちはー、みずまずです。
2度目のABCコンテストで大成長を遂げた興奮から、日曜の夜はなかなか眠れませんでした(ぅω・`)

でも今回は運が良かっただけで、次また解けなくなっていたらすごくショックなので、パフォーマンスを落とさないように精進しなきゃ……と、翌日にはもうびくびくしていました。
(ネガティブ……この上なくネガティブ！！)

みずまず、目標決めたってよ

レートはとにかく上げたいです(プロフィールページのグラフビュンって右上がりにしたい)。
色もなるべく強い色になりたいです。
成長のスピードははやい方が理想です。
コンテスト後に強い人達やFFのみんながTwitterで議論してる内容を理解できるようになりたいし、私もその輪に入りたいです。

ただどうも具体的な精進の方法がぼんやりしていたので、"とにかく早く茶色になる"ということを短期的な目標として、それを達成するために何ができるようにならなくてはいけないのか、何をすべきか、を調べました。



"調べました"とは言いましたが
ABSの元となったdr.kenさんのQiitaの記事

qiita.com

とそのリンク記事

qiita.com

に必要なことはすべて書いてありました。ありがたや…。

tipsの方の記事によると茶色になるには

A～C の 3 問を早く解けるようにする (3 問合計で 30 分が目安です)


らしいです。

3問合計で…30分…………。

今の私は100分の制限時間内に確実にABC3問ACできるかも怪しい状況。
実は2回目の参加時に何分で問題をACできたか計っていたのですが、A,Bの2問解くのに30分、Cまで解き終わった頃にはコンテスト開始から75分が経っていました()


"""Cがどうこう以前にABの時点で遅い"""


ということで

・基本的にABCのB,Cレベルの問題だけ漁る。
・A,B(特にB問題)にかける時間短縮のために、B問題の過去問はスピードを意識して取り組む。
(たいていのA問題は問題見てからACするまでシンキングタイム0なので、とりあえずスルーします。タイピングが遅いとか、コードが冗長だとか、実行時間がーとか改善できるところはたくさんありますが、今はまだ細かいところを詰めるフェーズではないかなと。)
・C問題の過去問はなるべくいろんなパターンの問題に触れられるように選んで取り組み、コンテストで安定してACできるようにする。
(クセのある問題よりかは、典型的？なものを丁寧に解いていきたい。自力で解いたらいくつか他の人のコードも見てみて、より良いアプローチがあったか確認できたらいいな。)

しばらくはこんな感じで精進していこうと思います。
(C問題を短時間で解く的な訓練がないけど、それは次の段階かなって感じです…。)


方針、固まっちゃったね……///


周りの人達が強すぎて茶色ってすぐなれるものだと思ってたけど、意外と遠いんだなぁ、と思いました。競プロの世界は甘くなかった……。

ABC071 B Not Found

そんな感じで方針も決まったので、今週は先程リンクを貼った記事(1つ目の方)に載っている【類題】の問題を上からつぶしていました。
その中でひぃーーってなった問題について話します。

まず1つ目 ABC071 B Not Found。
集計処理というタイプの問題だそうですね。

APG4b育ちの私はset大好き？で、ABC085のB Kagami MochiやABC170のC Forbidden Listでもぱっと思いついたのはsetを使う解法だったのですが、せっかく配列を使ったバケット法なるものを学んだからには1度はやっておこう、ということで挑戦した問題です。
(B 問題辺りだとこのやり方でメモリが足りなくなることはほぼないらしいですね。良いことを知りました。)

#include <bits/stdc++.h>
using namespace std;

int main() {
  string s, answer = "None";
  cin >> s;
  vector<char> c(26, 0);
  for (int i = 0; i < s.size(); i++) c[(int)s.at(i) - (int)'a']++;//s[i]がaなら0,zなら25を増やす
  for (int i = 0; i < 26; i++) {
    if (c[i] == 0) {
      answer = (char)((int)'a' + i);
      break;
    }
  }
  cout << answer;
}

 
が、これsetの方が圧倒的に楽だったのでは…？()

整数とアルファベット対応させるのに少し苦労しました。
結果的にchar型とint型の変換にも慣れることができたので、そこは勉強になりましたが。
結構頑張りました…というおはなしです。

ABC074 C Sugar Water

全探索というタイプの問題らしいです。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int a, b, c, d, e, f;
  cin >> a >> b >> c >> d >> e >>f;
  vector<int> mizu;
  vector<int> sato(1,0);
  for (int i = 0; i <= f / 100 / a; i++) {
    for (int j = 0; j <= f / 100 / b; j++) {
      int ariemizu = (i * a + j * b) * 100;
      if (ariemizu != 0 && ariemizu <= f) mizu.push_back(ariemizu);
    }
  }
  for (int i = 0; i <= (f - 100 * a) / c; i++) {
    for (int j = 0; j <= (f - 100 * a) / d; j++) {
      int ariesato = i * c + j * d;
      if (100 * a + ariesato <= f) sato.push_back(ariesato);
    }
  }
  pair<int, int> answer(100 * a, 0);//first砂糖水,second溶けてる砂糖
  double maxnodo = 0.000000;
  double gendo = 100 * (double)e / (100 + (double)e);
  for (int i = 0; i < mizu.size(); i++) {
    for (int j = 0; j < sato.size(); j++) {
      int satomizu = mizu[i] + sato[j];
      double nodo = 100 * (double)sato[j] / (double)satomizu;
      if (satomizu <= f && maxnodo < nodo && nodo <= gendo) {
        maxnodo = nodo;
        answer = make_pair(satomizu, sato[j]);
      }
    }
  }
  cout << answer.first << ' ' << answer.second;
}

これははまりました。

まずどうやって解いたものか方針もなかなか決まらず、いざ書いてみたもののWA！WA！WA！
テストケース1個だけ通らなくてつらかったんですが、求める砂糖水の質量、砂糖の質量共に初期値を深く考えず0にしていて、解が初期値のまま1度も更新されないと無の砂糖水()が出来上がっていたんですね。問題文にわざわざ"砂糖が全く溶けていない水も濃度0 [%] の砂糖水と考えることにします"って書いてくれてあるし、制約でも"100A≦F"だって言ってるのに…。

あと、この問題と言いABC169のC Multiplication 3と言い、ほんとdouble型が信じられない…。
私の中でdouble型のイメージが"わりと頻繁に誤差出る上に、中で何が起こってるかわからないもの"になりつつあります。

正直こっちの問題はちゃんとわからずACしてる感ありますし。(よくないね。)

近々一度double型の安全な使い方を勉強しないとなーって思ってます。

あとがき

この他にTwitterで誰かが流してくれて気になった問題なんかにも興味が薄れないうちにと挑戦していたので、今週は1日平均9問くらいACしていました。
問題解くの、一度始めるとやめられなくなりますよね。

「もうこんな時間……寝なきゃ、明日起きれない………うーんでもあともう1問だけ←」

みたいな。
N予備とか他にもやることいっぱいあるのにね。こわいこわい。

明日のABC171、楽しみですが、先週のアレがまぐれだったと発覚してしまうんじゃないかとドキドキです。
頑張るぞい。