Shirotsume の日記

嘘Greedyを生やすな

AtCoder 黄色になりました

こんにちは,Shirotsume です.黄色になれました.

いつものやつ↓

こうみると1問でレート1増えるというのは正しそうですね

誰?

現在は神戸大学M1です.中学高校は公立で,高校では吹奏楽で部活漬けの生活を送っていました.(塾も,中学生のころに夏季,冬期講習にいったことがあるだけです)

高校生の頃に友人から Shadowverse というゲームを教えられ,人生が狂いました(いいえ).大学入学後は(学業や部活と並行して) Shadowverse をかなりやっていたのですが,圧倒的に自分にはシャドバのセンスがないことが判明し,競技的にやるのは限界かなーと思っていました.というわけで移住先のゲームとして競技プログラミングに出会い,初めてみたところそこそこ勝ててなにより楽しいので続けているというところです.*1

学習したこと

いろいろやりました.Library Checker をしたり,EDPC埋めをしました.典型90も埋めたかったのですが,どうしても分からない問題を放置しているのであと数問残っています.

これまではかなり知識を中心をしたインプットを行ってきました.解説もガンガン開くようにしています.分からなくて負け,というのはできるだけ避けるようにしたいと思っているので,知識の漏れはなくすように心がけています.あと,「アルゴリズムに問題を合わせに行く」という思考が大事そうなことに最近気が付きました.燃やす埋めるとかが分かりやすいのですが,こういう形式に持っていくと解けるという一般形を知っておいて,問題を一般形に変換できないか?という方向から考察するとうまくいきやすいという感じです.

考察の弱さ(というか,忍耐の弱さかもしれないです)が課題点だと思っているので,これからはそれを伸ばす方向に頑張っていきたいと思います.

作問,テスター

水色くらいから,yukicoder で作問をしたり,テスターをしたりしています.最近は Library Checker の作問作業もしています.半分は界隈へ貢献したいという思いから,もう半分は単に自己顕示欲のためにやっています.

競技プログラミングの練習という面から,作問はかなりよい練習になると思います.ABC-Exに自分の作問したのとほぼ同じ問題が出て,サクッと撃破することができました.

atcoder.jp

yukicoder.me

問題から先に考えた問題は,自分の知らない解法が出てくる可能性が高いので,特に良いと思います.

心構え,考え方

私の強みの一つは,ゲームの普遍的な捉え方だと思っています.シャドバをがんばっていたころにさまざまな記事を読んでいたのですが,そこで勉強した思考の部分を競プロに応用しているということが多いです.

私が読んで有用だった記事を列挙しておきます.

krone-sv.hatenablog.com

krone-sv.hatenablog.com

app.famitsu.com

nxjpn.com

wikiwiki.jp

強い人はたいがいメンタルも強いので,鍛えておくことはおすすめします.特に,コンテスト中にティルトしない*2というだけでもかなり強くなれると思います.

順位表やレート予測なども一長一短です.これが原因でモチベ上がるという人もいれば,むやみに焦ってしまうような人もいるでしょう.これらをできるだけ見ないようにしてコンテストに出てみると,新たな発見があるかもしれません.私はいろいろ考えた結果つけておくことにしています.

あと,「こだわりを捨てる」ということはかなり重要だと思っています.これは自戒でもあるのですが.言語,書き方,アルゴリズムについて,「なぜこれを使っているのか?」を常に考えるようにすると良いと思います.あんまり意味ないなーと思った自分ルールは積極的に捨てることをお勧めします.例えば,○○パフォ取らないとヤバいみたいな思考や,Cまで○○分で解けないとヤバいなど.それ本当にヤバいですか?最終パフォーマンスはchokudaiのボタン押しによって決定され,それ以外は全てまやかしです.

オンサイト

ゆるふわオンサイトとトヨタコン(イベントのみ)に参加しました.これはかなりモチベーションアップにつながりました.twitterでみる人たちが実在するんだなと思うと,一緒に頑張っていこうと思えました.会った人たちに作問面白かったよなどと言われたのも,かなりうれしくてにこにこしてしまいました.

このような機会があるのも,競技プログラミングを大事にしてくれる人や企業がたくさんあるからだと思っているので,感謝を忘れずにこれからも頑張りたいと思っています.

これからやること

AtCoder 黄色に到達すると,ABCがUnratedになります.これにより,Rated帯で解く問題数が4分の1くらいになるので,競プロがかなり別ゲーになるのではないかと考えられます.私はARCがやや苦手なのですが,なぜ苦手なのかに対して自分なりにひとつ仮説があって,これからはそれを検証するために時間を使ってみようかなと考えています.*3

具体的にやることとしては,ARC-D埋め,AGC-Cまで埋め,典型90埋めをやっていきたいと考えています.ばちゃやyukicoderにも,出れるタイミングなら積極的に出ていきます.

まだまだ上っていけると信じているので,やれることはやっていきたいと思っています.

質問コーナー

一部マージしたり本編に統合したりした質問があります.

好きな問題を教えて

問題のシンプルさと解法のエレガントさを考えると,Small Multiple が一番好きですね.

atcoder.jp

印象に残っている問題

断然 Happy Birthday! 2 ですね.茶色のころに見たのですが解法見てめちゃくちゃびっくりした記憶があります.

atcoder.jp

競プロに役立つ趣味

前述のとおり,シャドウバースは役に立ちます.音楽は,基礎ポイントの上昇くらいは役に立ってるのではないでしょうか.何より趣味は楽しむのが一番なので,あんまり役立つとか考えなくてもいいんじゃないかとは思います.

勉強したアルゴリズム

Library Checker を埋めつつ,ACLの勉強などをしていました.ACLの機能については,ひととおり勉強しておくと良いと思います.

あとは,アルゴ式などでDFSなどのテクニック(サイクル検出など)の勉強をやりなおしたのですが,これはかなり効きました.そういうのがスラスラ書けるようになって,ABC序盤の安定感がかなり増したと思います.

入黄までのモチベ

やはりオンサイトでいろんな人と交流できたことですね.橙コーダーや赤コーダーもちゃんと人間の形してるんだなって思いました.

好きな自作問

これです.

yukicoder.me

数えたいものがすり替わる感覚がかなり好きですね.実装はかなり単純なので,見た人全員解いてください.☆4は過剰かなと思っていたのですが,バケモンが☆3を提案していてバケモンはバケモンだなと思いました.

終わりに

入黄達成,やった~

*1:シャドバは今も全然続けています.レートなどはやっておらず,ランクマ毎期グラマスを目標に頑張っています.またやる気が出ればレートやるかもしれません.今期デッキない助けて~

*2:このティルトって誤用?

*3:正しいことが検証されれば公開しますし,そうでなければなかったことにします.