【コンテスト開催記】AtCoder Regular Contest 212

AtCoder の公式コンテストで初めて Writer を務めました。

ARC の Writer をやるのはずっと夢だったのでとても嬉しいです。

ARC212

Tester の Nyaan さん、 maspy さん、Admin の snuke さん、ありがとうございました。

経緯

レートHighest 黄色の人が ARC の writer をやるのは前例が無いと思いますが、snuke さんがDMでスカウトしてくださり、例外的に writer をやらせていただけることになりました。

snuke さんは自分が以前開催した yukicoder の単独コンに参加してコメントしてくださったり、あーだこーだーの配信で興味ある writer(?) で milkcoffee の名前を挙げてくださったりしていました。TUPC の問題も見てくださっていたみたいです。今まで作問を頑張ってきて良かったと心底思いました。

社会人になって競プロ(特にアルゴ)に割く時間が減っていたところでこのDMが来たので、狂ったように作問をしていた時期を思い出して再び作問集中期間に入りました。作問ストックは結構ありましたが、ARCに良い問題を出したい一心で頑張りました。結局、今回は A と C 以外はDMを頂いた後に作った問題です。

全体の感想

開催前は不備がないか心配でしたが、無事にコンテストを終えることができて安心しました。

気づいたら一瞬で解ける問題が多いこともあり、全完が大量発生しないかと思っていましたが、Rated の全完は 17 名だったらしく、耐えたと思います。

個人的にはもっと面白い問題を作りたかったという反省もありますが、コンテスト後の感想ツイートを見る限りある程度は満足いただけたみたいで良かったです。

各問題について

AとDがもう少し解かれて、Bがもう少し解かれないと思っていましたが、難易度傾斜は概ね予想の範囲かなという感じです。

以下、ネタバレ有り

A. Four TSP

AGC の「C4」みたいな問題を作りたくて作りました。N=4 の完全グラフのハミルトン閉路を書いてお絵描きしていたら、通らない辺が良い感じにグループ分けできることに気づいたので、これを使う問題設定にしました。

原案を考えたのは2年くらい前だった気がします。

想定解は O(K^2) ですが、 O(K) でも解けます。

B. Stones on Grid

完全に解法から考えました。つまり、「最小のサイクルを作る」というグラフ問題を、できるだけ別の設定で置き換えたものを考えて作りました。何かの問題を考えてグラフに帰着できると面白いですよね。

解法から考えたので難易度が読めなかったですが、思ったより解かれたなという印象でした。人によっては A よりも解きやすかったかも？確かに今回のコンテスト内では最も再現性を持って解ける問題かもしれません。

C. ABS Ball

このままの問題設定を考えて、それが解けたので出題しました。積の和典型を使いたくてこういう設定の問題をたくさん生んでいた気がします。FPS解法はまだ読めていないので読んでおきます。

この問題も2年前くらいの原案です。

D. Two Rooms

今回のコンテストの主役かつ問題児です。

「山登り法」を使った問題を作れたら面白いかなと思って考えた問題です。少しアルゴから離れていたことでこの発想に至れたのかもしれませんね。

山登り法とは局所解にたどり着いてしまう可能性がありますが、逆に言えば(何らかの意味で正の進展があれば)必ず局所解にはたどり着いてくれます。局所解は「これ以上進めない」という条件を満たしていると言えるので、その条件を問題の条件にしてしまえば、山登りをアルゴでも出題できると考えました。

当初は500点で提案しましたが、色々あって 600点になりました。snukeさんが解説放送でこの問題がコンテスト最難と言っていたように、ハマった人がいるかもしれません。証明込みで AC した人は何人いるんだろう。

自分は面白いと思って出題しましたが、かなり好き嫌いが分かれそうだなと思います。自分が参加者だったら絶対に嫌ですね。adhoc 過ぎると逆にウケないというのが経験上ありますが、それでも出したくなってしまう。

E. Drop Min

このままの問題設定を考えて、それが解けたので出題しました。本人は解くのに2時間くらいかかったと思います。

内容は割と典型寄りだと思いますが、細かいところを詰めるのが辛いと思います。

F. Add Integer

元々は A_{i+2} = |Ai - A_{i+1}| という設定で何か問題を作れないかと考えていましたが、逆から見たら2パターンの遷移になることに気づき、今の問題設定にしました。

逆から見るという発想をした後の高速化パートも綺麗になって面白いと思います。自分の作った問題ではこのタイプの高速化を使うのは初めてな気がします。

終わり

というわけで幸いにして ARC writer デビューをすることができました。

競プロ引退したら作問に関する記事をまた書こうかと思いましたが、自分が使いたいのでしばらくは自分用に取っておこうと思います。

以前書いた作問方法の記事はこのブログの過去記事に載っているのでそちらもぜひ。

自分の過去の作問リストは以下から見れます。暇な時に解いてみてください。

hackmd.io

また作問頑張ります！

【コンテスト開催記】yukicoder contest 440

yukicoder で3度目となる単独コンテストを開催させていただきました。

yukicoder contest 440

およそ 1 年半ぶりの単独コンテストでした。

作問は定期的にしていたのですが、昨年は就活で忙しくてあまり時間が割けなかったので結果的に久しぶりのコンテスト開催となりました。

