はじめに
AtCoder Beginner Contest 235に参加して75分5完、955位でした。
あまりにも不甲斐ない内容だったために再発防止のためにコンテストでした思考を時系列順にまとめたいと思います
A - Rotate
21:00:00 開始
問題文中に
3 つの数字 x,y,z をこの順に並べてできる 3 桁の整数を xyz と表すことにします。
という文を確認
- 文字列として受け取って一桁ずつ処理
- 3桁なので力技で行く
の2択から、汚くても速く書ける後者を採用
ll n;
cin>>n;
ll a,b,c;
a=n%10;
n/=10;
b=n%10;
n/=10;
c=n;
21:01:53 提出 AC
汚いコードだが、とにかくAC
B - Climbing Takahashi
実際にシュミレートするだけ
21:03:36 提出 AC
C - The Kth Time Query
問題を流し読みし、制約をろくに読まずvectorで実装し始める
2×10^5なら充分がと思いこむがそれだと実際に必要な配列の個数はaiの最大値の10^9個
21:08:00 Google検索 c++ map
実装し終わったものの、テストケース2でランタイムエラーを起こす
ここでようやくmapを使わなければいけないことに気がつく
C++日本語リファレンスを見ながら実装するも、
mapにその要素があるかどうかをempty()でやろうとしてバグらせる
.count(x) == 0 に修正してAC
21:22:07 提出 AC
もうここで14分無駄遣いしている。この14分がなければ青パフォであった
D - Multiply and Rotate
出てくる数字がせいぜい10^6の10倍程度なのでとにかく出てくる数字を全部出してsetで管理すれば良いなと判断
21:40:00 Google検索 set同士の足し算 c++
insertでsetを足そうとして手間取る
setの結合はmerge かあ。足し算 という単語も適切ではないっぽいので、しっかりと使うものは頭に入れておくこと
21:42:20 提出 TLE
現在のループで新しく発見した数字が空ならループを抜ける処理を書いていたが、
いくつかのケースでTLEが発生。無限ループが出たと思われる
21:45:11 提出 AC
この問題ではすぐに答えが出るだろうと判断。1000回の試行で解がでなければ不可能と判断して打ち切る処理を足してAC
5分以上の思考をするならペナルティ覚悟ですぐ出す、という競技プログラミングの解き方をした
E - MST + 1
Eの問題に面食らったが、最小全域木の求め方のアルゴリズムがしっかり頭に入っていたため、
それをやっていけば良いと判断
21:52:00 Google検索 c++ 配列 上限 個数
しかし、クエリをO(1)で処理するためにはクラスカル法の全状態を保存しなければ行けないのでは？と迷走
200000*200000で40000000000個の配列を作ろうとして流石に無理だと考察を続ける
22:00:00 Luzhiled's Library内 でunionfindを捜索
クエリの先読みだと気付き実装を開始
AtCoder Libraryを使えば良さそうなものだが、未だにpaiza.ioで実装しているため人のライブラリを使わせてもらっている
22:10:34 提出 AC
グラフの持ち方が
vector<pair<ll,pair<ll,pair<ll,ll>>>> g(m+q);
cin>>a>>b>>c;
g.at(i)={c,{-1,{a,b}}};
という実装でいいのか疑問だったが、他の人の提出を見てみると
pair< pair < int,int>, pair< int,int> > とかタプルで作成しているのでまあいいのだろう。
F - Variety of Digits
桁DPだということは制約を見てすぐ分かったが、
ちゃんと桁DPを実装したことがなかったためえっちらおっちら実装しているうちに時間切れ。精進しなさい
今後の課題
- set,mapの使い方を再確認 コンテスト中に見るチートシートを作成しておく
- D問題で無限ループする原因の特定と対処法の確認
- 桁DPの過去問を解く