Parliament(4)
- 超絶テクニック（実装）
前回の例で説明した第3群を利用して、具体的にコードを書いてみよう。
まず、第1回でも述べた「各群の最後の2つだけが3から始まる」という部分の処理を考える。最後の2つのtとmの値を見てみると、
で、t >= mになっている。他の値では、すべて t < m になっているので、これを利用することにする。特に短く書くのであれば、if(t>=m)...ではなく、整数値の乗除算は小数点以下が切り捨てられるのを利用すれば、t/mと書くだけで十分である。
N=12のとき、t = 3, m = 3
N=13のとき、t = 4, m = 3
次に、
N= 9: 2 3 4
N=10: 2 3 5
N=11: 2 4 5
のように、途中から1増やさなければならない場合の処理を考えてみる。
これについてもN, tとmの関係に注意すれば、ある規則に気付くだろう。
Nとtを書き出してみると、
当然だが、Nが1ずつ増加すると、tの値も1ずつ増加する。
(m=3)
N= 9: t=0
N=10: t=1
N=11: t=2
N=12: t=3
N=13: t=4
N=10のときは、最後の数だけ1増やしたい。
N=11のときは、最後の2つだけ1増やしたい。
N=12のときはすべて増やすのか？
それはNOだ。なぜなら、N=12,13のときは3からスタートするので、既に1ずつ増やしてある。ということは、N=12のときはそのままにしたい。
ここで気付くはずだ。最後だけ1増やすということは、N=10のときと同じ処理をしたい。N=10のとき、t=1になっている。そう、tの値から、さらにmの剰余を取ればよいことになる。こうするとN=12のときも、t%m=3%3=0となり、N=9の時と同じになる！
しかしN=13のときは最後の数だけ1増やさなければならない。
以上の点を踏まえて、この様なコードを書いてみた。
現在の最短コードは86Bであるが、90バイトを切るためには更なる超絶テクニックを駆使せねばならない。
int i, t, m=2;main(){
scanf("%d",&t);for(;t-m>=0;){
t-=m;
++m;
}m-=2;
for(i=0;i<m;++i){
int n = i + t/m;
if( i + t%m >= m ) ++n;
printf("%d ",n+2);
}
}
つづく
