【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、素数判定、座標圧縮などのよく使う関数は常に貼り付けておきます。

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

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

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

おわり

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

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

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

2021年の競プロ活動の振り返り

こんにちは。milkcoffeeです。

2021年も残すところあとわずかなので、今年の競プロ活動をかるく振り返ります。

今年はめちゃくちゃ競プロに没頭した一年でした。

2021の成績を振り返る

2021年のレート変動　833 -> 1918 (+1085)

2021の元旦には緑下位でしたが、青上位になりました！

当時の2021年の目標が青になることだったので、思ったより早く達成できて嬉しいです。

ただ、1991まで行ったのに黄色になれなかったのがすごく悔しいですね・・・

ここまで行ったら黄色になって年越ししたかった〜

2021の精進を振り返る

2021年1月時点のAC数はおよそ300だったので、この一年間でおおよそ1000問解いたことになります。そう考えるとやばいですね。

特に頑張ったのは冬休み（2~3月）で、この時にE8さんの記事を見ながら基礎となるアルゴリズムを一通りやりました。レートもその時期が一番伸びてました。

夏休み（8~9月）も結構やってましたね、青Diff や 黄Diff のStreakを続けたりしてました。

2021の作問を振り返る

MojaCoder でたくさんコンテストを開きました！（共同主催してくれた方々ありがとうございました！）

milkcoffee & riano Contest 001

milkcoffee Penalty Contest 001

milkcoffee & riano Contest 002

Prime & Divisor Contest 001

Brainfuck Beginner Contest 001

milkcoffee & riano Contest 003

2021好きなAtCoderの問題ベスト10

具体的な解法が書きませんが、一応ネタバレ注意！

１位：ARC121-D 1 or 2

自分が今まで解説をみた問題の中でダントツで発想がえぐいと思います。天才

２位：ABC191-C Digital Graffiti

この問題に触発されて作問を始めました！ABCだけどAd-hocで面白いと思います。

３位：ARC120-D Bracket Score 2

本番で解けず、解説みた後の悔しさが忘れられません。

４位：ARC114-A Not Coprime

解法が見えづらい問題で好きでした。

５位：ARC128-C Max Dot

言われてみれば・・・となる面白い問題

以下、６〜１０位

ARC112-D Skate

ARC117-C Tricolor Pyramid

ARC120-B Uniformly Distributed

ABC195-F Coprime Present

ARC128-A Gold and Silver

その他

2021年になって競プロ用にTwitterを始めて、いろんな競プロerと知り合えました！

特にスペースで仲良くしてくださった皆さんありがとうございました！

来年の抱負

全部達成します！！

• AtCoder Rating 2200以上
• AtCoder Ranking 学内3位以内
• AtCoder AC数 2000以上
• 最高パフォーマンス 2800以上

2021お疲れ様でした

来年も競プロ頑張ります！

2022年もよろしくお願いします！

それではよいお年を

【競プロ作問】問題の原案作成のアプローチ

はじめに

この記事は競プロ Advent Calendar 2021 の15日目の記事として投稿したものです。

こんにちは、milkcoffeeです。

私はよく自作問題で競技プログラミングのコンテストを開いたりしていて、このブログでもよく【コンテスト開催記】を書いています。

問題をいくつか作ってきて、自分なりの作問のアプローチについて列挙したくなったので記事を書いてみました。

今回の記事では、作問作業の行程の中でも「問題の原案を考える」部分に焦点を当てていきます。

問題から考える

初めて作問をするならこのやり方がオススメです。

一番問題を量産しやすい方法だと思います。

問題設定

自分が良くやる方法として、「問題設定」と「求める内容」に分けるというのがあります。

問題設定はおおよそ「何が出てくるか」と「何をするか」で決まります。

【何が出てくるか の例】

• 数列
• グラフ
• 二次元座標
• 二次元グリッド
• 数式
• 文字列

【何をするか の例】

• 要素に数字を加算する
• 要素を選んでいく
• 要素を入れ替える
• (グラフや座標上の点を)移動する

「何をするか」というのは、問題文でいうところの「操作」にあたります。

思いつく操作の例が多いほど、作問がしやすくなります。

(そもそも操作が存在しない問題もあります。)

ABCのC問題くらいをいっぱい解くと引き出しが増えると思います。

実際に問題をテキトーに考えてみましょう。

N個の正整数からなる数列Aがあります。(何が出てくるか)

この数列に対して、「要素を1つ選び、1を加算する」という操作をK回まで行います。(何をするか)

問題文っぽくなりました。

問い

問題設定ができたら、何を求めるかを決めます。

問題文の最後の「問い」ですね。

【何を求めるか の例】

• (和・積などを)計算する
• 最大値・最小値
• 最適解(最短経路、最小操作回数など)
• 場合の数、何通りあるか
• Yes/No 判定
• 期待値
• 条件を満たすもの列挙・構築

さっき考えた問題設定に合わせるとしたら

操作後の数列Aの最大値をXとすると、Xは最大でいくつになりますか。

操作後の数列Aとして考えられるのは何通りですか。

のような文が考えられます。

問題設定と何を求めるかを組み合わせることで、(とりあえず)原案ができます。

ここで、組み合わせ方によって大量の原案を作ることが出来ると思い、以下のような表を作成しました。

名付けて「100マス作問」！！！

