writerデビューをしたよ
11/23に令和NF恒例の11月祭プログラミングコンテスト2019でwriterデビューしたよ
writerのすることとか全然知らなくて知見がいっぱいあったのと、最近ブログ書いてないな〜と思ってたから色々感じたこととか書く
作問が何するか分からない人がほえ〜んへむへむ言う記事にしようと思ったけど多分そんな大したことは書けない
解法もついでに書くのでまだ問題見てない人は先に挑戦してきて
気楽な時期
きっかけ
そういやNFの日にコンテスト開きたいなと思ってたけど作問してねぇ
— drogskol (@cureskol) November 5, 2019
しますか
— やむなく (@yamerarenaku) November 5, 2019
軽い気持ちで呟いたらwriter経験のあるやむなくに拾われたのでやるかーとなった
この時はwriterのすることの8割は問題案を考えることだと思っていて気楽に考えていた
問題案作成
A（回文ゲーム）
回文を使った問題を出したくなったので授業中に考えたら一瞬で生えた
真ん中あたりに注目すると何文字でも取れるのでただのNim（知らない人は蟻本見て）
回文の特性を用いたギャグとして結構クオリティ高くない？個人的にお気に入り
B（根付き木のやつ）
やむなくから送られてきた問題
簡単過ぎるので一瞬で答える
一瞬で反例が返ってくる
根付き木は部分根付き木で解けることが多いので考えて解けた
俺のは下からだけどやむなくは上からだった
多分他にもいろんな解き方があるはず
割と自由度の高い問題
C（じゃんけん大会）
元々AtCoderじゃんけんのつもりで問題案を考えた
全然解けなくて、普通のじゃんけんでも解けない気がしたのでやむなくに投げたら一瞬で解法が返ってきた
セグ木使わなくても累積和とimosで解けるので知識的には緑くらいで解けて、結構教育的な問題に見えてる
D（鍋のやつ）
やむなくから送られてきた問題その2
制約がDPって書いてあってソートの匂いもするのでやるだけの一番典型問題
2人とも最初はxで二分探索をしてからDPすると思ってたけど途中でいらない事が発覚
温度の三角形の両端にAが小さい方から入れていくのが最適。dp[i]を左をi時間まで使う時の右側を使う時間の最小値として持つ。N個目を最後に真ん中に入れてあげる。
最初dp[i][j]を左からi時間右からj時間使う時、みたいなTLE解をやりがちなんだけど、そうするとdpをboolで持つことになってかなり勿体ない
基本的にdpをboolで持とうとしてる時は情報を一個intで持てないか考えるべき
ちなみに実装はdp[A][B]:A個目まで入れて左からB時間まで使う感じでいいんだけど、結構メモリを使う。でも完全に配列を使い回す一次元dpだとちょっと書くのが大変。で、今回は大丈夫なんだけど、そういう問題でもしメモリが溢れるような制約の時に使えるテクニックがあって、dp[i][j]を埋めるときに参照するのはdp[i-1][*]だけなので、
dp[A&1][B]=dp[(A&1)^1][*]
みたいな遷移の実装にすると、一次元目の確保が2でよくなるので1次元dpと同じくらいのメモリしか使わなくて済む
E（大工のやつ）
問題案は9月くらいにふと浮かんだ（設定はただの無向グラフ上のゲームだった）
解けそうにないから人に投げて、話し合ってたら解法が生えてきた
1-nでいつでも終わらせられることに注目するとi*jが2n以上の辺を選ぶ利点がないので、nを繋ぐのに使われるのは1-nしかない。結局1-n以外でi*jが2n未満のやつを小さい順に（1-nで勝てるタイミングが来るまで）やるだけで、これは調和級数でnlogn個しかないので全部列挙してからsortしてあげても十分間に合う（もう少し計算量を落とすやり方もある）
入力が数字1つだから天才にO(1)とか見つけられたら悲しくなっちゃうなぁと思ってた
俺は凡人なので規則性は全然わからなくて、例えばN=9242~10000の中で答えがSecondなのはN=9928,9932の二つしかなかったりするし、 偶奇と答えが一致する長さ100以上の区間も多くて、かと思えば完全にまばらな区間もあった
天才向けの問題にも見えるしやること一つなので自明の問題にも見えて扱いに困った
やむなくはそこそこ悩んでたので600くらいはあるのかも？くらいの気持ちだった
X
簡単枠が欲しいねって言ってやむなくが生やした300点
割と簡単で面白いのでいいやんけ！と思っていた
やむなくが左下から構築は嘘って気づいて消えていった幻の問題
どうやって解けばいいんだろうね
頑張る時期
rime
テストケース生成にrimeってのを使うって聞いたことがあったので人に使い方を聞く
pythonをインストールするところから始まって結構時間かかった
言われたことをかたっぱしからコピペしてPCに貼り付けると単純なテストケース生成は出来たけど何をやっているかしっかり理解出来ていなくて、トーク履歴を遡りながら一個一個調べる必要があるなぁとなった
ターミナルのコマンドを g++ ./ cd ls くらいしか知らないとコピペする言葉の意味が全然分からないんだよね
初めて自分のエディタでファイルを開けるようになった（今までどうしてたんだろう）
GitHub
やむなくからGitHubを使うと言われてリンクとか送られてきた
ブラウザ上にコードを直書きすると相手にも勝手に共有されて便利!くらいの機能を想定していたんだけど、実は思った以上に出来ることが多そうなことに気がつき怖くなる
初心者でもわかるGitHubの使い方！みたいなブログをいくつか読み漁ったんだけど侍になっても塾に通ってもエンジニアになっても何もわからない
仕方がないのでやむなくを大学に召喚してGitHubの使い方とかやることとか全部習う。Heno Worldのチーム練とかKCPCが偶然なくなったおかげもあってなんとか一通り習うことが出来た
とりあえずGitHub Desktopってのを使うと結構楽に出来た（比較対象がないのでどれくらい便利なのか知らんけど）のでオススメ
実際にやったこと
問題作成
問題案考えたり細かい制約考えたりする
制約は言語ごとの実行速度の差を考えながら最適な制約を...みたいなことは俺は特にせずやむなくに言われた通りの数字を打ち込んだ
問題文
問題文を書く
誤読が起きたりしないようになるべく解釈が一意のものを作る必要がある
サンプルに対しての説明文も書く
小学生か？ってくらいの酷い文をGitHubに投げるとやむなくが完璧な文にしてくれる
Latexとかで使う？なんか数字を$で囲ったりする魔法とかも全部やむなくがやってくれた
申し訳なくなって俺もやむなくの書いた文を校正しようとしたけど直すところ見つからなかった
想定解
想定解を書く
これと後述の入力ケース生成コードを書くと入力ケースと出力ケースが勝手に出来上がるらしい
何も分かっていないけどとにかく言われたファイルに書く
ここはいつも問題を解くのと同じ感じで書けばいいので楽
いざ書いて見ると思ったより実装が軽かったり重かったりする事に気づく
愚直解
Nが大きいとTLEするような愚直な解法を書く
すると勝手に想定解と愚直解両方に入力ケースを試してくれてNが小さい時に両者の答えが一致するかを見てくれる...のかなぁ？
何も分かっていないけどとにかく書く。こいつブログ書いてるくせに何も分かっていないな
ここで大工の問題愚直解書けなくない？ってことに気がつく
実験できないから手のつけ方わからなくて辛い人には辛そうだなぁとここで初めて思う
回文の方も愚直解書けなくて、結局書いたのはじゃんけんのやつだけ
流石に回文も大工も想定解に嘘はないと思ってたけどちょっと怖くなった
相手の問題の解
相手が作成した問題の解法を書く
これで一応愚直解が書けない問題も解法コードが2つは出来るのでちょっとだけ安心
ただ2人が嘘解法共有していたら結局気づけないので愚直解の方が欲しい気がする
鍋の問題の解法書いてテストケースもきちんと確認したらやむなくが俺の解法だけ落ちるコーナーケースを作ってきやがった（dp配列のサイズが5000じゃなくて7500くらい取る必要があって、完全に俺が悪い）
鍋の問題でのほほんと解くとxを小数にしたくなるのに気づいたので非負整数なのを強調することにしたりとか、相手の書いた問題文に対しての指摘が出せたりした
ジェネレーター
テストケースを生成するコードを書く
C++にファイルを生成するって関数があるのを知って感動する
乱数関数とファイル生成関数で終わりかと思ったけどそんなことはなくて、Nが大きいケースを多めに作ったり区間幅が広いのを多くしたケースを作ったりと結構狙い撃ちするケースを作るようなコードを書いた
乱数関数はa以上b以下の数字を返すって感じなので、bをすごく小さくして見たりaをすごく大きくして見たりして偏りのあるケースを作ったりした
あとは例えばじゃんけんだとh[i]は0~2なので、0~3の乱数を作ってからmod3をしてやると0が半分くらいのケースを簡単に作れたりする
h[i]が全部0のケース作ったら俺の書いた想定解がWAを吐いてキレた（答えがintを超えるのを考えてなかった）。#define int long longを書いて事なきを得たがやむなくには「うわぁ」って言われた。
ヴァリデーター
validatorなるものを書く
これはお互いに相手の問題に対して書くもので、相手の作ったテストケースがあっているかを確かめるもの
これ存在知らなくてほえ〜ってなったよね
スペースや改行が入っているか、制約に違反した数字が入ってないかなどを見る
int型を読み取りながらa以上b以下かを判定するreadInt
spaceを読み取るreadSpaceと改行を読み取るreadEolnを使って入力を一単位ごとに読み取る
ensurefは条件式がfalseだったら指定の文字列を出力してくれて便利
validatorを書く側が間違えると当然相手の生成ケースが正しいのにエラーを吐く（一敗）
ジャッジ
俺は何もやってないので知らない
今回の根付き木の問題みたいに正解が一意じゃない時は正解判定コードが必要なはず
やむなくがいつの間にか書いたんだと思ってる
アップロード
ここまで作ったものたちを当然コンテストサイトにあげる必要がある
ついでにコンテストの名前とか時間とかそういう設定もする
偉そうに書いているけどいつの間にかやむなくが全部やってたので正直何も知らない
テスターを見つける
なんか強い人にコンテスト前に出てもらう
やむなくがTwitterで募集したら強い人が引き受けてくれた
俺は全然やりとりしていないので知らなかったけどテスターの意見により問題順が変わったっぽい
宣伝
【HackerRank有志コンテストのお知らせ】
— やむなく (@yamerarenaku) November 22, 2019
11月祭プログラミングコンテスト2019 を開催します！！！
コンテスト時間: 11/23 17:00~19:00 (120分)
問題数: 5問
配点: 400-450-500-550-600
writer: drogskol, yamunaku
コンテストページ: https://t.co/PguJU7pbeA
明日開催の11月祭プログラミングコンテスト2019に回文部からも回文にまつわる問題を一問提供させていただきました
— 京大回文部 (@Ky_oto_yK) November 22, 2019
どなたでも参加できるので時間の都合がつく方はぜひ挑戦して見てください！ https://t.co/rum14ANrkW
いろんな人に挑戦してほしいので適当に宣伝をする
なんでdrogskolアカウントで宣伝ツイートしてないんだろうな
あ
実は開催1週間前頃は問題案出来ているんだからすることなんてほとんどないやろと思ってのほほんとしていた
やむなくから何日に何をするべきみたいな予定表が来てもしかして時間ないのか？みたいな気持ちになる
日曜にやろうと思っていたらGigaCodeが入っていたから土曜になったりしてさらに準備期間が減ってようやく焦り始める
コンテスト
図書館で勉強しながら順位表を監視
全然勉強に集中できなくてどんどん監視頻度が上がった
いつの間にか質問が来てる！でもすでにやむなくが答えてる！みたいなことが2回くらいあった
いろんな人が参加してくれて、簡単枠がないの結構申し訳ないなぁとなった
大工さんのやつでサンプルがただの偶奇問題に見えるの全く気づいてなくて、みんな同じ提出してるのを見てびっくりした
りあんさんが600を結構早めに通したから簡単なのかな？ってなったけど結果的にはそうでもなかったみたい
難易度を完全に見誤っていて、
A<D<B=C<E だと思っていたんだけど、コンテストが終わって見ると
A<C<B<E<D だった
Aは知識ゲーなのでDが実質一番簡単と思ってたのに実際は最難っぽくて何も分からん
コンテスト時間割とぴったりだったっぽくて難易度逆転と簡単枠が無い以外は結構いいセットになった気がする
終わりに
初めての経験ばかりで大変だったけど楽しかった
結構好評だった気がしてホッとしてる
労力割と大きいので次いつ出来るかは分からないけど機会があればまたやりたい
writerをやりたくなったらやむなくを雇うのが最適解
