LoginSignup
6
2

More than 3 years have passed since last update.

@Shiroha_MK3((Mitta Kazuki) 白羽)

[初投稿] AtCoder入茶してみたw [至って真面目です]

Last updated at Posted at 2021-03-20

はじめまして。白羽(shiroha_F14)です。
Twitterでもうご存じの方もいらっしゃるかもしれませんが、Qiita初投稿なので、はじめましてにしておきます。

この度晴れてAtCoderで入茶したので、これまでの記録をまとめるという意味でも、またこれすると良いよ！みたいなのを紹介する意味でも、
とんでもないふざけたタイトルで他人の目をひくようにして記事を書こうと思った次第です。

自己紹介

田舎に生まれ田舎に育ってる最中の18歳(専1)です。これ書いてる時はなんとまだ誕生日迎えてないので19歳ではありません。
田舎なのに専門学校に進学したせいでレベルの低さに萎えつつも、時々人生で一番の至福であるプログラミングに逃げながら就活ちゃんと頑張ってます。
実績も大きめの開発経験も特にないですが、そのくせプログラミングは人生などと言い張りプログラミングと婚約しようとして失敗しJava/C++/Python/JavaScript/C#などさまざまな言語と友好を深めています。息を吸うようにプログラムを書き息を吐くようにデバッグしています。

競プロ(AtCoder)は2021年の2月から始めました。他には3月からyukicoderを始めました。それ以前は競プロって何それおいしいの？って感じでした。
使ってる言語はC++です。
そして入茶したのは6回目のAtCoder Beginner Contest 196(以下ABC***と略)です。

先に結論

これをやれシリーズ

  • AtCoder Problems Boot Camp for Beginners
    • Easy 100問
      • 文字列操作系が多いから後半飽きてきたら早解き練習のつもりで
    • Normal 1/3くらい
      • 全部は難しい
  • AtCoder Problems Recommendation
    • Moderateが基本
      • 苦手なタイプの問題こそネット活用
    • 時々Hard
      • Easyは正直簡単すぎるのが選ばれがちなので早解き練習
  • AtCoder Scores
    • 300点でランダム出題が正義
      • AC済み排除とランダム出題が有能すぎる
  • 様々なQiita等のAtCoderに関連する文章を読む

最終的に身に付いた知識

  • Javaに逃げた方が良いときもある
  • C++で使えるデータ型
    • vector : 可変長配列
    • unordered_map : 連想配列
    • priority_queue : 優先度付きキュー
    • pair : 二つの値のペア
  • C++で使えるメソッド
    • sort : ソート
    • swap : 値入れ替え
    • reverse : 要素の前後入れ替え
    • find : 値の発見
    • next_permutation : 順列の全列挙
  • 基本的なアルゴリズム
    • 全探索
    • bit全探索
    • 二分探索
    • エラトステネスの篩
    • etc……

つまるところ

ざっとこのくらい出来れば茶にはなれると思います。
どちらかというとC問題が出来るならD問題とかより速度の方が大事です。
事実過去問の解答状況は緑diffのAC数3ですし、ABCのD問題はAC数7です。
難易度上限は恐らく他人より低いです。

最近のABCは3完を15分や20分で達成すると緑パフォがもらえます。
私個人の意見としてはそれを狙った方が十分パフォーマンス値を出しやすかったです。
入茶したいけどD問題はすぐには出来そうにない、そんなときはとにかく早解きしましょう。
　
　
　
　
　
　
　
　

ここからはただの自伝なので要らない人はブラウザバック推奨

入茶までの流れ

総合

ABC194は滅茶苦茶ボコボコにされて勿体ないことになっていますが、それ以外の回はレート+50台を1回と+100台を3回達成してます。2回目のABC192は+150も出してるのでこれでABC194の爆死を帳消しにしてる感じです。
image.png
いやでもぶっちゃけ……遅いですね、私(白目)
正直ABC194で爆死さえしてなければ5回で入れてましたし、最初の一回目から今日まで一回も本番で4完出来てないので本当に雑魚だと思います。入茶して嬉しいとは思うけど普通に恥ずかしいです。なぜかTwitterフォロバされてる物理好きさんにも見せる顔がありません。
ひとまず成績みてちゃんと振り返りましょうか……

初出場 ABC191

結果

初めてコンテストに出たのは2/6のABC191でした。この時出題されたC問題の解法が全く思いつかず、しかもD問題はまさかのDouble型の精度をはみ出る計算をうまいことやる問題でした。
あえなく爆死したので6分58秒で2完とかいう意味不明な成績を残して死にました。2完は2完でも割と速く出したおかげでパフォーマンス値が755も出ているのが面白いですね。image.png

ここからABC192までの戦略

初戦わずか2完に終わった私は敗北の味を噛みしめながら、2週間必死にAtCoder Problems Boot Camp for BeginnersのEasy100にぶち当たり続けました。
ただ、2戦目まで2週間もあったにもかかわらず、100問AC出来なかったのを覚えています。でも40問はクリアしていると思います。

2戦目 ABC192

結果

あまり進捗は良くなかったもののBoot Campに挑戦し続けました。すると気前のいいことに女神が舞い降りて15分で3完しました。急に緑パフォが出てレーティングが157も伸びました。
SOMPO HDさんには感謝しかありません(は？)。

ただこの時出たD問題「Base n」が二分探索で解けることを知った私は解説を見て苦虫を嚙み潰したような顔をしたのを覚えています。

