Commentārius Tobisatis

 4msで動作した本番69位の解法を紹介します。  問題リンク   https://atcoder.jp/contests/ahc044/tasks/ahc044_a  解説  何人かの社員を選んで一列に並べ、社員を頂点、次の割り振りへの遷移を辺としたグラフを考えます。簡単なグラフをいくつか作って挙動を確かめてみると、次のようにして構築できるグラフの性質がよさそうなことがわかりました。 割り当て回数が偶数のとき（画像橙線）、次は右隣の人に割り当てる ただし右端からは左端を割り当てる 割り当て回数が奇数のとき（画像青線）、次は左隣の人に割り当てる ただし左端からは右隣を割り当てる  左端から始めてこのグラフを一周するまでにそれぞれの頂点を訪れる回数は、頂点数を\(k\)とするとき、左から\(k, 2k - 2, 2k - 4, 2k - 6 ... , 6, 4, 2\)となります。右端の頂点を訪れる回数を基準に、その1倍、2倍、3倍、……、k - 1倍の回数だけ訪れる頂点を作れるので、 各社員の割り当て回数の目標が一様ランダムであることを考えると、問題をこのグラフに帰着させることでそこそこよさそうな割り当てが得られそうだと感じられます。  実際にこのグラフ（以下、元のグラフ）にすべての社員を当てはめる際には、ひとつの頂点に複数の社員を対応させたくなります。次のように構築する（以下、割り当てグラフ）ことで、同じ回数だけ訪れる複数の頂点を並べることができます。  割り当てグラフにおいて、\(L\)回目の頂点を訪れるまでにある頂点を訪れる回数は、\(\frac{Lkv}{SN}\)と見積もれます（元のグラフにおいて一周するまでに訪れる頂点の合計を\(S\)、選んだ頂点に対応する元のグラフの頂点を一周するまでに訪れる回数を\(v\)とする）。元のグラフのひとつの頂点に対応させる社員の数がおよそ\(N/k\)であることを用いています。  \(k\)を\(N\)まで試し、それぞれの社員について割り当て回数が上記の見積もり回数に一番近い頂点に当てはめることで、割り当てグラフを構築できます。実装上、元のグラフの頂点に最低一人の社員を当てはめるようにする必要があります。スコアの評価も見積もった値か...

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...

 問題リンク   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\)、湯た...