Commentārius Tobisatis

2024年9月7日、AtCoder Beginner Contest 370で黄色に到達しました！ https://x.com/tobisatis/status/1832423259440345214 初参加が2018年9月1日で、黄色になるまで6年をかけました。いわゆる初めての色変記事というやつで、競プロをはじめてから黄色到達までを振り返ります。原則時系列順に書いていくので、練習の様子、AtCoderをやっていたおかげで就職できた話などがランダムに出てきます。問題の内容については、一部リンクを掲載するものの、ほとんど書きません。 スペック 黄色到達当時28歳 競プロ初参加は22歳、大学卒業半年前 現役ソフトウェアエンジニア エンジニア歴は合計で4年ちょっと  経営学部卒 数学は大学1年生の微積と線形代数まで、プラス統計を少々 計算機科学の前提知識はゼロ 初提出まで プログラミングを始めたのは大学2年の頃だった気がします。一定間隔で音を鳴らすタイマーが欲しかったので、見よう見まねでC#で作りました。大学3年の暇だった頃にふとオンラインゲームが作ってみたくなり、無料レンタルサーバーを使って遊んでいました。HTML、JavaScript、PHPを少し覚え、データベースとの接続ができたあたりで満足して（面倒になって）やめました。 競プロを始めたのは大学4年の夏休みです。暇だったのでなんとなく難しそうなことに挑戦したくなり、見つけたのが競プロでした。 ある程度過去問を見てから初参加したABC108は、Aのみの1完でした。浮動小数点数などを理解しておらず、 提出 にはC問題で阿鼻叫喚している様子が残っていました。 水色到達 ABC126より前のABCは4問体制で、Rated上限は1200でした。この節目である水色に達したのは2019年1月、初提出から約4か月後でした。 あくまで個人的な体感ですが、当時水色まで到達するのは今と比べるとずっと簡単だったように思います。ABCのC問題によく置かれる300点は、基本的なソートや全探索ができれば解けるといった問題が多かったように感じています。D問題は解けないことのほうが多かったのですが、運良く解けると上限である1600程度のパフォーマンスを得られ、これが5回ほど積み重なって水色になりました。 成功した回の問題を見返してみると、本当に運

 問題リンク   https://atcoder.jp/contests/arc044/tasks/arc044_c  解説  縦のビームが飛んでくるとき、高橋君は横に逃げます。このとき、縦に逃げる必要はないため、縦方向の座標は考えなくてよいです。横のビームも同様です。したがって、縦に逃げる回数と横に逃げる回数を独立に計算して足し合わせれば答えが求まります。  縦のビームを考えましょう。各時刻にそれぞれの座標にいるときの移動回数の最小値を、配列\(move\)で管理します。最初、すべての座標について移動回数は\(0\)です。 \[\begin{array}{c|c|c|c|c|c|c|c} \text{座標} & 1 & 2 & 3 & 4 & 5 & 6 & \ldots \\ \hline \text{移動回数} & 0 & 0 & 0 & 0 & 0 & 0 & \ldots \end{array}\]  ここで、ある時刻に座標\(2, 3, 4, 5\)にビームが通過したとします。次のようにして移動回数を更新してみましょう。 ビームが通過した直後に座標\(2, 3, 4, 5\)にいることはないため、これらの座標の移動回数を無限大とする ビームが通過した座標に、その左右の位置から移動してくる。ビームが通過した座標を\(p\)として、\(move(p) = 1 + min(move(p - 1), move(p + 1))\)で更新する  手順2を座標\(2, 3, 4, 5\)の順に左から行うと、更新後の移動回数は次のようになります。 \[\begin{array}{c|c|c|c|c|c|c|c} \text{座標} & 1 & 2 & 3 & 4 & 5 & 6 & \ldots \\ \hline \text{移動回数} & 0 & 1 & 2 & 3 & 1 & 0 & \ldots \end{array}\]  これは最適ではありません。座標\(4\)に移動するためには、座標\(6\)から左に2回移動するのが最適です。このよ

 問題リンク   https://atcoder.jp/contests/arc034/tasks/arc034_4  前提となる知識 重複組み合わせ \({}_n \mathrm{H}_r = \dfrac{(n + r - 1)!}{(n - 1)!r!}\)  解説  次のようにカードを引いた場合を考えます。   \[a_1, b_1, a_2, b_2, b_3, c\]  このとき得点は\((a_1 b_1 + a_2) b_2 b_3 = a_1 b_1 b_2 b_3 + a_2 b_2 b_3\)です。\(a\)に\(b\)をいくつか掛け合わせて、それを足した形をしていることがわかります。    赤いカードから1枚選び\(a^*\)とし、青いカードから\(k\)枚を選んでその積を\(B^*\)とします。得点に\(a^* B^*\)が足し合わされる確率が分かれば、それに\(a^* B^*\)をかけたものについてすべての選び方に対して和をとることで答えが求まります。この確率は、得点に\(a^* B^*\)が足し合わされるような山札の並び方の総数をすべての山札の並び方の総数\((A+B+C)!\)で割ることで求めることができます。  条件を満たすような山札の並びは、次のようにしてすべて作ることができます。 選んでいない赤いカードをシャッフルして並べ替えておく。\((A-1)!\)通り 選んだ青いカードをシャッフルして並べ替えておく。\(k!\)通り 選んでいない青いカードをシャッフルして並べ替えておく。\((B-k)!\)通り 湯たんぽのカードをシャッフルして並べ替えておく。\(C!\)通り  「選んだ赤いカード1枚」、「選んだ青いカード\(k\)枚」、「湯たんぽのカード\(C\)枚」をこの順番で列に並べる。1通り  「選んだ赤いカードの直前」または「湯たんぽのカードの直後」の\(C+1\)通りの場所に選んでいない青いカードを並べる。\({}_{C+1} \mathrm{H}_{B-k}\)通り 例えば選んだ青いカードを\(b^+_1, b^+_2, b^+_3\)、選んでいない青いカードが\(b^-_1 \ldots b^-_4\)、湯たんぽのカードを\(c_1, c_2, c_3\)とすると、\(b^-_1, a^*, b^+_1, b^+_2, b^