はむ吉(のんびり)の練習ノート

主にプログラミングについて、思いついたことや、試してみたこと、学んだことを、覚え書きを兼ねてまとめます。

yukicoder No.3032 Unavailability of Inequality Signs コメンタリーもどき(解説除く):April fool contest 2018

競技プログラミング練習サイトyukicoderにおいて,昨年までと同様に,風変わりなコンテストyukicoder April fool contest 2018が4月1日22時より開かれました.その中の一問として,私が作成した問題であるNo.3032 Unavailability of Inequality Signsを出題していただき,多数の方々に取り組んでいただきました.問題の解説自体は当該問題のページに記しましたが,作問の経緯や考えたことなどを,この記事にまとめておきます.

作問のきっかけ:「制限プログラミング」との出会い

私がこの問題を作る最初のきっかけとなったのは,2016年のyukicoder April Contest - yukicoderで出題された,kzyKTさんによるNo.353 ヘイトプラス - yukicoderです.この問題を通じて,プログラム実行時の時間/空間計算量ではなく,ソースコード自体の記述方法に制約を課すという,いわば「制限プログラミング」問題というものをはじめて知るとともに,その面白さにひかれました.そのあまり,いろいろなアプローチでこの問題を解く記事(ネタバレ注意)を書いたほどです.翌年のyukicoder April fool contest (変わり種問題) - yukicoderでも制限プログラミングの問題がいくつか出題され,試行錯誤しつつ楽しみながら解いたのを覚えています.このような背景から,自分も制限プログラミングの問題を作ってみようと考えました.

問題完成に至るまで

私がこの問題を作ったのは2月頃のことでした.かなり気が早かったのですが,その分じっくりと見直しができ,それなりの問題を作れたと思います.

骨子の作成

普段プログラミングで多用している言語機能あるいは関数の使用を制限するという方向性は,当初より決めていました.ただし,そのままだとこれまで出題された問題の劣化コピーになってしまいます.そこで,やや大げさですが,いかにオリジナリティを出し,さらにひねりを加えるかが課題でした.あれこれ考えているうちに作り出したのが,不等号を使わずに大小比較を要求し,しかも出力には不等号を必要とするという,今回の問題でした.

制約について

はじめは  N の上限を下げ,埋め込みを許可する方針でした.また,後半部分の,ソースコードで使えないはずの不等号を出力させるというタスクもありませんでした.しかし,その場合だと★1~★1.5の問題にしかならず,あまり差別化を図れないように思えたので,現行の制約および出力形式にしました.

制限時間について

想定解が  O(N) で,なおかつ N の上限が小さいので,当初は 1 秒としていました.しかし,一部の言語(Scala など)では(おそらく)VM の立ち上げ等に数百ミリ秒の時間がかかることに後になって気づいたので,急遽 2 秒に変更しました.

ジャッジの方法について

本問では出力結果だけではなくソースコードの内容も確認する必要があるため,通常のジャッジは利用できず,自前でジャッジを行うコードを用意する,スペシャルジャッジを使用する必要がありました.スペシャルジャッジの使用は初めてでしたが,上述の過去問を参照し,無事に作成することができました.高速性を重視して,C++でジャッジコードを記述しました.私がC++でのファイル入出力を用いたのはこれが初めてかもしれません.

問題文について

以前発表したNo.406 鴨等間隔の法則 - yukicoderなどでは少々「いちびって」,ストーリーに凝りましたが,問題の趣旨をいたずらに分かりにくくしかねないので,本問ではほどほどにしておきました.問題文がHTMLタグに利用される<や>まみれで,いちいち文字実体参照に置き換えるのが面倒でしたが,自業自得です.

反省点

解説でも触れましたが,問題の性質上やむを得ないとはいえ,そこそこ多用される言語であるPHPによる解法を見いだせませんでした.今回はこれも踏まえたうえで変わり種問題として扱ったためよかったのですが,通常の競技プログラミングの問題を作成する際には,本質的でないところで言語選択の余地を奪わないよう気を付けたいものです.

コンテストの様子をうけて

コンテストが始まるまで,何か重大な誤りを見落としていないかとやや心配でしたが,しばらくして続々と内定もとい AC が出て,ほっとしました.

ただ,問題文の表現として,「いかなる形であれ < や > をソースコードに含めてはならない」という点をうまく説明できていなかったという問題がありました.本問の場合,(1) 出力には < や > を含めるが,だからといってソースコードに < や > という字を記述してはならない,(2) これらの記号は,#include < ... >-> といった形ですら使えない,という 2 点をうまく伝達できず,混乱を与えてしまったようです.問題文を書く難しさを感じました.

問題の冒頭で,言語により正答できないおそれがあると述べたのはよかったのですが, C++ では解答困難というのは誤りであることに,コンテスト中の提出を通じて初めて気づきました.いろいろと C++ による解法を模索したつもりでしたが,基本的なところを見落としていました(詳細は解説に記載).

感想

例年のApril fool contestでは解答者として楽しませていただいてきましたが,今回は出題者としての立場からも参加することができました.このような機会を与えていただいたyukiさんや,参加者の方々に感謝いたします.