テスターをしてくださった Y.Y.さん、first_vil さん、nonon君、suo君、とりゐ君、ありがとうございます！！

各問題へのコメント

各問題の出来た経緯やお気持ちを書きます。解法への言及もあります。

今回も 「ARC っぽい問題」を目指して作りました。

A : Take and Flip

問題設定から考えました。ギャグですが、気に入っています。

もともとは first さんとの共同コンテストで出す予定でしたが、有耶無耶になってしまったのでここで出すことにしました。

B : Comment Out

問題設定から考えました。C++ でコード書いているときに行を範囲選択しながら「Ctrl + /」を押して「//」が増えるのを見て思いつきました。

これも結果はギャグですね。自分は解法が思いつくまでそこそこ時間がかかりました。

C : Flip Trimino

解法から考えました。反転させて偶奇で不変量みたいな問題はかなり典型化してしまったので、mod 3 の場合を考えて作りました。

要するに全てを白にできる必要十分条件を考えさせる問題を作りたかったのですが、判定問題だと貪欲にできちゃったりしそうだったので、数え上げにしています。

自信作なので前の方に置きたくて C にしましたが、数え上げにしたのもあってか B との崖が出来てしまったのが反省点です。

D : Diagonals

問題設定から考えました。始めは N*M の長方形のグリッドのみでしたが、流石にエスパーされそうな気がしたので任意のグリッドグラフにしました。

adhoc 度は低い？今回のセットの中だとそんなに気に入っていないです(?)

E : AND Constraints

今よりシンプルな問題設定を考える → 嘘解法を思いつく → その嘘解法が正しい解法になるように問題設定をいじる　という手順で作りました。

今回のセットの中で一番最後に作りました。数え上げっぽい数え上げを作りたくて作ることができたので嬉しいです。難しいけど面白いと思っています。

F : RGB Plates

解法 (最小値のみ考えれば排反という制約を考えなくて良いという考察) から考えました。今回のセットで一番最初に作り、この問題を出すためにコンテストを作りました。

↑の考察に鳩の巣原理をかけ合わせて解くというのが非常に面白いと思っていましたが、鳩の巣原理を使わずとも bitset で解けますね・・・。想定解でない方法で解いている人が多そうでした。

簡単な解法を思いつけなかったので難易度の逆転も起こってしまいました。反省点ですが、どうしようもない気もします。

G : Leaf Eater

問題設定から考えました。

シンプルな設定で気に入っています。根から葉の距離が関係なく、枝分かれする場所が重要という性質が見たこと無かったので面白かったです。

★3.5 想定でしたが、全体テスターの Y.Y. さんの助言で 4.0 になりました。実際解いた人は少なかったので上げて良かったと思っています。

最後に

卒業前にゆきこで単独コンテストを開けて良かったです。来年からは社会人になるのでどのくらい作問ができるか分かりませんが、余裕があればまた単独コンテストを開きたいです。今回没になった単体の問題もゆきこのオムニバスとかで出すかもしれません。TUPC が(もしあれば)そちらでも writer をやりたいと思っているのでよろしくお願いします。

【AHC024】 19位解法

AtCoder Heuristic Contest 024 で 19位を取ることが出来ました。

順位表の1ページ目に載るのはアルゴ部門含めても初めてのことで嬉しいです。

記念に書いてみたかった解説記事を書こうと思います。

最終提出のビジュアライザは以下の通りです。

seed : 0 で 1935点です。

最終提出の内容

提出したコードのアルゴリズムは以下の通りです。

1. 行・列を削除する。
2. ランダムに隣接するマスの色に置き換える。
3.  1と2 を反復する。
4. 外側を空白にする。

以下に詳細や実装方法などを書きます。

1. 行・列を削除する。

位置関係を保ったまま大きい区画を縮めたくなり、この操作を思いつきました。

実装としては マスが存在する全ての列において以下を行ってます (行も同様)。

1. 選んだ列を全て空白に置き換える。
2. その列より右を全て 1 マスずつ左にずらす。
3. その結果、条件を満たすならば採用。満たさないならば元に戻す。

削除は行と列で交互に行って「1行目、1列目、2行目、2列目・・・」みたいに見ています(これが良いかどうかは怪しい)。

また、条件を満たすかどうかの判定は高速化は特にせず、 O(N^2) で行っています。

seed:0 でこれを 1 周すると以下のようになります。これだけでも 1000 点超えます。

2. 隣接するマスの色に置き換える

行・列の削除をより行えるようにするためには、盤面に変化を加えたいです。

そのために隣接するマスの色に置き換えることを行います。

削除できる行・列が無くなるたびに、以下の操作を1000回行います。

• ランダムに(空白でない)マスを選び、それと隣接するマスの色に置き換える。
  • 隣接する色も同じ色だった場合は置き換えずスルーする。
  • 隣接するマスが空白の場合、実行時間が 1 sec 未満ならばスルーする。
• 置き換えた結果、条件を満たさなくなったら元に戻す。

seed:0 で実験したところ 1000 回がちょうど良かったので1000回にしています。

「隣接するマスが空白の場合、実行時間が 1 sec 未満ならばスルー」というのは、早い段階で空白マスへの置き換えを許容してしまうことで削除できた行ができなくなったりするため入れた処理です。

