重い腰を上げてAtcoderを始めた(青)

5年ぶりです。タイトル通りの三日坊主です。

2022/04/23(ABC249)、重い腰を上げてAtcoderを始めて、05/28のABC253(5回目の参加)で水色、06/26のARC143(10回目)で青になったので一応記事を書きます。

どうして今更

  • Project Eulerをやってて、300問くらい解いた
  • AtCoderの存在は知ってたが、4問時代は全問正解しても、その中の速さで決まってたのを見て、(のんびりやりたいタイプなので)あんまりやりたくならなかった
  • 最近見たら、いつの間にか8問になってて、毎週あるABCで2000まで上がれて、しかも純粋に解ける数が重視されるようになってたのでやってみることにした
  • cargo-atcoderやcargo-competeのようなツールが充実していて、安全で、高速なRustを使ってやってみたかった
    • コンパイル有りなのでCEで済む場合がある、てきとうに書いててもCのように危険な落とし穴を踏みづらい。型が強力で抽象化しやすい。

練習方法

一応ProjectEulerからの転生組なのであんまり参考にしないほうがいいかもしれないけど、私のやり方

  • 解けることがわかっているクラス(300以下など)はあんまりやらない
    • 他の人はたくさん埋めたりStreakを稼いだりしているけど、飽きっぽくてめんどくさがりな私には向いてなさそうだと思った。
  • 解けるけどちょっと時間がかかる問題の方針を速く立てることを重視して、問題を見て方針が思いつかなかったら解説を見るトレーニングをやる
    • これに使うのは典型の多いとされるABCがよい。ARC以降は考察ウェイトが多くネタバレが致命的かもしれないので、後の練習に取っておいたほうが良さそう?
    • とりあえずはコーディング速度を上げるよりこっちのほうが楽そうだと考えた。
    • 難易度を見積もるのが早くなると、前から順にABCDEF(2000)ではなくABCD+(EorF)+(GorEx)(2100)、というふうな選択肢ができる上に点数有利な目標ができる
  • たまにライブラリ整備兼ねてAtcoder ProblemsのRecommendationのModelate,Difficultを適当にバチャコン化して解いてみる

    • 解説を読んだらその問題は寝かせて、後日再挑戦する
  • ちなみに、私は持ち込みライブラリがないと時間内に正しく実装できないタイプなので、整備は時間外にやってる

  • 作ったライブラリ

    • (関数を渡しての)二分探索。答えを決めて二分探索とかに重宝する。
    • LazySegTree(抽象化つき, 一番のお気に入り)
    • SparseTable
    • 座標圧縮
    • Union Find (高さを持ってない手抜き)
    • Convex-Hull (Monotone Chain)
    • グラフアルゴリズムは概ねpetgraphで解けるが、なぜかDinicとか、ベルマンフォードの到達不能な負の閉路を除外したものとかがないので、そこは自分で書いた
    • 連立方程式
    • 素因数分解, GCD, 拡張ユークリッドなど
  • 自分に合った解法を見つける、その上で広げる

    • 例えば、解説に公式解説とユーザー解説でニ種類以上の解法が載ってたりする。正解は一つではないということ。
    • ぐちゃぐちゃだろうと自力で解ければえらい。その上で他の解法を見ると思考の幅が広がるし、いつか似た問題が出たとき使える考え方が身につく。
    • コンテストは短いので、(自分にとっての)難易度の見積もりが重要。(特にA-Dが絶対解けてEFGExから選ぶ場合)得意技が使える問題、不得意な問題を見極められると楽。
      • ちなみに私はLazySetTree抽象化による区間クエリはどちらかというと得意技のつもりだったけど、ABC256で区間が2問出たにもかかわらずそれ以外しか解けなかったいうことがある。
    • これはどこかの色変記事で見た「想定解で解けるようにしろ」(意訳)に対するカウンター

今後

しばらくはライブラリ整備のために毎回は出ないつもり。今年中に黄色くらいを目標に。

コイントス:どっちの列が先に出る?

こんなゲームが(ずっと前?)話題になってたらしい。

ルール
先手、後手がそれぞれH(表)かT(裏)で構成されるL文字の文字列を決める
(ただし、後手は同じ文字列は選べません)
どちらかの文字列がマッチするまでコイントスを続け、先に出た方が勝ち。

たとえば、
A: HTT
B: HHT
コイントスの結果: HTHTHTT
だったら、Aの勝ち。

先手が選んだものの最後の文字だけ逆にすれば、勝率は50%(同時にリーチで、最後の一投で決まるので)
明らかに後手は50%以上の勝率を確保できるのであるが、各組み合わせの勝率はいくらなのでしょうか。

それを計算するプログラムを書いてみました。こちら。
Web-based online coding environment | paiza.IO

原理は"ちゃんとやろうと思うと"わりと難解なので次回以降ここで解説してみます。

自己紹介

とある大学の数学科の学生(執筆時点で2年生)です。 広義の数学(物理・工学・情報等々)全般に興味があります。

プログラミングができますが、 自然言語と(特に人の名前を)覚えることは苦手です。

私の誕生日は、各桁の数字の和が月に等しく、各桁の数字の積が日に等しいです。これは一意に決まります。 (上の桁は0で埋めません)

ここでは、その時々で興味を持った分野の数学について語るつもりです。 たまに間違えたりするかもしれませんが、その時はご指摘ください。