秋分コンテストを開催しました！
スタッフ：japlj,kagamiz,snuke,tozangezan
あの伝説のジャッジシステムKCSが復活し、またこうして新たなお誕生日コンテストが開催されたことを喜ばしく思います（？）
ただ復活しただけでなく新たな進化を遂げ、自由度がさらに高まったKCSでwriter陣は大暴れをいたしましたが、びっくりしていただけたでしょうか？
その上で、楽しんでいただけた問題が１つでもあったならば幸いです。
自作問題解説
F - The Empty
過去のお誕生日コンテストの定番シリーズで、どこかに隠されたキーワードを探すという問題です。
例えば、問題ページのhtmlのコメントとか、問題ページに限らずトップページのどこかとか、隠し場所は色々考えられます。
ただ、ほとんどの隠し場所はすでにHackerRank時代にやり尽くしているので、今回はKCSにしかない場所に隠すことにしました。
というわけで、通知一覧をご覧ください。
ちなみに、https://kcs.miz-miz.biz/static/2000/the-empty.html にURLをエスパーしてたどり着くとクエストキーが得られます。（４通りの表記ゆれをカバーしてます）
さすがに無理だろうと思っていましたが、案の定たどり着いた人は０でした。
KCSは画像だけでなくhtmlもアップロードできるんですねぇ〜〜
G - くそなぞなぞ
想定解
- 秋分（それはそう）
- 秋分の日（分数として読むだけ）
- 重文（ちなみに例文はwikipediaを参照しました。「しげふみ（小惑星）」の項にちょっと笑った）
- 大田区（オータム）
- 鉄アレイ（鉄array）（ちなみに漢字で「鉄唖鈴」とも書くらしい）
- メンブレン（面がブレないので）
- コアタイム（そのまま読む）
- スタッフオーバー苦労（「ふ」と「く」をswap）
２番で「一日千秋」を連想して「千分の一」と答えるとクエストキーが得られます。
１人くらいは通じ合える人がいるかな〜と思っていたら、１人いて嬉しい。
L - Sqrt
正は10^40なので、100000000000000000000(10^20)が答えです。
「垓」という答えを見て「たしかに」となりました。たしかに。
O - 沖縄
ja.wikipedia.org
の図をご覧ください。
正規表現を使うと楽です。
ただし、C++でやる場合は気をつけて下さい。
https://kcs.miz-miz.biz/contest/2000/code/103529
このコードどこがおかしいかわかりますか？
実は "ー?" の部分が駄目で、"ー" はマルチバイト文字なのでその最後の1バイト分にしか '?' がかからなくてすごいことになるっぽいです。
（"(ー)?" ならok）
ここにも実はクエストがあって、ソースを見て画像のURLを見ると、この画像はかぼすであることがわかります。
いらすとやでシークワーサーの画像を探してきて、そのファイル名からURLをエスパーするとクエストキーが得られます。
ちなみに似たシリーズとしてすだちの画像もいらすとやにあるらしく、こっちにアクセスするとさらにクエストキー入手です。
tozangezan考案で、最初ちゃんとシークワーサーの画像を問題文に貼ってたのにも関わらずなぜかすだちの画像のURLにアクセスしようとしたらしい（当然そんなものは置いてなかった）
（それにしても "fruit_shi-kuwa-sa_shikuwasa.png" って言う命名なんなんだ？）
ちなみにこの図はQuizKnockで知ったんだっけな。コンテスト数日前にtwitterでも流れてて「あっ...」ってなったけどまぁいいやとなった。
Y - A/B Problem
ジャッジコードでソースコードを取得できる機能がKCSに生えたということで、お誕生日コンテスト用問題ストックにあったのを放出。
'/' を使わず割り算をする問題です。
pythonやc++で "div" を使うという解法もありますが、"div" を含む場合は50点にしました。
それ以外にもいくらでもやりようはあります。
例えばO(log A)でアルゴリズムの力に頼って足し算と掛け算だけでやるのもありです。
他にもpythonのevalを使って print(eval(input().replace(' ',chr(47)*2))) とやるのもありですね。
#define waru di##v とかもありですね。
Z - Chess
個人的にチェスが結構好きなので出題してみました。
海外では一番メジャーなボードゲームなだけあって、チェスネタはプロコンでもたまに出題されますね。
- 右上のルークとナイトが入れ替わっています 棋譜
- キャスリングを使います。チェックがかかっているということは今は黒の手番なはずなのでparityをずらす必要があるんですが、ルークかクイーンを２マス動かせばずらせます。 棋譜
- ダブルチェックがかかっているということは最後の手はディスカバードアタックなんですが、アンパッサンを使うのが唯一の手段です。 棋譜
- デザイン重視。ただ、ポーンをすれ違わせるのは駒を犠牲にしなければ出来ないので、うまくやらないと供物(?)が足りないので頑張って下さい。 棋譜
- なんかすごいことになってますがプロモーションを使えばクイーンを量産できます。あとは最終盤面から１手前の状況を推察することを繰り返せば目標は見えてくると思います。黒のビショップ(白マス)かクイーンが必要になって「あれ？足りなくない？」となるかもしれませんが、こちらもプロモーションを使えば作れますね。 棋譜
- トリプルチェックは普通のチェスでは不可能です。そこでバリアントルールに手を出します。この問題はAtomic Chess（駒を取るとその８近傍のポーン以外の駒が吹き飛ぶ）を使うとかなり短い手数で実現できます。 棋譜 （最短手数だと思っているんですが、これより早くトリプルチェックを実現する方法があったら教えて下さい）
- こちらはキングがなくてもうめちゃくちゃです。キングがなくても良いのはAntichess（駒を全部取られたら勝ち、ただし駒を取れるときは取らないといけない）くらいです。ただし、Antichessで提出しようとすると「NGワード:anti」と言われます（「否定的な単語は使わないようにして下さい」と問題文に書いてありますね？）そこでジャッジコードを見るとpython-chessを使っているので、ドキュメントを読んでみるとAntichessに似たルールのSuisideとGiveawayが使える事がわかるのでこれを使いますが"Suiside"は当然NGワードなのでgiveawayを使うとACです。 棋譜 （lichessにはAntichessしかないのでAntichessで代用）（ドキュメントを読まなくても、Antichessの別名を普通に検索して片っ端から試してみるというのも手ですね）
ちなみに初期盤面がジャッジコード内でしっかりチェックされていることを考えると他のバリアントはCrazyhouseしか使えなさそうですが、これもなんかFENに持ち駒の情報が付いてしまって使えません。
別解
python-chessの実装を読んだりすると「パス」に相当する "z0" (null move) というのが使えるようで、これは自分のキングにチェックかかってようが可能みたいで、これを使うと大体なんでもやりたい放題になります。
全く予想外でしたね... これは参加者の方が一枚上手でした。
別解２
実は６もAntichessで頑張れば解けるみたいです。（ただしgiveawayで提出する必要はある）
これを見つけて感動したので、急遽クエストキーを追加しました。（その後 z0 解にクエストキーが取られてびっくりした）
[ - Cheat
意外と気づかれないもんですねぇ。
yesと答えた後に得点を書き換えようとしてみて下さい。
びっくりしてもらえましたか？
仕組み（白文字）：KCSはVERDICTにhtmlコードを仕込めるのでそこにjsをガッツリ書きました
ちなみに、変な出力をすると "Answer Yes or No." と言われるので、"Yes or No" とそのまま答えるとクエストキー "kuso_mitaina_parse_wo_suruna" が得られます。
] - 数列クイズ
OEISして終わり！かと思いきや、OEISが間違っています。しかもかなりガバ。
この数列は、へやわけというパズルで中央の正方形の部屋に最大いくつ黒マスが入れられるか、というやつです。
解法としては
- 適当に±1してみる（一番楽）
- 「へやわけ 黒マス 最大」みたいな感じでググってここなりここにたどり着く
- パズル盤面作成ツールで右クリックして数字の最大値を見る。（こんな機能ついてたんですね(驚) さすがに空中の長方形部屋限定ですが）
historyのところに修正提案がちゃんとあるらしい（情報提供：amylaseさん）
ちなみに似たのがもう一個あって、そっちもはちゃめちゃ。
_ - Echo
競プロ。
とりあえず提出してみると、-135点が来ます。
よく見ると、testsetが大量に設定されており、その中には負の配点のものもあります。
つまり、正解するテストケースを上手く選ぶ最適化問題というわけです。
構造をよく見ると、
- set_???：２〜５個のケースからなる、正の配点
- penalty_??：１個のケースからなる、負の配点
という構造になっています。
この最大化はmincutに帰着できます。
詳細に解説はしませんが、この問題などが参考になるのではないでしょうか？
ちなみに、ちゃんとテストセットの構造を見て計算しないとなかなか正の点すら得られません。
なんとなく得点効率が良さそうなやつだけ選ぶ貪欲で100点ちょいが来ます。
マラソンでも満点行けるんかな？と思ってましたがちゃんと焼き鈍したりしないと意外に満点はきついっぽい？（199で止まる人がちらほら）
ちなみに最小化は多分多項式とかでは解けないと思いますが、IP（整数計画問題）に落としてソルバを使えば爆速で答えが求まります。（-1644点 (笑)）
-1644点を取った人はclimpetさんただ一人でした。（クエストを設定しようと思ってましたが、キーワードを与える方法がなくて断念しました）
ちなみに最適解は２通りだけみたいです。（14,24,42をflip）
ちなみにHackerRank恒例の負の得点はKCSは対応していません。（順位計算時に0とのmaxが取られる）
というかHackerRankが異常で、なんで「負の得点が取れて、一回取ってしまうと撤回不可能」みたいなことができるかというと、「問題の点数は0~1の実数で出して、順位計算時にそのmaxを取ったものに配点の値を掛ける」というシステムだから（多分）です。