ここでの条件を満たすかの判定も高速化していません (ここは流石にした方が良かった)

隣接マスの色に置き換える処理を入れたことにより、削除できる行・列が増え、よりスコアが伸びました。

3. 1 と 2 を繰り返す。

時間いっぱい 1 と 2 を繰り返します。

高速化をしていないため、ここのループは20回ほどしか回っていません。

4. 外側を空白にする

外側の無駄な土地をできるだけ空白にします。

賢い方法が思いつかなかったので、以下の処理を2回行っています。

• 空白マスと隣接するマスを空白マスに置き換える。条件を満たさなくなればもとに戻す。

これらを実装した結果が以下のビジュアライザになります。(最初に載せたものと同じ)

やらなかったこと

やったけど上手く行かずに不採用 or 思いついたけどやらなかった、やれなかったことのまとめです。

• 地図を1から構築する (かなりしんどそうなので最初に捨てた)
• 行・列だけでなく斜めにマスを選んで削除 (やってみたけど削除できる場合が少なすぎた)
• 削除する行・列をランダムにして、複数の状態を保つビームサーチ (試行回数が少なすぎるため改善が見込めない、高速化が上手く出来ていれば効果あるかも)
• 色iと色j の隣接個数の差分を計算することによる高速化 (時間がなく断念)
• 行・列の全体ではなく部分を削除 (時間がなくて断念)

良かった点

• 盤面を保持する二次元配列の外側に色0のマスを 1周分作ることで、実装がかなり楽になった。
• 前回のAHCから class を使うようになり、実装がかなり楽になった。
• 高速化を諦めてとりあえず点が出る方法を実装したため、時間内に間に合った。

反省点

• seed:0 しか見ていなかったので多様なケースに対応出来なかった。
• 終盤、新しい操作を考えるよりもパラメータ調整などに時間を使ってしまった。
• 順位表を見てドキドキするだけの無駄な時間があった。

感想

問題を見た瞬間にこれは楽しそうだなと思って、実際に楽しみながら良い順位を取ることができたので良かったです。

考察については、行・列の削除という操作が早めに思いついてそこからスムーズに進んみました。上位の方と方針がわりと似ていて、あたり方針を引くことが出来きたなと思います。

実装についても、途中参加でかなり焦りながら実装していましたが、特にバグらせずに実装し続けることができ、自分にとってはかなり調子が良かったと思っています。

また、今回でついにアルゴのレート (highest:2104) をマラソンのレートが超えました。

橙になりたいけど橙パフォはまだ安定する気がしていないので、かなり遠そうだなと思っています。

AHC は楽しいのでこれからも頑張っていきます。現在就活生ですが、ヒューリスティックや最適化をやっている会社も良いなぁという気持ちになっています。

記事は以上になります。ありがとうございました。

TUPC2022 参加 & 開催記

東北大学プログラミングコンテスト (TUPC2022) が AtCoder 上で開催された。

東北大の競プロサークル「puzzleknot」が主催で、自分もその一員としてwriter & 運営の手伝いをした。

atcoder.jp

初のAtCoder 上でのコンテスト & 初のオンサイトということで、普段と違う思い入れがあっため、準備から開催までを振り返る。

TUPC2022 開催決定

競プロサークルの長、sotanishy君が「今年もTUPCやりましょう」と発言したのがきっかけ。

前回の TUPC2021 は AOJ を借りてやったが、「ワンチャン AtCoder を借りれないか？」という話になる。

AtCoder 側にお願いしてみたら「kotatsugameさんが居るなら問題ありません。」ということで、AtCoder 上での開催が決定。激アツ。

さらに「オンサイトでやれたら楽しいね」という話になる。正直オンサイトのために仙台に人が集まるか不安だったが、Twitterでアンケートとったら30人くらいが「行きたい」に投票したので、それを信じてオンサイト開催することに。大学が協力的だったので、会場はキャンパス内の教室を使えることになった。

問題準備

自分はもともと作問が好きで、いつか AtCoder 上に自分の問題を載せたいと思っていたので、思わぬ形で願いが叶うことになった。

せっかく AtCoder に自分の問題が載るのだから、とっておきの問題を出したい。それに、前回は 1 問しか出せなかったので、今年はたくさん出したい。

他の3人の方がレートが高いので難しい枠は任せて、低〜中難易度のパズルっぽい問題を担当しようと思ってた。作問ストック (yukicoder で出す予定だったものとか) からお気に入りのやつをいくつか提案した。

普段から作問をしていたので、TUPC 用に問題を作るという感じでは無かったが、唯一、インタラクティブを入れたかったので頑張ってTUPC用に1問作った。

writer 陣はレート黄色前後の4人しかいないが、問題数はすぐに足りた。なんなら結構余った。

各問題について

他の問題については各 writer がそれぞれコメントしてると思うので、自分が writer をした問題についてのみ書く。

A: Sum Sort

設定から作った。条件がシンプルな感じになった。

設定は この問題 から着想を得て思いついた。

C: Flip Grid

解法から考えた。

「1箇所マスを選んで色を反転させる」というのに対して二次元累積XOR を考えると、長方形区間の色の反転になる。この問題ではそれを逆に考えれば良い。