ここで3完してしまったのを最後に頭の悪い白羽さんは3完では満足できなくなってしまいました。しかも入茶するまでに4完達成することもありませんでした。
image.png

ここからABC194までの戦略

ABC191と192のE,F問題を見て動的計画法が多量に出題されていることを知った私はEducational DP Contestの問題を解くことにしました。
結論から言うと、これらは今の所結果に繋がっていません。(多分いつか役に立つ)

この時期何をすべきだった？

AtCoder ProblemsやAtCoder Scoresでとにかく一定難易度の問題を埋めまくること。これがこの時期の自分に最適な学習法だったと思います。

Boot campは？

Boot CampのEasy100を全部ACしたのはABC194～195の間ですが、正直なところEasyは後半になってくるとstring型の操作問題が大量に出るので飽きてきます。だからといってNormalに挑めば人間じゃない問題に圧し殺されるので、正直Boot Campに固執する必要はなかったと思います。

3回目 ABC193

酷い解き方でしたがなんとか35分3完を勝ち取りました。C++じゃなかったらTLEしてる気がします。
image.png
B, Cどちらとも前回よりは難化していたのですがそれでもちょっと遅いですね。ですがそれより心残りなのはただの全探索であるDで実装をバグらせてしまったことです。今の俺なら絶対4完してるんだよォォオォォオオ！！！！！

気づき

2完で終わったABC191とパフォが10くらいしか変わってません。こんなんあり得んやろって思ってたんですけどよくよく成績見直して気づいたことがあります。
ご存じかもしれませんが、B問題までの速度が割とパフォーマンス値を大きく変えます。
私と同じくらいの地力でさっさと茶に上がりたいと思っているならB問題の早解きをやるのもかなりアリです。テストせずに通してAC安定してきたらそれだけでもパフォ700とか余裕ですし、更にCで悩むための時間も作れますし……

4回目 ABC194

$\huge{大☆爆☆死}$
image.png
C問題がまさに主客転倒という一番苦手なタイプのやつでした。Dも定理知ってないと絶対に解けないので見事にサヨナラホームランを打たれ2完爆死。E問題もしゃくとり法であることに気付けず死に、せっかくEDPCをやっていたのにF問題の桁DPもついぞ解くどころかDPであることがわからず終了しました。

ここからABC195までの戦略

DPやっても意味がないと気づいたのがこの回でした(遅い)。そこでついにBoot Camp Easy100を最後まで埋めました。ただ時間が余りに余っていたのでようやくAtCoder ProblemsやAtCoder Scoresで一定難易度埋めを始めました。判断が遅い。
具体的には

  • Problems
    • Point条件で絞ってDifficultyの昇順にAC済みを除外して埋める
    • Difficulty条件で以下同上
      • かなり詳細なデータが複数集計されているのでモチベ維持しやすい
  • Scores
    • AC済みとABC以外を除外して点数で絞り、適当な数をランダム出題して埋める
      • diff機能はないがランダム出題がとても便利

という感じで結果的には下記の灰埋め合わせて70ACくらいしました。
どっちも滅茶苦茶便利なので片方とか言わず両方使っていきましょう。

その他

本番3日前と1日前に100点灰diff問題20問早解きをやった記憶があります。目的としては指のウォーニングアップだったのですが、若干速度は上がったかもしれません。
ただ、正直200点灰diffの方が良いと反省しています。
加えてこの期間の難易度埋めだけで茶diff前半までクリアできるようになりました。外部サービスがあまりにも有能過ぎるのに今更気づきました。

5回目 ABC195

前回の大爆死で精神的なショックが若干抜けきっていないのか、B問題がずっとわからずCを解いて1時間後にようやく1ペナでBをACするに至りました。
パフォがちょっと低いです。やっぱりクリアまでの時間が相当影響していると思います。
image.png

ここからABC196までの戦略

この時点でパフォ506を出すとレート400超えが確定していたので、とにかく安定して解ける難易度と30分程度で解ける難易度を高めることに集中しました。
やったこととしてはABC194~195と同じくProblems埋めですが、この一週間は地力に見合った茶後半や緑diff序盤の問題、300点問題、そしてRecommendationタブのModerate問題を埋めまくりました。
結果として緑diffがいくつか埋まるようになり、その経緯でSTLコンテナのデータ型やアルゴリズムの話も時間をかけて読むようになりました。
でもABC196でDFS問題を解けずに死ぬんですけどね。

6回目 ABC196

友人を誘い参加したABC196でついにABC192以来の緑パフォを出しました。入茶も達成しました。
この回はABC192ほどの当たり回でもなくCは普通にdiff230くらいあるのでまぐれだとは思いたくないです。
しかし最後まで4完は出来ませんでした。
image.png
21分で3完を達成しました。特に2完までに関しては3分で出してるので相当効いてると思います。
1回も4完出来てないことについて言い訳すると、D問題が初参加のABC191以来ずっと緑diff以上で茶が1回も出てないんですけど、嫌がらせですかね？

今後

当然レーティング緑は狙いますし、水も青も狙います。上を見るとキリがないので気にしないようにはしてるんですけどね……()
でも何より4完出来てないのがくやしいので絶対に4完してから緑になります。待ってろよ
　
　
　
　
　
　
　
　
　
　

裏話

ABC195と196ではC問題をJavaで解きました。C++はString→Long Longの変換が難しすぎるんじゃあ。

6
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
6
2