※社内ブログで2020/8に掲載されたものです。
弟です。今日は有休をいただいています。いやっふぅ。
プロコンをやってると「問題作れるのすげ〜〜〜」というありがたいお言葉をいただくので、今日はどんな風に作問をしてるかをご紹介します。
1. テーマを決める
せっかくFusicの冠をつけてる訳ですから、どうせならFusicっぽい問題にしたい訳です。
例えば、社内サービスとかですね。今回はMieluをテーマとして取り上げることにしましょう。
2. 問題概要をつくる
一番頭を使うアイデアを考える部分です。
サービスをながめながら、「こんな機能があってもおかしくないな〜」って思える機能を考えたり、「ここの実装社員が10万人いたらこまんないかな〜」とかを考えます。とはいえこの段階で実際にコードを書くことはなくて、頭の中でぐるぐるさせるだけなので一番楽で楽しいです。ガチャみたいなものですね。
で、以下のようなアイデアができました。
N個の区間[s_1, t_1], [s_2, t_2] ... [s_N, t_N] と、１〜Xまでの区間を考える。 「各区間が被覆する整数値に１を足す」という処理を区間１〜区間Nまで行ったあとの１〜Xの区間の状態を求めよ。
この時、できたアイデアに対して「知らないと解けない問題じゃないか」というのは厳しくチェックします。
案にUnionFind木とかセグ木とかを要求してないか、二分探索やダイクストラ法なんかを要求してないか、とかですね。
自然な流れでそうしたアルゴリズムを自然に実装できるような場合には、そのまま進めてみることにしてますが、この段階で高度典型やデータ構造ゲーは基本なくなります。
3. 解いて正当性をチェックする
２で考えたアイデアを自分で実際に解いてみます。
正当性が心配な時は複数の解き方で解いてみて、どの方法でも答えが一致するかなどを考えたりします。
今回は２種類の方法で解いてみました。
solve1が愚直な解法、 solve2がより効率のよいアルゴリズムによる解法です。
答え見たくない人はガーっとスクロールしてください。4. 制約を決める
制約は問題の難易度を左右するとても大切なものです。
今回は先ほどの
solve1 だとダメ、 solve2だったら通る、ぐらいの制約にしてみます。・入力は全て整数 ・１≦ N ≦ 100000 ・１≦ X ≦ 100000 ・１≦ s_i ≦ t_i ≦ X
その他の変数についても、矛盾が起こらないよう良い感じに制約を設定します。
難しすぎるなぁ。。。と思ったら、簡単になりすぎない範囲で別の解法を許したりもします。
5. 問題文を考える
1.で作った問題のアイデアを、Fusicっぽい問題文にします。
簡潔に、わかりやすくなるようにがんばります。
MieluはFusic社員の出勤状況がわかるサービスです。 特に「みんなのコアタイム」という機能では、各社員がどの時間帯によく働いているかを知ることができます。 今回はそれにならった「全社のコアタイム」を求めることを考えます。ただし１日を X 等分します。 また等分された区間をそれぞれ時刻１, 時刻2, ... 時刻 X と呼ぶことにします。 さてある日の勤務状況について、出勤した社員数 N、各社員の出勤した時刻 s_i 、退勤した時刻 t_i、が与えられます。これらの情報から「各時刻に何人の社員が働いていたか」を求めてください。 ※ s_i ≦ x ≦ t_i が成立する時、時刻 x に働いていたとみなします。
6. テストケースをつくる
提出されたソースの正当性をチェックするテストケースをつくります。
主に以下を意識して作ります。
- サンプルは簡潔で、問題の意図がよく伝わるものを入れる
- サンプルの後半は少しだけ複雑なケースを入れる
- テストケース前半は小さめの制約にする
- テストケース後半は大きめの制約にする
- 最大ケース（今回だと N = 100000）は必ず入れる
- 他コーナーケースがあれば必ず入れる
面倒ですが、ガーっとテストケース生成機をかきます。
7. HackerRankに登録、もっかい解く
やっと問題ができました！
有志コンテストを開催できる「HackerRank」というサイトに問題を登録し、自分でもっかい解いてみます。
またこの際、一応ダメな解法が落ちるかもチェックします。
これでようやく完成です！
8. 解説を書く
最後に大事な仕事が残っています。そう、解説を書くことですね。
「読んだ人が自然な流れで解法を理解できるか？」「あいまいな表現をしていないか？」を意識して頑張ってかきます。また必要であれば、計算量やアルゴリズムの発展系・一般形についても触れます。
ちなみにPDFにします。
洒落てますね。
9. 完成！
これにて完成です！！！
こういうのを４、５回やって１つにまとめるとFusicプログラミングコンテストが出来上がります。
身につく力
まぁいろいろみにつきますよね。
本当はここを書きたくて書き始めたんですが、燃えつきました。
告知
第三回を10月ぐらいにやりたいなと思ってます（早いですね）
次は許可とって昼にやれたらいいなと思っています。
それでは一足早いお盆休みに入らせてもらいます！
Fusicオープン社内報へ戻る
