Atcoder水色になりました

はじめに

108回目のABCで煩悩まみれの入水を果たしました。

全国10億飛んで7人の皆様始めまして、あかしあと申します。
色変したら記事を書く権利が与えられるそうなのでこれまで何をしてきたかをつらつらと書いていこうと思います。
拙文ではありますがお付き合い下さい。

本記事には大量のポエムと気持ち程度の精進内容、覚えたアルゴリズムなどを書きました(予定)
ポエムは隠しておくので読みたい人だけ読んでください。

バックグラウンドと自己紹介

・IT系企業勤務の社会人
・atcoder使用言語:python
・情報系の皮を被った学部を卒業しました

「あかしあ　みどり」です
後述しますが精進をyoutubeで垂れ流しています
atcoderアカウント:https://atcoder.jp/users/akasia_midori
twitter: https://twitter.com/akasia_midori
youtubeチャンネル: https://www.youtube.com/channel/UCkIaUs9Z43s1cSLS8mh9ppg

緑色になるまで

ポエム1 ~ 最初の空白期間について

最初の空白期間について

atcoderに登録したことを忘れている期間です。
友人にABCに誘われて登録しようとしたら「そのメールアドレスは使用されています」的な文言が出て何回か驚いていました。

この期間は無職という名の人生の夏休みに入っていて、今の間だけでも人生謳歌しよう！と意気込んでいたのですがいざ入ってみると何も手につきませんでした。
減っていく残高が自分の余命のように思えてぼんやりとした不安が常にまとわりついていました。(入水ﾌﾞﾗｯｸｼﾞｮｰｸ)
余命の供給源さえあれば無敵だと思うのでみなさんは石油王になってから人生の夏休みに入ってください。

追記:一回転職成功したら無職になっても何とかなるという謎の自信がつきました

精進をするようになってからのことを書きます。
今とは環境が大きく異なっている点に最大限の注意を払った上で 斜め読み してください。

この頃(ABC151ぐらい)は灰色の次の問題が緑以上のdiffなことが多く、灰diff早解きでも緑パフォがそこそこ出ていました。
振り返ると精進量の割に緑にまでなれたのはこの崖のおかげ

精進内容

・ログを見る限り2、3日に1問ぐらいのペースで解いていました(2019/8 ~ 2020/7)
・コンテスト中に取り組んだ問題で解ききれなかったら解けるまで粘っていました

使えるようになっていたはずのアルゴリズム

・再帰(dfs, bfs)
・本当に簡単なdp(EDPC-Aなど)
・累積和(imos法も含む)
・二分探索

ポエム2 ~ 取り組み方の失敗

取り組み方の失敗

この時期の失敗として書いておきたいのは、問題を自分の中で「解ける問題」と「解けなくても仕方ない問題」の二つに分けてしまったことです。
Eは解けなくても仕方ない、水色以上は解けなくても仕方ないと言い訳して真剣に考えることをしなくなっていました。

このままではマズいということで色も問題の区分(DとかEとか)もなるべく表示せずランダムに選んだ問題を解くようにしました。
解けてから色を確認すると水色だったりして「なんだ、案外いけるじゃないか」と問題に挑戦する勇気を取り戻せたのをうっすらと覚えています。
自分で自分を縛ってちゃ世話ないよね。