100マスではないですが、問題設定×求める内容の掛け算で、作問の土台を大量に作ることが出来ます。

ただ、すべてのマスを埋めることができるわけではありません。

解けない、そもそも問題として成り立たないなどの組み合わせもあるので、そこはうまいことチューニングする必要があります。

解法から考える

使用するアルゴリズム・データ構造や、答えの考え方から問題を組み立てるやり方です。

ただし、このやり方で問題を作ると解法が分かりやすい問題になってしまうことが多いです。ある程度難易度を高くしたい場合は解法をうまく隠す工夫が必要です。

使う解法を考える

まずは、問題の答えの本筋となるものを決めます。

【使う解法の例】

（知識・アルゴリズム系）

• 高速な素因数分解
• 二分探索，bit全探索，順列全探索
• DFS, BFS, その他グラフ理論
• DP(動的計画法)
• 組み合わせ
• データ構造(priorityキュー，BIT，セグ木)

（考察系）

• 要素をソートする
• 累積和を取って考える
• 主客転倒
• ポテンシャルを考える
• 答えを決め打つ
• 鳩の巣原理を利用する

解法に合う問題設定を作る

答えに必要な解法が決まったら、それを使うように問題設定を考えます。

しかし、狙った解法で解けるような問題を意図的に作るのはかなり難しいので、それを使うような既存の問題を探して参考にするのがいちばん手っ取り早いです。

AtCoder Tags のカテゴリを見れば、AtCoder の過去問を解法から絞って調べることができます。

参考にする問題が1つだとその問題に似すぎてしまうことがあるので、できれば複数の問題を見るべきです。

解法を隠す

解法から作問をすると、解法が分かりやすい問題になってしまう可能性があります。

例えば、以下のような場合は解法が推測されやすいので気をつけましょう。

【解法がバレやすい問題の例】

• 「お決まり文句」を使っている

例えば「最大値を最小化してください」は二分探索のお決まり文句なので、想定解が二分探索だとバレやすいです。逆に、この文言があれば二分探索に誘導できるので、ミスリードを狙えます。

• 制約が特殊

例えば「1≦N≦16」という制約はbit全探索やbitDP であると気づかれやすいです。

• サンプルが分かりやすい

例えば、想定解が「素数ならばYes、それ以外ならばNo」であるとき、サンプルに素数のものが多いとエスパーされやすいです。

解法を組み合わせる

一つの問題で使用するアルゴリズムなどが複数あることは珍しくありません。

いくつか組み合わせた方が解法をうまく隠すことができます。

【組み合わせやすい例】

• 探索系(二分探索、bit全探索、順列全探索)

　　特に二分探索は応用が利きやすく、組み合わせやすいです。

• 素数、約数系

　　素因数分解してから or 約数列挙をしてからもう一つ考察をして解く、という問題は多いです。

• DP

　　DPを使う問題はABCに山ほど出ているので参考になると思います。

それ以外から考える

問題の本質以外のところから先に考えて、問題に発展させていくやり方です。

ad-hocな問題など、面白い問題が生まれる可能性が高いです。

問題文テーマから考える

以下は問題文に出てくる物と、そこからどう問題に発展させていくかの例です。

• すごろく

　　サイコロを振ってマスを進める・・・期待値問題など

• チョコレート

　　チョコレートのマスをグリッドと考える・・・最適に切り分ける問題など

• スライム

　　くっつけると合体して一つになる・・・操作系の問題など

他の物：調味料、乗り物、ボードゲーム、お金、・・・

その他

問題名から考える、制約から考える、コンテストの構成から考えるなど...

詳しくは以下の「具体的な作問例」のところを見てください。

具体的な作問例

自分が出題したことのある問題について、どのようなアプローチで原案を考えたのかをいくつか紹介します。

(スプレッドシートに今まで公開してきた自作問題のリストをまとめています。)

milkcoffee 作問リスト

問題から考えた例

• RGB walking (二次元グリッド & 隣り合うマスに移動 & Yes/No判定)

• Math MASU (二次元グリッド & 数字書き込み & 構築)

• XOR Operation (数列 & XOR操作 & 最大化)

• 3 perf Number (数 & オリジナルの設定 & Yes/No判定)

解法から考えた例

• Making Tree (UnionFind)

• Prime Stairs (順列全探索 & 素数判定)

• Pairwise Coprime Segments (鳩ノ巣原理 & 素因数分解)

• Polygon Locus (二分探索 & 図形に関する考察)

• Long Digits Number (倍数判定の応用)

それ以外から考えた例

• Elevator (出てくる物：エレベーター)

• RGB Slimes (出てくる物：スライム)

• MARU Game (問題名、丸亀うどんを食べながら考えました)

• Rich Primer (制約、変わった制約の問題を作りたかった)

• Under M (コンテスト構成、ペナルティコンテストのための引っ掛け問題)

さいごに

この記事にあるのが自分の作問のアプローチの全部だと思います。

作問は、問題を解くのとは違った面白さがあります。

特に、コンテストを開催して他の人が自分の問題の感想を言ってくださったり、自分の問題で苦戦してくださるのはかなりの快感です。

問題が思いつかない、作ったことが無いという人も是非1つ作ってみてください！

この記事を見て、作問を始める方が一人でもいてくれたら嬉しいです。

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