経路構成はある意味, 短縮技術以上に差のつくかもしれない部分です. 

このページでは, 実際の問題で経路を考える際に役に立つ定石を取りまとめています. 


【思いついたの書き足してね！】

*位置合わせ [#ma9a61b4]
-無限ループによる位置合わせ
-中心極限定理
**繰り返しによる位置合わせ [#s7462109]
四方の壁にぶつかる経路は, 無限ループで繰り返すと必ず正しい軌道に乗ります. ~
例えば[[Problem 1637]]のような問題においては, 位置合わせなどを意識せず, ~
とにかく1辺分を作って無限ループに入れれば勝手に位置が合うことになります. 

壁配置が複雑だと, これが上手く機能しない場合があるので要注意. 

**中心極限定理 [#m558cb96]
 f(X,T):f(sX,T-1)Xr
 f(,30)
のように, 等差数列的に育てたパーツを大きい方から並べると, 中心に戻るという定理. ~
 f(X,T):f(sX,T-1)rXr
 f(,30)
のように, 「両側に棒を立てて中央に戻る」というような使い方もある. 

過去のコンテストでは[[Problem 1317]]や[[Problem 1550]]などで用いられている. 

*パーツの作り方 [#v613b00f]
**正方形1 [#cf7b39dd]
-再帰の打ち切り
--XXXXで打ち切る
 a(X,T):XXXXa(sX,T-1)
 a(r,9)
正方形を作り, その場に留まります. 
--XXで打ち切る
 a(X,T):XXa(sX,T-1)
 a(r,9)
正方形の中央から外側へ進みます. 中央への移動手段がある場合, 4回で作るより短いです. 
--中央から中央へ
 a(X,T):XXa(sX,T-1)X
 a(r,9)
上述の正方形を描いた後, 中心極限定理で中央へ戻った場合ですね. 

-棒を並べる

**正方形2：斜めの場合 [#uaa1cb74]
-再帰の打ち切り
--XXXXで打ち切る
--XXで打ち切る
-棒を立てる
-XXrXX, XrXXrXの関数の利用

**直角二等辺三角形 [#rff18c5e]
-棒を立てる
-XXrXX, XrXXrXの関数の利用

*4倍の4倍 [#n445fd24]
-中心から増やす
--2倍関数や4倍関数を使うのが一般的だが, 中央に戻ったあとはとにかく増やせばよいので, ~
4倍にこだわらない方が良いこともあることに注意. 
-隅から増やす
--1辺がXXrXX的な関数で増やせることが多い. それを繰り返しに乗せればよい.
トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS