ZONeエナジー プログラミングコンテスト “HELLO SPACE” B - 友好の印
問題
考察
コンテスト本番では上る高さを二分探索で決めて、UFOからその上った高さの位置までの直線を
一次関数y = ax + bの式に当てはめて、各iについて、x = d[i]の時にh[i]以上かどうかで探索していた。
これだと実装が複雑になるし、バグも出やすいので悪手だった。
公式解説では
H - D / (D - d[i]) * h[i]のmaxを求めていた。
発想的には一番高い遮蔽物の上部を通るような直線をタワーとUFOの間に引くと
遮蔽物とUFO間、タワーと遮蔽物間、タワーとUFO間で直線ができる。
遮蔽物とUFO間の直線を斜辺とした直角三角形
タワーとUFO間の直線を斜辺とした直角三角形が相似であることを利用する。
(D / D - d[i]) * (H - h[i])=上った高さとUFOの高さとの差 なので
UFOの高さ - （上った高さとUFOの高さとの差）で上った高さが求まる。
それを各iについて行ってmaxを取る。
追記
この考え方がわかりやすい
昨日のBに悩んでた人は、ひっくり返すと計算しやすいかも。
— chokudai(高橋 直大)🍆 (@chokudai) 2021年5月2日
7進むと5増えます。10進むといくつ増えるでしょう？ pic.twitter.com/8X2wx0Aty2
反省点
タワーと一番高い遮蔽物とUFOの間に直線を引くところまでは本番でも
思いつくことができたが、そこからの数学的発想や知識を使ったところで
迷走してしまった。
