つちのこの日記

競プロと音ゲーがメインです。

yukicoder contest 276 で Writer をやった話

前書き

yukicoder contest 276で単独Writerをやりました、nok0です。セットを投稿するのは初めてでしたが、楽しんで頂けていれば嬉しいです!

今日単独コンテストを開催できたのは、yukicoder及びyukiさん、testerを心良く引き受けてくださった皆さん、全問の難易度等をチェックしてくれたくまー(@kuma_program)くんのおかげです、本当にありがとうございます。

自己紹介と諸々

最近AtCoderで黄色になりました。競プロ歴はまだ1年もないのですが、折角競プロというコンテンツに割とどっぷり浸かってしまったので、創作もやりたくなり、セットを出させていただきました!これらの問題を作ったのは多分青の頃なので、レートにあまり関係なく、作問は楽しめると思います(多分)。

 問題ごとの解説及び講評(注:問題のネタバレを大いに含みます)

A.OR XOR

tester:zkou(@meander_uts1)くん

First AC:hitonanodeさん(01:44) (以下、FAの時間は(分:秒)で表記します。)

一問目なので、易しい考察で解けること、及びに典型要素が学べることを重視してこの問題を置きました。bit演算を扱う問題はbit毎に着目すると良いことが多いです。結局xorが0なことから、この問題は

Nの立っているbitそれぞれについてをA,B,Cのいずれか2つに割り振る。ただしA,B,Cが全て正という条件を満たすために、A,B,C全てに一つ以上bitを割り振らなくてはいけない。

という問題に言い換えられます。そうすると、構築可能な条件もわかりやすかったのではないでしょうか?

解説にも書きましたが、Nの一番下の立っているbitを N & (-N) で取り出せるということを使うと実装が簡潔です。余談ですが、初めて私がこのテクニックを知ったのはsnukeさんの解説放送(確かBITを実装する回)だったはずで、めちゃくちゃ感動した記憶があります。

講評:いい感じに1問目としての役割を果たしてくれました。思ってたよりWA率が高かったですが、多くの皆さんが解いてくれたようでよかったです。

B.Random Array Score

tester:zkou(@meander_uts1)くん

First AC:sugarrrさん(02:27)

数学問兼ギャグ問枠です。

最初は各要素がi回目に選ばれた時の、総和の増加分の期待値を求めて、それを足し合わせることで答えを求めようとしてましたが(それでも普通にできます)、よく考えると各操作で期待値が2倍になることがわかります。 操作が少し難しそうに見えて答えがすごいシンプルに表されるのが面白いと思って出題しました。

ちなみに、問題文中の期待値が有理数で表せるというところはひっかけで、単純に整数で表すことができます。

講評:難易度自体は割と予想通りのものになりました。ただ、数学要素が強い問題だったので、寒色コーダーの方でも苦戦する方も一定数いらっしゃったようです。

C.Sum of Inversions

tester:NOYA(@NOYA08096071)さん

First AC:tatyamさん(10:23)

簡単な典型枠です。真ん中に着目するといいことがある場合が多いってことだったり、転倒数は座圧してBITに載せることで計算できるといったことだったりは、高難易度だと当然のように要求される典型事項なので、もし知らなかった場合はこの問題を通して学んでいただければ嬉しいです。

講評:どちらかと言えば考察力よりも実装力、基礎的なデータ構造の使い方を問うつもりの問題でした。実装が重めでしたがかなり解かれていて、みなさんの競プロ力の高さを感じました。

D.Strange Graph Shortest Path

tester:zkou(@meander_uts1)くん

First AC:beetさん(02:21)

典型枠2(このセット、典型が多い気がしてきました)、コストがintに収まりきらない最小費用流のverifyにお使いください。解法ではなく設定から作ったのですが、よく見ると蟻本に乗っていました。蟻本は本当に情報の密度が濃いので、この問題が解けなかった方は今一度読み返すといいかもしれません。

もともと想定はdijkstraしてから経路復元し辺の長さを変更し、再度dijkstraだったのですが、冷静になると大嘘でした(これを落とすためのケースがkiller-01で、k-th-shortest-pathをk = 1からある程度のkまで回して最短になったものを採用するコードを落とすためのケースがkiller-02です)。killer-02はtesterさんに考えてもらったので、感謝です。

ところでこの問題、c_i > d_i でも解けるんでしょうか?何かご存知の方いれば教えてくださると嬉しいです。

講評:中度典型枠でした。知っている方は爆速で通した(beetさんは早すぎて本当にびっくりました)一方、知らなかったり思いつかずDijkstraの嘘解法に走ってしまい、ペナを量産している方も見受けられました。概ね想定通りの難易度でした。

E.Random Tree Score

tester:まつかわ(@tpyneriver)さん

First AC:hos.lyricさん(07:43)

グラフ枠かつ冪級数を用いた数え上げ枠。次数の積という条件を扱いやすくするために、次数を固定して考えてみると解説の式が実験なりなんなりで出てくるはずです。(Cayleyの公式をこの補題から証明したことがある人なら秒だったかもしれません。)そこにさえ辿り着けば、単純な冪級数の累乗で答えが表示できます。最初は Ο(NlogN) 想定でしたが、非本質で落とすのも違う気がするのと、logの区別は難しいので、Ο(Nlog^2N)でも余裕で通る制約にしました。 

まつかわさんのtester解は、全然違うことやってます、すごいです。めちゃくちゃいい感じのpdf解説を書いていただいたので、そちらも合わせてご覧ください。

講評:やや難しめの数え上げ問題でした。割と非想定で通されている気がするので、コードをみて勉強した後に、解説及びここのブログに追記します。難易度は想定よりやや易しめだったでしょうか。

F.Inconvenient Kingdom

tester:hamamu(@hamamu_kyopro)さん

First AC:maroon_kuriさん(16:26)

ボス問枠、行列木定理を用いた数え上げを線形代数で高速化する問題。もともとはもっと簡単な問題でしたが、hamamuさんからの数々の助言のおかげでボス枠になりました。hamamuさんには問題文の日本語直してもらったりテストケースについて助言を頂いたり愚直解をチェックしていただいたり、、本当に頭が上がりません、めちゃくちゃお世話になりました。

この問題は、行列木定理に感動して作りました。全域木の個数が多項式時間で数え上げられるの、本当にすごくないですか?? 高速化の方法も割とシンプルでかなりお気に入りです。連結成分が2個以上の場合はちょっと場合分けがめんどいのですが、そこは頑張りましょう。

講評:思ってた以上に通されました。赤コーダーだったり本当に強い方々との力の差を痛感しました。hitonanodeさんの解が5msで、本当に脳内が???です、どうやってるんでしょう?

問題の準備にあたって

これ、めちゃくちゃ大変でした。そもそも作問って

原案の準備→解説の準備→問題文の準備→テストケースの準備→確認

って感じでなかなかやることが多いです。特に大変なのが問題文の準備で、わかりやすい日本語書くのって、めちゃくちゃむずいんですよね。長い文章をまとめあげる自信がなかったので、今回のセットは極力ストーリーをカットしました。

テストケースの準備はめんどくさいんですが、今回はRimeを使うことでめちゃくちゃ楽になりました。詳しくはbeetさんのブログをご覧ください。(とてもわかりやすくまとまっています。

後書き

作問はなかなか大変ですが、めちゃくちゃ楽しいので、是非皆さんもやりましょう!ちょっと前に作問でかなりやらかしてしまったのですが(本当にごめんなさい。。)、今日は無事に終わることができて安心しました!(しかもclar0を達成しました!!)本当にありがとうございました!

 

bit