2019-10-28

ABC144

ABC 参戦記録

結果

問題	ACまでに要した時間	AC	WA
A	2:40	1	0
B	7:41	1	1
C	-	0	0
D	-	0	0

Rating	順位
516 (-39)	4478

久々のAtCoderコンペだったがおそらくこれまでで一番ひどい出来だった．
ABC143がエラく簡単だったので最近のABCはユルくなったのかと思ったがそんなことは全く無かった．
C問題，D問題をコンスタントに解けるようになりたい．どうすればいいのか．．

所感

B問題

つまらないWAでめちゃくちゃRatingを失った．情けない．
何をミスったかというと Yes No を YES NO とtypoしてまさかの全WAをキメた．
前にもLeetCodeで同じミスをしたことがある気がする．本当にもったいないので気をつけたい．

C問題

回答中に考えていたこと
- 最短経路となるi, jの組わせをどうやって決定するか？
- 移動距離は目標の座標がa,bならば a + b - 2 になるが，これが最小になる座標をどうやって決定するか？
- しかも探索範囲が広いのでどうやって計算量をへらすか？何も考えずに総当りすると，時間計算量は $\mathcal{O} \left( \displaystyle \frac {N ^ 2} {2} \right)$ となり，Nの最大値は 10¹² なので確実にTLEする
どうすべきだったか
- 25,30とかのわかりやすい値について検討すれば $\sqrt{N}$ までの範囲で探索すれば十分であるということはすぐわかったはず
- Nの最大値にビビらずに総当りで解く方針を崩さずに考えればよかったのだが，いきなり「計算量の少ない方法があるのでは？」と疑って手が止まってしまったのは良くなかった
- 提出数と正答率を見ても結構高めなのでそれほど難しい問題ではないはず．これは解けないといけなかった．

D問題

回答中に考えていたこと
- 水筒を二次元の図として捉えて，水筒を傾けたときに動く水面の位置の点(x,y)までの角度はstd::atan2(y, x)で求められるが，これと傾ける角度との相関性がわからない
- ってかホントに二次元の図として捉えていいのか？多分傾ける角度と水面の位置は連動して動くから，水の三角柱の底辺の面積とかを考慮する必要はないはずだけど本当にそれでいいのか？（これは気にしなくていい話だった）
どうすべきだったか
- atan2で角度を求めるところまでは正しいので，根気よく傾ける角度と動く水面までの角度との相関性を調べれば解けた可能性がある
- 場合分けが必要だったので完答までいかなかったかも知れないが，それでもいくつかのテストケースは通せるぐらいの実装ができないと厳しい

2019-10-27

ABC143

過去問練習 ABC

atcoder.jp

所要時間

30分4問完答
通常のABCと比べると異常なほど簡単だった

解答メモ

A - Curtain

問題文通りに実装すればよし．

#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int A, B;
  cin >> A >> B;

  cout << max(A - 2 * B, 0) << endl;

  return 0;
}

B - TAKOYAKI FESTIVAL 2019

ワークロードが小さいので何も考えずに時間計算量O(N^2)のbrute forceで解を求めれば良い．

#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N;
  int d[100];

  cin >> N;
  REP(i, N) { cin >> d[i]; }

  int result = 0;
  for (int i = 0; i < N; ++i) {
    for (int j = i + 1; j < N; ++j) {
      result += (d[i] * d[j]);
    }
  }

  cout << result << endl;

  return 0;
}

C - Slimes

S[i] ≠ S[i+1] となる箇所のカウント+1が解答．

#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N;
  string S;

  cin >> N >> S;

  if (N == 1) {
    cout << 1 << endl;
    return 0;
  }

  int result = 1;
  char prev = '\0';

  REP(i, N) {
    if (prev == '\0') {
      prev = S[i];
    }

    if (S[i] != prev) {
      ++result;
      prev = S[i];
    }
  }

  cout << result << endl;

  return 0;
}

このブログは何か

このブログは何かマイルストーン

はじめに

AtCoderに最初にアカウントを作ったのは2017/01ぐらいらしいのだが，それ以来コンペに参加したりしなかったりを繰り返して中途半端な状態になっていた．2019/10/27日現在のレートは555で茶コーダーである．

f:id:serihiro:20191027120857p:plain — 2019/10/27現在における筆者の惨状

しかし，2019年以降に受けた面接の場でのコーディング面接における絶望的なパフォーマンスを鑑み，「自分はアルゴリズム実装という能力において同業他者と比べて圧倒的に劣っており，それが自分のキャリア選択の自由度を妨げている」ということに気づいた．

よって，競技プログラミングに真面目に取り組んで赤コーダーを目指すことを決意した．

赤コーダーという目標について

茶色底辺が赤コーダー目指すとか目標が高すぎやしないかと思うが，現在ラグビーのイングランド代表のhead coachを務めているエディ・ジョーンズも，自身の著書の中で以下のように述べている．

目標は漠然としたものや、抽象的なものではいけません。数字などで具体的に表現され、結果が出たとき達成できたかどうか、はっきりわかるものでなければなりません。

エディー・ジョーンズ. ハードワーク　勝つためのマインド・セッティング (Japanese Edition) (Kindle の位置No.92-93). Kindle 版.

目標は、「そんなことができる訳がない」と思えるほど、大きなものを掲げるべきです。

エディー・ジョーンズ. ハードワーク　勝つためのマインド・セッティング (Japanese Edition) (Kindle の位置No.112-113). Kindle 版.

赤コーダーになる というのは，具体的にはレート2,800を超えることである（2019年10月27日時点のレギュレーションにおいて）．そして，それが自分にとってどれぐらい高い目標かと言えば，レート500前後を2年以上うろうろしている自分の現状を鑑みれば相当高い目標である．

以下のchokudaiさんのブログによると，各ランク別の印象は以下のようであるという．

chokudai.hatenablog.com

茶色: 正直あまり高いレベルではありません
緑色: 競技プログラミングに熱心に取り組んでいる人
水色: かなり優秀
青色: 超優秀
黄色: 九割以上のIT企業において、このレベルのアルゴリズム構築能力は必要ありません
橙色: ここまで来ると、検索サービスとかの滅茶苦茶アルゴリズムが大切な会社さんとか、研究開発とか、そういうところじゃないとこのアルゴリズム力は生かせない気がします。
赤色: 化け物しかいない

自分に化け物になる覚悟はできているだろうか？

また，赤コーダーになると，AtCoder Jobsにおいて最低年収1,000万円以上の求人へも応募資格を得られる．これは大変夢がある．また，機械学習の世界においてはアルゴリズムの実装能力は高く評価されているように考えられ，この傾向は機械学習界隈が成長しても大きくは変わらないと考えられる．よって，アルゴリズム実装能力を高く維持することは，自身の業務だけでなく今後のキャリア形成においても恒常的に重要であると考えられる．

以上のことから，目標としての条件は十分であると考えられる．

2019/12/31までに達成すべき短期目標

コンペで時間内に4完を達成する
緑コーダーになる

今後何を書くか

コンペ参加記録
過去問練習記録
アルゴリズム解説

seri::diary::competitive_programming

AtCoderで茶から赤を目指す競プロ精進日記