解法は この問題 から着想を得た。操作の種類は違うが、二次元にして言い換えを逆にすれば今回の問題になる(と思う)。

わりとお気に入りの問題。採用された問題の中では最初に提案したやつ。

E: 00-11 Rotation

設定から作った。

「011 <-> 110」が 0 の偶数移動という性質を最初に見つけた。この操作だけだと 0 を追い越せないが、「100 <-> 001」が 0 を追い越すように見えれば解ける。

自分はこの手の「操作言い換え最適化問題」が大好きで、今までも似たような問題をいくつか作っている。その中でもこの問題は特にお気に入り。

オンサイトに来てくれた何人かの仲の良い人から「問題見た瞬間にmilkcoffeeのだと思った」という声をいただいた。作問の特徴を理解してくれる人がいると嬉しいし、やりがいを感じる。

最初はゆきこで以下のような問題を出すつもりだった。これを難しくしようと操作の種類を増やしたら今回の問題になった。

これだと多分緑Diff くらい。

L: Inversion High and Low

インタラクティブの問題を出したくて準備期間に頑張って作った問題。

解法を先に考えて、それを活かすように (testerの協力のもと) 頑張って問題設定を変えたり、制約を調整したりした。

Rotation と転倒数の増減に良い感じの関係があり、それを見つけるのが難しい。

本番中は1人にしか解かれなかった (その一人も想定解ではなかった)。

全問題で一番ACが少ない問題となった。インタラクティブ & 実装重い というところで敬遠されていそうで悲しい。後からでもぜひぜひ解いてください。

E 問題は、設定が「Rotation」解法が「転倒数」

L 問題は、設定が「転倒数」解法が「Rotation」

になったのが我ながらスゲーとなった (sotanishy君に言われて気づいた) 。

オンサイト本番

オンサイト会場で自分は司会をやった。

競プロ界の有名人がたくさんいる場で話すのは緊張したが、楽しめた。

コンテスト中は順位表眺めてニコニコしていたり、知り合いを応援したり。

仲良い人が自分の問題を通しているのを見るとテンション上がりますね。

終わった後の懇親会でも色々な人と話せて楽しかった。

問題面白いというお話をいただくたびに嬉しくなっていた。

不備も無く、無事にコンテストが終わって安心。

最後に

またこのメンバーで作問したいね！というわけで、おそらく来年もTUPCやります。

作問を褒められて自分は AtCoder で ARC を書きたい気持ちが高まりました。

橙になれるように（まずは黄色に戻るところから）頑張ります。

今回から常体をメインに書きました。気に入ったので次回からもそうするかも。

【コンテスト開催記】yukicoder contest 370

yukicoder で2度目となる単独コンテストを開催させていただきました。

yukicoder contest 370

参加してくださった方、ありがとうございました！

コンテスト開催にあたって

前回の単独コン を開催したときから既に作問のストックがあって、それらを消費しよう！というモチベで２回目の単独コンを開くことになりました。そう思って問題セットを組んでみると色々納得が行かない部分があって、結局は当初出そうと思っていた問題は3つしか残らず、他は新しい問題を作って出すことになりました。問題セットを考えるのはこだわりだすと止まらない(楽しい)。

自分の作問の理想は ARC みたいな問題を作ることで、典型力や実装力よりも考察力・エスパー力を問うような問題を作りたいと思っています。その考えは今回のコンテストも同じで、ARCっぽい問題を作ろうと頑張りました。いかがだったでしょうか？

テスターはTwitterで募集して応じてくれた方や知り合いの方に頼みました。p-adic さん、遭難者さん、かぽかぽさん、first さん、hamamu さん、nok0 さん、ありがとうございました！

各問題へのコメント

どういう経緯で作ったかなどを書いています。解法への言及もあります。

A問題：Triangle

シンプルで簡単でインパクトがある問題を作りたくて考えました。

Bが与えられなくても解けるというところがインパクトがあるかなと思ってこの設定にしました。

B問題：Enumeratest

この問題はかなり前から(前回の単独コンテストより前から)温めていました。

問題設定から考えたんですが、なかなか良い問題文が思いつかなくてしばらく出していませんでしたが、良い感じに文章を書けたので出すことにしました。

想定解を考えたときはエスパーで解きましたが、証明もスッキリしていて良い感じです。

C問題：Segment Zero

解法から考えました。

「実は答えが○○」みたいな問題が作りたくて考えました。

D問題：Only One Bracket

この問題も結構前から温めていました。

問題設定から考えました。

解法を考えるときは、とあるABCのカッコ列を構成できるか判定する問題を参考にしました。

Tester解が賢すぎる・・・と思ったけどそちらの方が解いている人が多そう。

E問題：MM

この問題も原案は前から温めていました。

解法から考えました。M = 11 の場合を考えると、10進数における11の倍数判定が利用できるため、考えやすくなります。この倍数判定と数列への操作を組み合わせようと思って問題を作りました。

最初は数列ではなく文字列で、各文字がA~Dのものでした。

しかし、Testerさんが想定外の解法をされたので、現在の設定に変わっています。

F問題：Segment +-