黄diff? 解けるわけないでしょ(ヾﾉ･∀･`)ﾑﾘﾑﾘ

水色になるまで

復帰したら教材があふれていたので色々やりました。

ポエム3 ~ 社会人(主語ひろめ)は精進時間も取り難い

社会人(主語ひろめ)は精進時間も取り難い

私に限った話かもしれませんが自分で管理できる時間がそんなに無いです。貧乏暇なし。

ここの期間(合計1年強)は精進0だよ

社会人には厳しいコンテンツだ・・・と嘆いていたのですがコロナのおかげである程度自分の時間を確保できるようになりました。
具体的には以下で精進時間が取れるようになりました

• フルリモートできるようになった
  • 通勤時間が2時間から0になったことでとても楽になりました。(一方で通勤の徒歩ですら大事な運動だったんだなと気付きました)
• 忙しくないときは定時後の精進時間を会議設定しちゃう
  • 良識ある人は会議中の人に話しかけません。
• 飲み会を断る
  • 不要不急!

ポエム4 ~ 約半年atcoderから離れて

約半年atcoderから離れて

精進量も多いほうではなかったので半年も離れるとかなり多くのことを忘れていました。
(デスマーチって長距離を全力疾走するぐらいの苦行なのでそれ以外のことが抜け落ちがち)
忘れる筆頭はDPなのですが、二分探索の単調性の大事さも吹っ飛んでいたときは愕然としました。
半年離れるたびにレート100ぐらい消滅してたんじゃないかな・・・

精進ペースについて

色々終わって楽になったのと3日に1問ペースじゃ流石に悪かろうということで2021年の10月末からyoutubeで精進を垂れ流すようにしました。
部活みたいな強制力があり、多少眠くてもやるようになりました。案外頑張れば出来る。

「精進見てても楽しくないし人は来ないでしょ」と思っていたのですが案外人が来てくれて精進のモチベになっています。
精進配信に見に来てくれてる方には大変感謝してます。(もうちょっと何か楽しめるようにしたいね)
平日21時から精進してるので良ければ覗きに来てください。

下記グラフは精進グラフです

2021年11月のリハビリ中に茶色に落ちるギリギリのところまで来てるので1年で頑張ったなぁ(しみじみ)

ポエム5 ~ 具体的な精進時間

youtubeでの精進時間

この期間はログが全て残ってるので精進時間を正確に測れています
1年で172回放送していて平均1時間程なので・・・
いっぱいしょうじんしました

精進方法について

以下を行いました。

• 緑埋め(🧪除く)
• 水色埋めを行いました(ABCのみ 🧪除く)
• こどふぉを適当にいくつか
• 精選100(https://qiita.com/e869120/items/eb50fdaece12be418faa)　　
• 典型90の★5まで埋めた(https://atcoder.jp/contests/typical90)
• youtubeで精進垂れ流し

ポエム6 精進で気を付けたこと

精進で気を付けたこと

• streakを伸ばさないこと
  • 私の性質上、streakが切れた時に全てのモチベが消滅する可能性がありました。atcoder本体に関係ないところでリスクを背負いたくなかったので意識して続けないようにしました(今平日しか精進していないのですがそれが理由だったりします)
• 自分の色以上の問題を精進の問題として選ぶこと
  • 解ける問題を練習しても速く解けるようになるだけでいずれレートは頭打ちになってしまうと思ったのでこうしました。(現在早解きがとても苦手なのはこの思想が原因な気もしてます。きっと大事なのはバランス)
• 持続可能性を高める
  • 精進にもさすてなびりてぃが大事。無茶な精進をしてモチベを破壊しないようにしています。streakを伸ばさないもここに入るかもしれません。
  • より優先度が高いものが生えたら短期間に終わらせるようにしています
    　具体的に言うとライザのアトリエ1,2 ソフィーのアトリエ1,2を直近3か月ぐらいでやりました。合計プレイ時間は120時間超。

使えるようになった色々(応用できるとは言ってない)

色んな抜けがありそう

• 木
  • セグ木
    • 遅延セグ木
  • 木の直径
  • Union Find（これは木であってますか？）
  • クラスカル法
  • BIT(転倒数の求め方も含む)
• グラフ
  • 有向グラフ
    • サイクル判定
    • トポロジカルソートとその性質
  • 無向グラフ
    • サイクル判定
  • ダイクストラ
  • ワーシャルフロイド
• 数学
  • 重複組み合わせ
  • フェルマーの小定理
  • 調和級数に関する考察
• 累積和
  • 2次元累積和(2次元imosとかも)
• 探索
  • 二分探索
    • 決め打ち二分探索
  • 三分探索
  • 01BFS
  • しゃくとり法(元々時間をかければ書けてたけど頭が壊れにくくなった)
  • ダブリング(ここに入れていいですか？斧投げないでください)
  • Mo's algorithm
• SortedSet(tatyamさんありがとうございます！)
• DP
  • 桁DP（複雑なものはできない）
  • 耳DP（複雑なものはできない）
  • bitDP（複雑なものはできない）

余談

ポエム7 余談のポエム

時々atcoderやっても実力付かなくてへこむ・・・ みたいな人が多いのでこれを置いておきます

競プロerにあんまり知られてないかもしれないけど新人研修でif for クラス ユーザー関数教えたら後は現場に送りつけろみたいな事業者は大量にいるので
「実行時間が半分以下に?!いったい何をしたんだ!」
「何って連想配列を使っただけだが?」みたいなことはちょいちょいあります
内緒だよ

— あかしあ みどり (@akasia_midori) November 13, 2022

未経験歓迎！現場に入れろ！ﾊﾘｰﾊﾘｰ！みたいな事業者は多くて、そういう業者程上記ツイートみたいなことになっています。
それらが出来てれば業務の9割以上回るのは事実ですが。(もちろん場所による)
ただ、「最低限動く」から「効率的に動く」にするには知識がないとできるのかもわからないし、そもそも「効率的に動かす」という視点すらないことがままあります。
そんなとこで†二分探索†とか振り回してごらん？もうあれよ？すごいよ？

ポエム8 モチベを保つために

レートは相対評価だしパフォーマンスは標本の一つ

こんなパフォとってしまった。。。
あると思います。
結構心に来るので私は以下のように考えています。
一言でまとめると「統計リテラシーを高めれば無傷」です。

人間のパフォーマンスって体調とか問題の得意不得意とか様々な要素で決まるものなので毎回のABCで自分の絶対的なパフォが出ている訳ではないです。
神がいたらレートをxにするんだけど人間ではだいたいy±Nの範囲にxがありそう位しか言えなくて、今の自分のレートはそんな曖昧な範囲の中から出ているんだぐらいに考えています。
(もちろんABCで自分の不得意なものが分かったら克服した方がパフォーマンスは上がりやすいでしょう)
そもそも試行回数も数十回程度じゃ少なくて偏りも当然出るでしょう。数年経過したら母集団も変わってるでしょうしあまり気にしないことです。
一回絶望的なパフォを出してもそこまで気にしない方が良いです。所詮一回のABCのパフォなんて標本の1つで外れ値なのかもしれないのですから。
統計リテラシーを高めれば無傷です。