パーソナルブログメモリ

a = [1, 1]
for _ in "*" * 999: a += [sum(a[-2:])]
print(a)

アルゴリズムの一考察　二倍伸縮分（微分の幅を変える）による比較の高速化

2025-01-21 | CodinGame

こんな問題を解く

まず東西一本のケーブルを引き、そこから各家庭に垂直なケーブルをつないでいく　最短の長さは？

 

最終的に作成したプログラムがこれ

このプログラムはどこかに最短があり、その前後は伸びるだけという線分の最短を求めるために作成している

その最短のために3つずつ比較、この3つを1つずつ動かして、比較するアルゴリズムだと膨大な幅のあるケースでは解けない（時間制約があるため）

そこで３つの比較する間隔を２倍ずつ増やして、３つの比較の中心もその間隔だけ、大きくしていく

３つの真ん中が最短になったときから、その間隔を2分の１ずつ減らしていき　最小間隔（この問題では1）になったときの最短の位置を求める

 

この問題ではもっと簡単に数学的に解けるのだけれど

類似のケースで膨大な計算量になるときに、使えそうなアルゴリズムだと考えるのでここに記す

（すでにどこかにあるだろうけど）

伸縮分と名付けてみる

 


最新の画像［もっと見る］

コメントを投稿

ブログ作成者から承認されるまでコメントは反映されません。