問題設定から考えました。はじめは1,-1ではなく(,) の2つであって、反転させて括弧列を作る最小の操作回数を求める問題でしたが、難しかったので変えました。

問題設定を考えて愚直解を書いてみると、実は答えが小さくなることが発見できたので、それから解法や証明を考えました。

G問題：2 Pows

問題設定から考えました。初めは1つの整数Nについて、和がNのになる場合の最小コストを求める問題でしたが、嘘貪欲とかが通りそうに思ったので少し複雑にしました。

想定解を考えるときに某有名なABCの橙Diffの問題の解法を参考にしました。

考察ステップが多くて自分にとっては今まで作った問題の中で一番難しいと思っています。

最後に

高難度を作れないのが懸念だったんですが、後ろの問題は苦戦された方が多かったみたいで嬉しかったです。その分、難易度の崖ができてしまったのがちょっと残念でしたね・・・。完璧な傾斜のコンテストを作るのは難しいと改めて実感します。

現在、めっちゃ出したい作問ストックはそんなに多くないので、単独コンテストはしばらくやらないかもしれません（作問が沸いてきたらまたやります）。

また、自分は TUPC (東北大学の競プロサークルが開催するコンテスト) の作問も担当しているので、そちらも是非参加してください！開催時期は未定ですが近いうちにやると思います！！

milkcoffee が作問した他の問題も是非見ていってください↓

milkcoffee 作問リスト - Google スプレッドシート

記事は以上になります。ありがとうございました。

【コンテスト開催記】yukicoder contest 356

yukicoder でコンテストを開催しました。

yukicoder contest 356

yukicoder での単独 writer は初です。

参加者 137 人。多くてビックリです。参加ありがとうございました！

コンテスト開催にあたって

最近ちょくちょく yukicoder に問題を出すようになってきて、単独コンテストが開きたくなったのでやりました。

難易度の制約は多少ありますが、自分の作問ストックのうち特にお気に入りのやつを出そう思いました。

全体としては考察問題（ABCよりはARC寄り）の問題を出す方針で考えていたので、「実装量＜考察量」の問題が多いと思います。

また、難易度傾斜をミスらないようにテスターは全体テスター２人（rianoさん、nok0さん）でやってもらいました。

テスターは難易度評価が正しいのも大事ですが、問題の面白さの感覚が合うのが大事だと思っていて、特に作問が面白いと思っているこの２人にやってもらいたいと思い、こちらから頼み込みました。引き受けてくれてありがとうございます！

各問題へのコメント

解法への言及もあります。

問題名の横の星は（当初の提案難易度→相談後の最終難易度）です。

A問題 ：Anti Lexicography（★1.5）

1問目はできるだけ簡単な方が参加者が多くなるだろうという目論見で、できるだけ解きやすい、かつ単純すぎない問題を作ろうと思い設定を考えました。

B問題：Tunnel（★2.0 → ★2.5）

問題設定から考えました。セットの中で一番最初に考えた問題です。

無限回魔法を使うと「.#.#.#」という構造になるという性質からこの問題を作りました。この構造を問う問題設定にしても良かったかも。
解法はシンプルですが、問題設定から正しい解法を選ぶのが難しいと思うので多くの人が苦戦していたみたいです。
B に置いたのが失敗でした。こういうタイプのは難易度評価が難しいですね。迷ったら高めにしておけば安全？

C問題：Max Middle（★2.5）

解法 ( > と < の swap) から考えました。

自分の作問こういうタイプの問題が多く、解法から都合の良い問題設定を考えるのが好きです。

操作の条件が隣接項の関係なので、そこに注目して単純化（今回は不等号の向きを考える）をすれば解きやすくなると思います。

難易度とパズルっぽさがちょうど良かったのか多くのFavを頂いてかなり嬉しいです。

A_i = A_{i+1} の場合があっても同様に解けます。

D問題：NAND Pyramid（★2.5 → ★ 3.0）

問題名から考えました。セットの中で一番最後に考えました。

設定を考えて実験してみたらキレイになってビックリ。
実験すると簡単で、理詰めしようとすると沼ってしまうため、難易度に個人差が出そうです。

証明もシンプルで、普通に全パターン考えれば必ず交互に同じやつが出ることが分かります。

E問題：Strange Arrange（★3.0）

問題設定から考えました。

最初は一番気に入ってた問題でしたが、時間が経つにつれて自明に見えてきて愛が薄れて行き・・・

想定解は綺麗だと思ってましたが人によっては典型らしいですね。あと普通に貪欲が通るらしいです。残念。

本番中は2番めの制約を考慮しなくても通るジャッジになってました。すみません。

F問題：Copy and Avoid（★3.5 → ★3.0）

問題設定から考えました。

最初は「嫌いな数」が無かったんですが、難易度上げたくてつけました。本質の難易度はそんなに変わらない？

問題設定からはあまり想像し難い「約数列挙」が登場し、そこからグラフの問題になるのが個人的に面白いと思いました。

わりと典型らしいので★を下げました。人によってはD,Eより解きやすかったかも。

G問題：010-1 Deletion（★4.0 → ★3.5）

問題設定から考えました。

最初は 010 だけでしたが、シンプルすぎたので 1 を加えたら O(N^3) が浮かび、そこから O(N^2) になりました。

010 のみの時から考えていたので、解法と証明はわりとすんなり書けました。

こういう必要十分条件を考えてDPする問題、証明を書くのが楽しいですね。

コンテストを開催した感想・反省点

参加してくれた人の解法・感想ツイートを見るのがかなり面白いですね。

Fav もたくさんついてやりがいを感じました。

難易度推定がミスったのが残念でした（特にB問題の位置）

D,E の逆転は仕方無いですが、きれいな傾斜にしたかったですね〜

G は解かれすぎなくてちょうど良かったと思います。

E のジャッジ壊れてたのも申し訳ないです。すごく単純なミスなので防ぎたかった・・・

最後に

単独 writer すごく楽しかったのでまたやりたいです。

現状作問ストックがたくさんあるので、あと 2 セットくらいは組む予定です。

オムニバスコンにも少しずつ出すかもしれません。

他の milkcoffee の作問したものも是非見ていってください↓

milkcoffee 作問リスト - Google スプレッドシート

記事は以上になります。参加＆読んでいただきありがとうございます。

AtCoderで黄色になりました

こんにちは。milkcoffee です。

AtCoder で黄色になりました！！

ARC133 で念願の黄色になることができました。本当に嬉しいです。

嬉しいので青に落ちる前に色変記事を書いてしまおうと思います。

初めましての方は青になった時の色変記事から読んでみてください！

入青！一年間やってきたこと - milkcoffeeのブログ

ということで、青になるまでのことは既に書いてあるので、青→黄のことをメインで書きます。

精進内容

AtCoder Problems の記録です

青達成時と比較していきます

青→黄で（677→1256）です。倍くらい解いたことになりますね。

水Diff(78→159)

青Diff(38→144)

黄Diff(3→41)

水Diff絶対落とさない＆青Diffが安定＆黄Diffがたまに解ける　を意識していました。

長期休みで青streak、黄streakをやろうとしたものの続かず・・・

レート遷移とそのときの気持ち

水青反復期

青になりたての時は土曜日に水落ち、日曜日に青に戻るを繰り返してました。

この頃は特にARCが得意でABCが苦手だったので、それによるレートの振動が続いてました。

青下位ゆったり期

ARCが得意でABCが苦手でレート反復してたのはしばらく続いてました。

今までと比べてレートの伸びが遅くなりましたが、それでも少しずつは上がっていたので続けることができました。

レート爆上がり！→入黄失敗

苦手だったABCを克服し、この辺りからパフォーマンスが安定してきました。水や青の問題をたくさん解いたことで低難度を安定して解けるようになったのが良かったと思ってます。

そして、大成功の橙パフォを二連続で取ってレート1991！もうすぐ黄色！というところでARC130で失敗してしまいました・・・

原因はfor文の範囲が1つだけ小さくWAが取れなかったことでした。コンテスト終了後にこれに気づいたときは発狂してました。ああ、あの一箇所さえ間違えてなければ・・・（ストレスでポテチをたくさん食べる）

このままレートが下がったら、今日が最後の入黄チャンスになってたのか、などずっと考えてました

入黄！！

入黄チャレンジ失敗後も結果は振いません。得意だと思っていたARCでもレートが下がり、黄色が遠ざかっていく感覚は辛いものでした。微妙な気持ちで年を越しました。

年明けからのコンテストで調子が戻ってきました。

ABC234ではEx問題を通し、ABC235では苦手だった桁DPをAC！

そしてなんやかんやでARC133で3完やや早解きで、ギリ入黄できました！

質問フォームへの回答

色変記事を書くために募集した質問に答えるコーナー

入黄記事のネタが欲しいので、書いて欲しいことや質問を投稿してください！ご協力お願いします〜https://t.co/ZMTL3P5VQj

— milkcoffee (@milkcoffeen) 2022年1月23日

（現在も募集中です！随時追記していく予定です）

てことでこのフォームに来た質問に回答します！

被ってる質問・答えたくないやつは削ってますすみません！

黄色になるのにいらなかったアルゴリズム（覚えてなくてもワンチャンあるだろうなというものも含む）：タナイさん

知ってるけど本番でほとんどor全く使わなかったやつ

・最小費用流、強連結成分分解、重み付きUnionFind、橋(lowlink)、Z-algorithm、ローリングハッシュ、トライ木

逆に、コンテストに出たけど知らなかったり実装できなかったりで損したやつ（どれも青〜黄Diffレベル）

・平方分割、部分列DP、スライド最小値、牛ゲー、約数包除、原始根、拡張ユークリッドの互除法

彼女との馴れ初め：タナイさん

-1 (いない場合は-1を出力します)

レートが青のとき、停滞から脱出するにあたって取り組んできたことはなんでしょうか？：Alexさん

自分はパフォが良い時と悪い時で差があったので、悪い時を減らすために低めのDiff（水〜青）の問題を重視してやり、できるだけ安定させるようにしました。

逆にパフォが安定している人は高難度を埋めると良い気がします。

競プロを始めたきっかけ：MtSakaさん

大学の講義でAOJをやったことがあって、それがスタートだった気がします。

AtCoderはコロナ流行って家に居て暇だった＆就活で役立ちそうだから始めました。

