こんにちは！せるたわーθです！ついに、、、！2022/09/10に行われたAtCoder Beginner Contest 268にて緑色になれましたので(今のうち)に記事を残したいと思います…！！お読みいただければ嬉しいです！！
0.自己紹介
私は地方の高校2年生です。受験が迫ってきています。こわいですね…！AtCoderのユーザー名はymmtrです。メインの言語はC++です！
1.緑色のレベル感
こちらについては、すでに多くの方がchokudaiさんのブログなどから引用されているので、私はそちらのブログへのリンクを貼るのみにとどめます＞＜
AtCoder（競技プログラミング）の色・ランクと実力評価、問題例 - chokudaiのブログ
2.ここまでの道のり！！
総AC数は約840問で、私の場合は1問解くことがレーティングを1あげるのに寄与した格好になっています。ABC-C問題は166問,ABC-D問題は89問ぐらい解きました。
また、私は33回目のコンテストで入緑しました！本格開始から大体9か月かかっています…！
3.学習事項
茶色になってから新しく仕入れた知識は
- Union Find
ぐらいです…！コンテスト中に使ったことはありません…笑
茶色になるまでに習得した典型アルゴリズムのうち、実際にコンテストで使えたものは
- DFS
- DP(動的計画法)
- 累積和
- 二分探索
- bit全探索
- RLE(ランレングス圧縮)
などがあります。
茶色になるまでに習得したけれども、今のところコンテストで使ったことがない典型アルゴリズムは
- BFS
ですね…！
典型アルゴリズムを知っていることも大事ですが、問題文に即した状況を想像する力のほうが大事なような気がします…。
練習としては、ABCのCやDを解けるだけ解いていきました。また、けんちょんさんの鹿本の中にある問題も少しずつ解き進めていました。また、同じくけんちょんさんなどが作っていらっしゃる「アルゴ式」というサイトでBFSやDFS,Union FIndを学びました！！
4.ABC268受験のようす！
時刻はかなり適当に書いております…！
- コンテストの準備として、おふろと歯磨きを済ませる(-20分)
- コンテスト開始(0分)
- A:setにつっこんでfor文を回そう！(0.1分)
- B:substr使うか...(1分)
- C:$O(N^2)$解法しかわからない…どう計算量を落とすんだ？？？(3分)
- あぁ～、これは幾何の回と同様にレート下がっちゃうかもなー(5分)
- とりあえずD問題も見ておくか(20分)
- D:順列全探索と、、あとはなんだろう…。実装重そうだな、Cに戻ろう(23分)
- C:ﾅﾆﾓﾜｶﾗﾅｲ(25分)
- 賭けになっちゃうけど、D書いてみるか(30分)
- D:アンダースコアの配置は、DFSで全探索できそうじゃない…？(35分)
- D:頑張って実装、からの提出(66分)
- D:D問題一発ACキター！(66分)
- 残りの時間は椅子を温めておりました…！
5.好きな問題！
これより先は、問題の解法のネタバレをまあまあ含みます。次に紹介する2題を解かれてから読むことをお勧めします。
私がこれまでに解いてきた問題の中で、お気に入りの2題を紹介したいと思います！！
取り扱う問題は
-
茶diff部門 ABC171より 「E - Red Scarf」
-
水diff部門 ABC138より 「E - Strings of Impurity」
です！
それでは、ネタバレエリアに入ります…！！
「E - Red Scarf」
この問題はxorについての知識を問う問題です。猫のすぬけくんが偶数匹いる、という思わせぶりな制約がいい味出してますね…！
もちろん、解く際にはこの性質を大いに活用します。
xorの性質として、a xor a = 0 を知っていたらだいぶ解きやすいと思います。
話は少々脱線しますが、私は夏休みに大阪に旅行に行きまして、この問題はその時に解いた問題のひとつです。旅行気分も相まって、強く印象に残っている問題です。ABC263が旅行期間中に行われましたので、ホテルにパソコンを持って行って無理やり出ました(((
また、中之島の大阪市立科学館にも行きました…！そこにはですね、日本を代表するスーパーコンピューターであった「京」のラックが展示してあって(！)、ものすごく感動しました！特に、放熱を効率よく行うために基盤が斜めに配置されている、ということなど新しい学びがありました！科学館にはそのほかにも面白い展示があったのでめちゃくちゃおすすめです！！！
「E - Strings of Impurity」
この問題、めちゃめちゃ楽しかったです！！問題文が明快で、何を求値してほしいのかを把握することはとてもたやすいですが、私はそこから先になかなか進めませんでした…。2~3時間ぐらい考えました、というか方針が学校にいるときに立ちました…！（笑）
わかった時の爽快感はものすごくて、「これこそ私が競技プログラミングに求めていたものだよ！！！」という感覚でした。何が言いたいかというと、自分にとって難しい問題を解けたときは、いかなる場合でもとても気持ちが良いものだということです。
レーティングをゴリゴリに意識した記事を書いている私が言うのもアレですが、自分の成長を実感する場は、必ずしもコンテストだけではないと考えています。
ちなみに私は、貪欲に進んでいきたいが、単純にやると間に合わないので各文字が出現する場所を記録しておき、毎回二分探索をする、という方針で実装しました。
6.さいごに
茶色になってからここまで結構長かったように感じます…！茶色になったときと比べて、知識が増えたという実感はないですが、問題演習を重ねたことでAtCoderの問題形式に慣れることができたのだと思います。いつかは水色になりたいな…！
2022/09/15 せるたわーθ