今日行われたyukicoder contest 423で生まれて初めてWriterをやりましたのでその感想です。この記事は問題に対するネタバレがありますので、先に解きたい方は記事を見る前に…なにとぞ…なにとぞ…
・前置き
昨年7/7に行われた あさかつプレゼンツ2 では見様見真似でG,HのTesterをやっていましたが、あまり有意義な指摘ができず(真っ当に解いたあと「これmod統一したほうが良くないですか?」と言っただけ)ちょっと悔しい思いをしたため、その時に得た知見を元に(主にpoyonさん由来)何かしたいな~とはうすうす思っていました。
で、募集があったので応募ポチっとな。競技クイズの問題は下手すれば数万問単位で拵えてきたんですが、本当に競プロの作問出題は初めてです。
手元にあった問題案は精々茶diffで、空いている枠が水くらいしか残っていなかったため、応募した後プールで泳いでいる最中(水だけに)に問題案の原型を塑像。作った当初はちょうど水下位くらいのができたな~と思っていましたが、実際はどうだったのでしょうか…?(この記事の下書きをしているのは3月上旬)
・問題の感想
Tester作業も何問か併せて行ったため、そのほかの問題に関する感想も併せて書きます。マイナスな話題は一切ないです。
・A:Longest Infection Sequence
入力例の「A,B,O,W」の珍しさがおもしろ
・B:How many times reached?
基本的な全探索(でいいよね?)。問題文が少し長いですがBらしいなーと思います。
・C:Sword(全体Tester)
かなり基本的なDP。「昇順に適用」の文字が読めるかどうか。ABCでも最近この手の素直なDPは出ないイメージです。
Ti=2のときの効果を2倍だけじゃなくて、0倍、マイナス倍にしたら水diffくらいなのかな~と思いました。
・D:The Early Bird Catches The Worm(全体Tester)
尺取り。Cよりかは明確に難易度が上昇。尺取りがメインと聞けば易しいはずなんですが、工夫がある程度必要なだけにdiff1100程度を予想しています。
・E:Warp zone(Tester)
基本的なダイクストラ。ダイクストラの中身をある程度弄るABC342-Eがdiff1476であることを考えると、1400までには落ち着く予想しましたが…。
(この問題だけちょっと誤字が目立ってしまい…、ぼくの落ち度です。ごめんなさい…)
・F:Sign Creation(Writer)
長いのでのちほど!
・G:Range LIS Query
コンテスト中に問題を考察する予定でしたが、WriterTesterズでの通話が楽しくて全然考察できていません!!
・H:Many Asakatsu (Tester)
グラフの性質を利用した二分探索。要求される技術自体はそこまで複雑ではないのですが、水レート以下の方はがたっと正解率が落ちそうな雰囲気。初提出でACできたときはなんかちょっと嬉しかったです。
作問者の方とあまりにもレート差があったものの、諸事情で人が足りず、少し怯えながら自分が急遽テスターに。しかし当初の不安とは裏腹に、仮の人さんとかなり細やかにやりとりが出来、かなり作業がスムーズに進んで大変気持ちがよかったです(他の作問者の方とのやりとりが出来なかったわけではもちろんないです)。自分がもっと頼られるくらいレートも作問経験も積んでいきたいところ。解説PDFもめっちゃ気合が入っていて、刺激をすごく受けました。
・F
・当初は水下位枠E想定で作成したのですが、こっちの方が難しくね?ってことでFに入れ替え。解法ありきではあるので、面白いかどうかで言われると面白くない寄りだと思います…
・ぼくは夜空を眺めるのが好き。星座は一応クイズでは得意だった方のジャンルで、wikipediaに言及がある星の和名の殆どは覚えたはずです。今はだいぶん忘れましたが…。「朝活」なのに題材が「夜空」ってちょっとお洒落じゃないですか?
・二つの星でも星座と言えるんですか?→主要星ならばこいぬ座が2つです(プロキオンとゴメイサ)。まあ過去には88以外の星座もいっぱいありましたし…
・Dansparce さんmoさんKowerKointさんにテスターに入って頂き、手厚い支援を頂けました!Dansparceさんからは率直な難易度の感触を頂き、moさんには同じpython使いとして解法の議論コメントや実行時間制限に苦しんで頂き(?)、KowerKointさんは文章の体裁の指摘や別解の提示(掲載はしていませんが…)までして頂き、めちゃめちゃ助けになりました。本当に感謝いたしますm(__)m
・kysくんは(東京の某スタジオで)初めて会ってから14年経ちます。長いねえ。次に出題するときはおそらくkomoriさんあたりのお名前を借りることになるかなと(???)
・問題としては、純粋なUnion-Find(diffおよそ800)に、実装とカウントパートを加えて水下位を狙った方針。制約を確認して割と愚直に行ける、という段階を見るという意味ではそこそこ教育的ではないでしょうか?
・問題作り、楽しいですね。今回はほぼ典型の類だと自覚はしておりますが、典型とは言えない問題も作れるようになりたい。また出題の機会がありましたら!(問題案を作ってから…という話ではある)
1位記念パピコ