- ヒッキーのプログラミングするスレ 9 (旧 プログラミング雑談 in HIKIKO) [無断転載禁止]©2ch.net
173 ：（-＿-）さん[sage]：2017/03/20(月) 12:42:29.87 ID:TRx5EZH30 - >>157
難しく考えすぎだよ
問題文にはない変数としてt日目と
容量の上限としてNを導入すると
t日目の朝：n+m（ただしn>N ならばn=Nにされる）
t日目の夜：n-t
これしかいってない。だからこれをそのままwhileで回すだけ
＝＝＝＝＝＝＝
def tmp(n, m):
t=1
N = n
while(True):
n += m
if n > N:
n = N
n -= t
if n <= 0:
return t
t += 1
＝＝＝＝＝＝＝
javaっぽく書いて説明もつけると以下。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
n,mはユーザーから与えられる
# 初期化
t=1
N = n
while(True) {
# t日目の朝（穀物がm増加。ただしNが上限）
n += m
if(n > N) { n = N }
# t日目の夜（穀物がtだけ減少）
n -= t
# t日目で空になるか判定
if(n <= 0) { return t }
# t日目の処理が終わったのでtが一つ増える
t += 1
}
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
|
- ヒッキーのプログラミングするスレ 9 (旧 プログラミング雑談 in HIKIKO) [無断転載禁止]©2ch.net
174 ：（-＿-）さん[sage]：2017/03/20(月) 12:44:55.59 ID:TRx5EZH30 - ありゃ、空白が省略されちゃってるな。
初めのコードは正確にはこう
＝＝＝＝＝＝＝
def tmp(n, m):
t=1
N = n
while(True):
n += m
if n > N:
n = N
n -= t
if n <= 0:
return t
t += 1
＝＝＝＝＝＝＝
|
- ヒッキーのプログラミングするスレ 9 (旧 プログラミング雑談 in HIKIKO) [無断転載禁止]©2ch.net
175 ：（-＿-）さん[sage]：2017/03/20(月) 12:47:16.81 ID:TRx5EZH30 - 空白が上手く書けない；；
これで合ってるかな…
（while, ifの次の行はインデントが一つ下がってる）
＝＝＝＝＝＝＝
def tmp(n, m):
t=1
N = n
while(True):
n += m
if n > N:
n = N
n -= t
if n <= 0:
return t
t += 1
＝＝＝＝＝＝＝
|
- ヒッキーのプログラミングするスレ 9 (旧 プログラミング雑談 in HIKIKO) [無断転載禁止]©2ch.net
182 ：（-＿-）さん[sage]：2017/03/20(月) 20:45:58.49 ID:TRx5EZH30 - ああごめん
実行時間に制限があったのかｗ
じゃあ２分岐サーチですね
>>177
最大値とか最小値ということじゃなくて、
このケースだと平均値からkの２次式を計算するときに
実数から整数へとキャストしているせいで２分岐の両端を
更新する際に調整が必要になっている。
今回は「切り捨て」でキャストしているから、小さいほう（left）にだけ
+1する必要があるってこと。もし切り捨てじゃなくて切り上げにしていたら
逆に大きいほう（right）のほうを-1する
（元々実数でやっていればそもそも更新時の+1など不要なんだけど、
キャストするってことはx軸の位置を最大0.5ずらすので、平均値と
小さいほうか大きいほうの差が0.5以下だと循環してしまう場合がある）
具体例で考えてみるとわかりやすくて、
例えばn=8, m=1で初期値を left=0, right=8でやってみると
途中でleft = 3, right = 4, 平均=3.5->3となってleftの更新時に
+1がないと収束せずに延々と計算が続いてしまう
（キャストが切り上げなら3.5->4だからrightのほうに-1）
|
- ヒッキーのプログラミングするスレ 9 (旧 プログラミング雑談 in HIKIKO) [無断転載禁止]©2ch.net
184 ：（-＿-）さん[sage]：2017/03/20(月) 20:55:21.33 ID:TRx5EZH30 - もうちょっと細かいことを言うと
平均値が3.5で、そのまま実数値としてk*(k+1)計算すれば
3.5*4.5=15.75となるけど、3.5を3にキャストすると
3*4=12だから、キャストすることで k*(k+1)>=14 の不等号
判定が変わってしまうことが本質です
これってつまり、２次関数 k*(k+1)=14の正の解が3と3.5の
間にあることを意味してるわけです。２分岐の更新とキャスト
という２つの処理でこの解の左右を行ったり来たりしちゃってる。
|