MojaCoderで面白い問題を出されていたので、当然黄色になると思っていました（質問ではない）：merom686さん

ありがとうございます！めっちゃ嬉しい・・・

作問これからも頑張っていきます！！

いままで競プロを続けるために、何かから影響を受けたのでしょうか？

他の競プロerだと思います

Twitterなどで知り合ったライバル達に勝ちたいという気持ちは強かったですね

レートが近い人が精進をしていたり、レートが上がったりしてると焦ります

何を目指し、何を成し遂げると黄色になれるのか（埋めるもの・学ぶこと・解説AC）

コンテストに出続けることが一番大事です

埋めるのは自分と同じ色のDiffが一番効率良いと思います。高すぎるDiffは本番中に出会う機会が少ないのでレートに直結しにくい気がします。

解説はARC, AGCはできるだけ見ないように、ABCはしばらく考えて分からなかったら見るようにしてます。あと解説だけ見て実装しない解説未ACをよくやります。

冷えたときの心理面の対処法

無理して元気を出そうとせず、しっかり落ち込みます。

落ち込んでいるときはコンテスト後の復習もあまりしてません

音楽を聴いてから寝るのがオススメです！

覚えたアルゴリズムとか：Lukeさん

青になるまでに覚えたやつは入青記事で書いたので割愛

青になってから覚えたやつを挙げます

遅延セグ木、最大流・最小カット、全方位木DP、部分列DP、スライド最小値、牛ゲー、約数包除、原始根、掃き出し法

彼女募集中ってほんとですか？

はい

入黄おめでとうございます！自己紹介をお願いします！

ありがとうございます！

理系大学生です！詳しくはTwitterを見てください！

一番効果のあった精進はなんですか？(T/E)DPC, typical90 は埋めましたか？

青になるまではバチャ（主にくじかつ）をたくさんやってました

青になってからはProblemsでテキトーに青Diffの問題を選んで解いたりしていました

典型90とEDPCはかなり効果あるので早めに埋めたほうがいいです！

TDPCは割と序盤から難しいので後回しでいいと思います

何をやればfとかg問題が解けるのか？：Reneeさん

ABCはとにかくDPが多いので、DPを得意にすると解ける確率が上がると思います

状態の持ち方と遷移の仕方はたくさん問題を解いていろんなパターンを覚えていくのが良いです！

同じ問題を何回も解く?：Reneeさん

バチャで出た時以外は解いてないです

AtCoderに解いてない問題がまだまだあるので、わざわざ同じ問題を解く必要はないと考えてます

実装重視の問題だったら何回解いても効果はあると思います

普段はどのくらい精進をしていましたか？

長期休暇はほぼ一日中やってました

普段はずっとやってる日もあれば、PCに触らない日もあります

コンテスト中にお腹が空いたらどうしていますか？ おすすめのコンテスト中食について教えてほしいです。：西村博之さん

コンテスト中は緊張するのでお腹が空きません・・・

コンテスト前には眠くならないようにコーヒー牛乳を飲んだりしています。

コンテスト後はなぜかめちゃくちゃお腹が空くのでポテチなどを食べてます

好きな分野/嫌いな分野ありますか：myauさん

好きな分野：swapの最小値を求めるやつ、構築、パズルっぽいやつ、bitDP

嫌いな分野：桁DP、数学色が強いやつ、ゲーム問題、幾何

印象に残っている問題：myauさん

作問を始めるキッカケになった問題 ： ABC191 C - Digital Graffiti

解説を見てたまげた問題：ARC121 D - 1 or 2、 ARC120 D - Bracket Score 2

解けて興奮した問題：ARC129 D - -1+2-1、ABC234 Ex - Enumerate Pairs

コンテスト中に意識すること：myauさん

・少し考えて分からなかったら順位表と次の問題を見る

・解けてる人数より自分が解けそうかどうかで解くか決める

・サンプルが弱いと思ったら自分でサンプルを作る

入黄記念バチャで好きな問題８問選ぶとすると？

自分のレート上げてくれたありがたき問題でセットを組んでみました

・ABC172 C - Tsundoku（初緑Diff）

・ABC178 E - Dist Max（初E）

・ABC183 E - Queen on Grid (初水Diff)

・ARC117 C - Tricolor Pyramid（初青Diff）

・ARC114 C - Sequence Scores（初黄Diff）

・ABC209 F - Deforestation（初F）

・ARC121 D - 1 or 2（初橙パフォ）

・ABC234 Ex - Enumerate Pairs（初Ex、初橙Diff）

考えてたら楽しくなってきました、やってみようかな

Congrats !! How it feels to see your handle in yellow colour ??：Rajatさん

Thank you!

There is a sense of accomplishment.

The letters look strong! :)

（Sorry for my poor English）

I actually learn a lot by seeing how others approach the problems. So, what's your first thoughts when you see a problem.：Rajatさん

First I think about the samples.

Samples show the essense of the problem.

And I think about the problem while taking notes.

What are your future goals and what impact competitive programming has created in your life ?? ：Rajatさん

My goals are not clear, but now I want to be Orange because I want to be a writer of AtCoder!

Competitive programming enriched my life at home and I met a lot of interesting people through the competitive programming.

