notepad.exe

つまり覚え書き

社内のプロコンで作った問題と思ったこと

６月に行われた社内のプロコンで初めて問題作成を行いました。 実際に作った問題と問題を作っている中で考えたことをまとめます。

前提条件

問題の作成をする際の条件はこんな感じでした。

  • コンテスト時間は3時間
  • 問題数は5問
  • 問題のレベル感はAtCoder Beginner Contest程度
  • 全体の得点がばらけるように部分点を多く設定する

部分点については最終的には全部の問題で細かく部分点が取れるようにしました。
ここから問題の概要を順番に説明しながら作成中に考えたことを説明していきます。

A - Convert Gengo

和暦(M, T, S, H, X)が与えられるので西暦に直して出力する問題。
Xは未来の新元号です。

これはいわゆるおまけ問題。
ほとんどの人は問題なく解いてくれますが、プログラミングに慣れていない人だと案外引っかかるようで思ってたより時間のかかる人もいました。この問題では元号ごとに部分点が入るようにしていて、ジャッジ結果から実装ミスの予想もできるような最終的にものすごいおまけの部分点になりました。

B - GCP

GCPの3種類の文字から構成される文字列の中で特定の文字列があれば消していき、最終的な長さを求めてくださいというような問題。(ちなみにGCPは「ぐー」「ちょき」「ぱー」の頭文字)
この問題はとある問題を参考にして難易度を上げました(AtCoderの問題をたくさん解いている人なら心あたりがあるかも?)

この問題は実はあまり作るときに悩まなかった問題。for文で回して部分点をとれるのとstackを使わないと満点をとれない2段階に分けただけでした。 この問題の基本的な考え方が、 f:id:mosmos_21:20180810224821p:plain
このような感じで見つかるまで参照をずらして対象の文字列が見つかったら、 削除 → 文字列を詰める → 参照を一つだけ戻して再度探索みたいなものを想定していました。

ただ純粋にこれを実装してしまうと時間がかかってしまってTLEするはずなのですが、どうやらC#のリストを使うとこのあたりの問題が解決されているようで、本番で部分点の想定解法で満点を取る人が出てしまいました。

作成側としては検証の対象がC、C++、Javaだけなので、他の言語の仕様を知ることができた面白い機会だったと思います。

C - 10+10=23?

ざっくり言うと表記する文字のマッピングも与えられる進数変換をして足し算したものをさらに進数変換する問題。 どうゆうことかと言うと、例えば16進数 → 10進数の表記の変換をすると4e → 78

となりますが、これは16進数を表現する文字が

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F]

と与えられているのでそれを10進数に当てはめて計算することができるからです。 これの文字の順列を、例えば4進数の時に、[0, 1, 2, 3] ではなく [a, b, c, d]で表現されているとすれば、 前者で表現されている312という数値は後者で表現されているdbcと同値ということになります。 この時のN種類の文字列で表現されている数値をN種進数と呼んで、

S(A種進数) + T(B種進数) = ???(C種進数)

という計算をしてもらう問題でした。


解法自体は一般的な進数変換を少し変更するだけで答えを求めることが可能なので実装自体はそこまで難しくないです。これを作っているときに大変だったのが、この定義をいかに正確に問題文に反映させるかでした。 結果としては5問の中で問題文は一番長くなってしまいました。

おそらくそのせいもあって時間内に満点の解法を提出できたのは上位の3名だけでした。 ただ、終わった後に数学科の同期に「ここはどうなんだろうと思ったところが全部問題文にちゃんと定義されていた」と言ってもらえたので個人的には満足でした。

D - Sum of K

問題文は
「A以上かつBより小さい整数の中で、Kの倍数である整数のみを合計した数値を出力してください。」
以上です。

この問題は最初制約を 0 ≦A, B ≦ 3 * 109 にしていたのですがCで検証してみたらまさかの間に合ってしまって 急遽 -3 * 109 ≦A, B ≦ 3 * 109 にしました。そうしたら案の上想定解以外でACする人がいて終わってみてびっくりしました。

この問題の想定解は等差数列の和を求める公式で計算するだけなのですが、 たとえば -100 ~ 200までの和は-100 ~ 100の和が0なので100 ~ 200までの和を求めればいいのでfor文で間に合ってしまうんですね。

検証が甘くなってしまった問題でした。

E - XOOOX

M*Mの盤面でN目ならべをします。i手目で打ったての座標が (x_i, y_i)で与えられるので何手目で決着がついたか求める問題。

この問題だけ割と競プロ感が強い問題になりました(完全に趣味全開で問題を作ったため)。

Mの最大値が105なので配列すらとることができないようにしています。 もちろん部分点は制約がかなり少なく一番小さい部分点ではM = 4固定だったのでfor文で解くことができます。

満点の解法の想定解は同じ色の石が並んでいる部分をUnionFind木で管理してグループごとの大きさを持たせてそれを並んでる数として判定するみたいな感じです。

とはいえ部分点でかなりの点数を取ることが可能なので参加した人はそれを読み取ってもう少し部分点を取りに行ってほしかったなと思いました。

まとめ

問題文の全文と、今回の問題で自分の考えた想定解のソースはこちら GitHub - pgcon6/General

5問作ったまとめとして思ったのが

  • いかに勘違いさせない言葉で問題文を作るか
  • 検証中に問題文、データ、想定解のどこが間違っているのかを探す
  • いかにして点数をばらけさせるか

がかなり難しいということ 1つ目の言葉のチョイスは特にC問題で苦労しました。これは結果としてよかったと言ってもらえたので頑張ったかいがあったと思っています。

2つ目と3つ目は経験を積まないとなかなか難しいのでこれは次回の課題として取り組みます。 特に2つ目は鍛えると問題を解く能力も同時に上がるので一石二鳥でした。 競プロのプレイヤーとしてのスキルもまだまだで質の高い問題を作ることはなかなか難しいですが、 今後の勉強のきっかけとしてはいい機会だったと思います。

次回は11月なのでまた終わったら同じような記事を書きます。