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

Intro

こんちは。
2019/05/19 21:00 - 22:40に「AtCoder Beginner Contest 126」が開催されました。
参加したので、レポートを書いていこうと思います。

AtCoder Beginner Contest 126

今回から設問が6問に増えました。前回参加したABC125と比べると2問増えています。

Rated対象が拡大したのと、知名度が上がっていることもあり参加者数が増えていそうです。運営の方はお疲れ様でした。今後もよろしくお願いします。

2回目のコンテストですが、A,B,C問題の3つをACしてタイムアウトとなりました。DEFについては見ることすらできなかったのでもっと強くなりたいです。

クソコードでB問題もACしたので、A,B,Cの3問が解けたのが今回のABCが初だ（DEFは見ることすらできなかった）

— Ryota Ikezawa (@_pavlog) May 19, 2019

A - Changing a Character

一番最初のA問題です。提出はこちらのリンク。

問題概要

・1≦N≦50
・1≦K≦N
・入力は'A', 'B', 'C'の3文字のみから成る

N字の文字列Sが与えられるのでK文字目を小文字に書き換えて出力しなさい

解答（コード）

入力に用いられる文字数が3文字のABCのみだったので簡単でした。

#include <cstdlib>
#include <string>

using namespace std;

typedef long long int ll;
#define REP(i, I, N) for (int i = I; i < N; ++i)
#define rep(i, N) REP(i, 0, N)

int main() {
   int N, K;
   string S, ans;
   cin >> N >> K;
   cin >> S;

   rep(i, N) {
       if (i + 1 == K) {
           printf("%c", tolower(S[i]));
       } else {
           printf("%c", S[i]);
       }
   }

   printf("\n");
   return 0;
}

指定されたK文字目の時だけ tolowerして出力します。
12分かかってACしました（最初の5分ぐらいページがひらけなかった）。

公式の解説では、以下のように書いてあります。

小文字の文字コードが 32 異なるということを利用して char 型の該当する文字に 32 を加えても良いです。

初めて知ったので覚えておこう…。

B - YYMM or MMYY

提出のリンクはこちら。

A問題が終わってすぐ取り組みましたが、1回目の提出がWAになってしまって、頭が真っ白になってそのあとC問題に取り組みました。
最後20分ぐらいで、1回目の汚いコードを引き継いで調整したら終了2分前で提出ができて無事ACとなりました。

その間合計4回提出して、3回WAしているのでもっと勉強が必要ですね。

問題概要

4文字の文字列Sが与えられる。その文字列Sのフォーマットを検証して、以下のいずれかの出力を行え。YYは西暦の末尾を表現した表示でMMは月を表現したフォーマットである。

・YYMM
・MMYY
・AMBIGUOUS - 両方とも満たす
・NA - 両方とも満たさない

解答（コード）

#include <iostream>

using namespace std;

typedef long long int ll;
#define REP(i, I, N) for (int i = I; i < N; ++i)
#define rep(i, N) REP(i, 0, N)

bool isMonth(int v) {
   return (0 < v && v < 13);
}

int main() {
   string S;
   cin >> S;

   string head, end;
   head = S.substr(0, 2);
   end = S.substr(2, 2);
   int ihead = stoi(head);
   int iend = stoi(end);

   if (head == "00") {
       if (iend > 12 || iend <= 0) {
           cout << "NA" << endl;
           return 0;
       }
   }
   if (end == "00") {
       if (ihead > 12 || ihead <= 0) {
           cout << "NA" << endl;
           return 0;
       }
   }

   if (isMonth(ihead) && isMonth(iend)) {
       cout << "AMBIGUOUS" << endl;
       return 0;
   } else if (isMonth(ihead) && !isMonth(iend)) {
       cout << "MMYY" << endl;
       return 0;
   } else if (!isMonth(ihead) && isMonth(iend)) {
       cout << "YYMM" << endl;
       return 0;
   }

   cout << "NA" << endl;
   return 0;
}

めちゃくちゃ汚いコードや…誰やこれを書いたのは…。
普通にisMonthとかいう関数も 1<= v <= 12とすべきだと思いますし、判定を行なっている部分もstringを直接チェックする必要はなかったです。
もう少し綺麗に早くコードが書けると良いな…、精進します。

C - Dice and Coin

提出はこちらのリンク。

問題概要

すぬけ君は1 ~ Nの整数が出る魔法のN面サイコロと表と裏が等確率で出るコインの2つを持っています。サイコロを振った得点が基礎ポイントとなり、コインの表が出れば2倍、裏だと0ポイントになります。コインは、0<K-1の間振り続けることが可能です。すぬけ君がKポイント以上になった時、すぬけ君の勝ちです。すぬけ君の勝率を求めなさい。

解答（コード）

#include <iostream>
#include <cmath>

using namespace std;

typedef long long int ll;
#define REP(i, I, N) for (int i = I; i < N; ++i)
#define rep(i, N) REP(i, 0, N)


int main() {
   int N, K;
   cin >> N >> K;
   double point, ans = 0.0;

   rep(i, N) {
       point = round(i + 1 * 1.0);
       int count = 0;
       while (1 <= point && point < K) {
           point *= 2.0;
           count++;
       }

       ans += (1.0 / N) * pow((1.0 / 2.0),  count);
   }


   printf("%.12f\n", ans);
   return 0;
}

すごい長いこと考えてコンテスト終了の6分前に提出しました。べき乗の求め方とかどうだっけって感じだったので全然基本的な構文知ってなくてつらい感じです…。

初期ポイントはrepの先頭で与えられて、ポイントがKを超えるまで繰り返されます。pointがKを超えた時、1/N * 1/2^繰り返した数を答えに足していきます。

最終的に出力して、無事ACでした。
問題解説に書いてあったものを愚直に実装しました。解けて良かった…。

Outro

今回のコンテストでは、初めてC問題をACすることができました。
次はD問題を解けるように成るとともに、安定してC問題がACできるようになるところを目指したいと思います。

最近本業も忙しくなってきて、やらなきゃいけないことが増えているのでコンスタントに続けることを目標に過去問とアルゴリズムの勉強を並列してやりたいと思います。次のABC、ARCもかんばるぞ…目指せとりあえず緑。

【ABC126】採点システムの遅延が発生したため、今回のコンテストをUnratedとさせていただきます。申し訳ありません。
判断基準について、後続のツイートで説明します。

— AtCoder (@atcoder) May 19, 2019

今回のABCはunratedだったので、C問題までパスしたのに非常に残念ですが次回も参加するので対策、応援してます！！！