If i ever start a "COMPETITIVE PROGRAMMING PODCAST" would you like to come as a "GUEST" ??? (You can ignore this question obviously if you want) hahaha：Rajatさん

Of course! But I can't speak English well :D

黄色になるためにこれはやった方がいい！ベスト3：かぽかぽさん

EDPC埋め、典型90埋め、青Diff埋め！

俺の好きなポテチの味！トップ3：かぽかぽさん

堅揚げコショウ味、ピザポテト、のりしお！

美しいと思った問題トップ3：かぽかぽさん

Bowling、1 or 2、Small Multiple！

競技プログラミング　最高の瞬間20：かぽかぽさん

犯罪ACをした時、自分の作った問題が褒められた時、途中の問題を飛ばしてACをした時、色変した時、（略

モチベ管理について：Lilicさん

レートが近い友達を作るのが良いと思います（同じ学校でもTwitterでも）

自分はやる気が出ない日はバチャを開いてメリハリをつけたり、ライバルの解いている問題を解いたりしてやる気を出していました。

1850から2000になる方法を教えてください！：ReiVindicatioさん

自分は水パフォ以下を出さなくなってからレートが上がった気がします。

水Diff、青Diff埋めが効いたかもしれないです。

一緒にバチャやりましょう！

入黄記事で書きたかったのでこのフォームで書いて欲しかったお題：うえすぎさん

聞いて欲しいことは大体聞いてくれた気がします

大喜利がどの程度効果があったか：うえすぎさん

多角的な視点から物事を考える、という力がどちらにも必要なので大いに効果があったと思います。

ミルクコーヒーについて：うえすぎさん

いつもお世話になってます。コンテスト前によく飲んでいます。キャラ作りとかではなく普通に

2022好きなAtCoderの問題ベスト10：うえすぎさん

範囲せま・・・今年出た問題全部好きです

brainf*ck beginner contest 002 の開催日時：うえすぎさん

原案はいくつかあるのでいつでもできます

またwriter集めて近いうちにやりたいですね

需要あるんですか？

橙になれると思いますか？　なれるとしたらいつ頃なれると思いますか?

今は全く入橙の未来が見えないですが、いつかはなれると思ってます

目標は2023年内です（就活時期に橙を名乗りたい）

橙になってwriterをやるのが最大の夢です。

1月27日 追記分

本当に何日考えてもわからない問題はどうしているのか？ 私は典型９０の073 - We Need Both a and bの遷移が本当に何日考えても分からない

ABCなら知識ゲーの可能性があるので解説を見る、ARC/AGC なら（よほど見たくなった時以外は）解説を見ずに何日も考えます。

自分もその問題苦戦しました

自分はAGCの「Reversi」と「Extension」がずっと解けません・・・

黄コーダーになれた理由についての自己分析：mtsさん

パフォーマンスの下限を上げることができたのが大きいと思います。

特に自分はARCは安定していて、ABCで下振れてレートが下がることが多かったので、ABCの問題をたくさん解いて対策をしました。今はABCの方が得意になったと思います。

ABC と ARC でそれぞれ勝つために練習で意識していたこと、工夫していたこと：mtsさん

ABCはあまり強く意識していませんでしたが、実装の練習だと思って解くことが多かったです。

ARCはad-hocな問題が多いですが、次に活かせるようにad-hoc問題なりの典型要素を頑張って見出しながら解いていました。

精進と作問に使っている時間の配分：mtsさん

PCに向かっているときは精進、それ以外でスマホか紙が使えるときは作問という感じです。

青になった頃はよくコンテストを開いていましたが、黄色になりたい気持ちが強くなってからは意図的に精進を重視していました。

アイコン画像のミルクコーヒーは何 ml ですか：mtsさん

500ml です

黄色になって変わったこと：かびぽよさん

一区切りついたので、より作問に力が入ってます。

黄色になったのでこんなことをやってみたい：かびぽよさん

Python の勉強がてら、ABCのC問題くらいまでを埋めたい。

役立った記事やサイトなどはありますか？ 精進方法なども教えて頂けますと幸いです。 おめでとうございます！

ありがとうございます！

自分が精進の軸となったサイトを貼っていきます 

レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 - Qiita

レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【上級編：目指せレッドコーダー！】 - Qiita

競技プログラミングでの典型アルゴリズムとデータ構造 | アルゴリズムロジック

AtCoder の「EDPC」「典型90」もほとんど解きました。

精進はAtCoder Problemsからテキトーに問題を選んで解いたり、やる気が出ないときはバチャをやったりしていました。

自前のライブラリを管理/使用するときはどのようにしていますか

ライブラリはほとんどアルゴリズムロジックというサイトから拝借しています。

あと、毎回貼り付けるのが面倒なので、UnionFind、Combination、素数判定、座標圧縮などのよく使う関数は常に貼り付けておきます。

大学との勉強の両立をどうやってしていますか？：ゾビオさん

情報系の学部なので、競プロと被る内容が多いのと、そもそも授業数が少ないので競プロの時間は十分に確保できてました。

来年以降、研究が本格的に始まるのでどれくらい時間が割けるか分からないですね・・・

おわり

今後も作問や競プロ記事作成やっていきます

次は橙！入橙記事楽しみにしててください

入黄記事は以上になります。ありがとうございました。