作問がうまく行かなかった話。
こんにちは、にぼしです。
先日、競技プログラミングの問題として面白そうな問題を思いついたのですが、自分の期待するような問題が作れなかったので、残念なエピソードとしてココに記していこうと思います。
こういう失敗談はなかなかないので、面白いんじゃないでしょうか。
ちなみに私はサク問をしたことがありません。
まぁ、うまく行かなかったって言っても、期待どおりのものに対してACを吐き、その解法ダメだよ〜WWに対してWAを吐くことが出来ないってだけで、別に問題としてダメってわけではないですね。 (ココ重要)
問題
まずは、問題をご覧ください。(作問が初めてなので、問題文的にこうした方がいい。とかあれば指摘してほしいですね)
[問題] 入力として整数Nが与えられる。 N = 1 + 2 + 3 + ... + K (すなわち、Σi (i = 1 からK))で表せるかを判定し、 上の形で表せる時、Kを出力し、表せないならば"-1"を出力せよ。[制約] N <= 10 ^ 18
[入力例1] input N = 6
output 3
N = 1 + 2 + 3 で表すことが出来ます [入力例2] input N = 210
output 21
何をさせたかったか
想定解として二分探索をさせて、 (left = 0, right = 232 ぐらい？ , k = (left + right ）/ 2 )
N = ( K * ( K - 1) ) / 2 ;であるかを判定するっていうふうなのを想定していました。
それで、
ll plus = 1 ;
ll sum = 0;
while(sum < N ){
sum += plus;
plus ++ ;
}
として、1+2+3+...+Kとして、ちょうどNになるかをループを回す解法をTLEで落としたかった。
(伝わりますか？)
で、ループを109回させるとなると、109回ループを回したときの値は (109 * ( 109 -1)) / 2で1017くらいなんですね。
ただ、このループだと、AtCoder上のコードテスト（c++)は、実行時間が900msくらいだったんですよ。
で、二分探索でlong long でオーバーフローしないようにするためには,各kについて (K*(K-1)/2)が64bitに収まらないと行けないので、TLEを出すようなNの制約にしようとすると、Overflowを起こしてしまうということになってしまいました。
そんな感じで、うまく行きませんでした。
ちょっとまって。
N <= 264 -1
にしたら二分探索は通るけど,ループで解く(1+2+3+...+K）で求める解法を落とせる？
落とせるかも？
ただ、制約が N <= 264-1 なんてなっている問題、汚くていやじゃない？（そんな問題見たことが無い気がする。）
落とせそうな気がしてきた…
とりあえず。
とりあえず今回はTLEを出して、二分探索で解かせるっていう問題を作ろうとした。
結局、TLEを出すことはできなかった、（という設定のもとで）失敗しました。
（もしかしたら問題として良いものになるかも知れませんが、それはまた今度考えます）
問題を思いついたきっかけ
一週間くらい前に、45っていう数字を聞いたときに、「45がΣi(i = 1 からk)の形で表せる数かどうかってどうやったらすぐ判定できるのかな？」って思いました。
で、Σi( i= 1 からK) = ( k * ( k-1 ) /2 )だから
2倍した値が k * ( k + 1 )ならΣの形で表せるなって思いました。
たとえば、45は2倍したら90。 90 = 9 * 10 だから、45はΣi ( i = 1 ~ k)で表せる。
この、Σで表せるかどうかの判定法が面白いな〜って思って、この問題を思いつきました。
感想
問題を考えるのって難しいですね。 茶色の僕がちょっとしたひらめきで問題を作れるほど世の中甘くないですね。
でも、作問するの楽しかったです。
作問をして、「あ〜この問題ダメだな」ってなって、ツイキャスでhotmanさんにこんな問題作ったけどダメだった〜って 言って話をしてたのですが、ダメな理由というか、ダメだということについてお話してもらえて、「あ〜ダメだな」が深まりました。（どういうこと？）
まあとりあえず、作った問題についてお話させてもらったってことです。(ありがとう）
競技プログラミング楽し〜〜〜〜 夏までに水色なりたいという野望を抱いております.
おつかれ
後日談
この記事を登校した後にフォロワーさんからのリプライで、 出力を1個にするから単純ループ解法が落とせないんだ！！ってなりました。
つまり、入力で 5
15 10 6 1 3 みたいな感じにして
出力を 5 4 3 1 2
みたいに答えさせる問題にしたらTLEを出してやることが出来るっぽい！！！
