Fusicプログラミングコンテストの問題ができるまで,b,b

執筆

AT274

カテゴリー

Tech

テキスト

投稿日

Jun 1, 2022

※社内ブログで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 に働いていたとみなします。