sc12note/サンプルプログラム解説
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
since1995
開始行:
[[caution]]
[[sc12note]]
サンプル攻略のために
*サンプルプログラムの方針/基本戦略 [#p0637eb1]
(ここの章の話はスライドにも書いているはずです)
目標は最長距離の出力およびそれを実現する移動経路の再現で...
**最長距離のみの出力 [#m454417c]
ある時刻tmに起こりうるA,B,C三人の状態について考える。
~そのために、ある時刻tmにAはどこにいるかを考える。
~このとき、Aは駅にいるか、ある列車にいるかのどちらかの状...
~よって、Aの存在する場所はNst(駅数) + Ntr(その時間に存在...
~つまり最大でMAXst + MAXntr( = MAXss)だけの大きさを確保し...
したがって、3人の場所を考えると、最大でMAXss * MAXss * MA...
~この大きさの表に、ある時刻tmで、A,B,CがそれぞれposA,posB...
~[posA][posB][posC]に保存していくことを考える。
~最大値のみを求めるのであれば、この大きさの表を1200回(MAX...
**最長距離に至るためのルートの復元 [#i8253d40]
話は簡単で、
~先ほどの表を時間ごとに拡張したものを考え、
~[tm][posA][posB][posC]に、最長距離とその最長距離を実現す...
~最終的な答えから手繰っていって答えを求めることができます。
**大きすぎるデータ [#p3c056c4]
実は[posA][posB][posC]ではちゃんと保持することはできます...
~[tm][posA][posB][posC]までを保存しようとすることはできま...
そこで、しかたがないので確保できるギリギリの[MAXtm4test][...
~とりあえずこれでやりくりをして、求めた表をたどってMAXtm4...
その手繰った場所からもう一回MAXtm4test手繰るためにもう一...
...
という作業を繰り返して最終的に3人のたどった道のりを復元し...
**これに関して細かい話 [#z791baf7]
こういう動的計画法で表を更新する際に
~ある一つの状態から次の状態の遷移を考えて更新するか、
~ある一つの状態を更新するためにひとつ前の状態を考えるか、
~の二通りの考え方があります。
実は当初は前者で実装していましたが、
~GPUで高速にするには不適当です(そのあたりは作成者はちゃん...
したがって、前者型の実装を後者型の実装に変更した経緯があ...
*変数・配列に関して [#zbdfa26e]
**まずは必要なものを確認 [#c57ef4a4]
さて、以上の基本戦略を成し遂げるために何が必要かを考えて...
1-1.
~[MAXss]に書き込まれている数字<=>今いる場所(列車ならば列...
~の変換をできるようにする
1-2.
~さらに列車についてはもともとの列車番号ではなく、その時間...
~このため、(ある特定の時刻における列車番号)<=>(最初に与え...
の変換もできるようになる必要があります。
2-1.
~表を更新するためには
~ある時刻tmのある駅stにどんな列車が来るのかを知る必要があ...
2-2.
~さらにいま列車にいるとして、そのひとつ前の時刻にどこかの...
~もしくは、ひとつ前の時刻でも列車に乗っているのか
~も調べる必要があります
**それぞれの実現の仕方 [#t17c476d]
1-1.
~これについては、ある数字xを
~0<=x<Nstのときに、駅の番号をそのまま意味していることにし、
~Nst<=xのときに、この時間での便宜的な列車の番号を意味して...
この変換については例えばvalid関数でみかけることができます...
1-2.
~これは少々厄介です。
~便利のためにもある列車tに対して、
~先述の「便宜的な列車番号」は出現する任意の時刻で同じ数字...
こういうことから、この処理に使う表は実際のプログラム中で...
tidTmTr[MAXtm][MAXntr] : ある時間tmおよび、「便宜的な...
smalltidTr[MAXtid] : ある列車が与えられるとき、そ...
この表を作る部分を実装している部分がinput2tablesの一番最...
同じ数字を割り振りたい制約から、列車が遅く消滅する順に
~(本当は列車が早く現れる順の方がわかりやすそうですが)
~みていって、使用可能な数字があればそこに一気に割り当てさ...
ここの部分を実装するためにはある列車が登場する時刻および...
~このために使うのが以下の表です
bgntmTr[MAXtid] : ある列車の登場時刻
endtmTr[MAXtid] : ある列車の消滅時刻
以上の表を完成させる処理はそれぞれの列車を読み込む部分で...
2-1.
この処理をするための部分が
moveData[MAXst][MAXtm][MAXtd]
となっています。
~要するに、ある駅st に ある時刻tm で到着する列車の情報を...
「出会う」ことの定義から、列車はこの場合運行表をまるまる...
~駅stにたどりつくひとつ前の駅の情報および列車の番号を保存...
(サンプルプログラムでは色々保存してしまっていますが…)
moveDataの作成はinput2tables関数の真ん中あたり(bgntmTr,en...
また、moveDataを使う際には次の表を頻繁に用います
cnttrStTm[MAXst][MAXtm]
これで到着数を管理しておいて、変なところにアクセスしない...
~(つまり、コメント部分が間違っているようです)
2-2.
ここで用いるのは以下の表です。
stTmTr[MAXtm][MAXtid] : ある時刻tm , ある列車tidはどの駅...
これを用いればすぐに駅かどうかの判定を行うことができます。
~この表は最初に-1に初期化しておき、あとはmoveDataの表を作...
**その他のわかりづらそうな変数 [#pa64d36d]
nowApos , nowBpos , nowCpos
main関数の最初に宣言されている変数で、復元に使います。
~具体的には、MAXtm4testの大きさだけ復元をした後に、
~その次復元する際にどこにA,B,Cがいるのかを覚えておいて、...
~覚えつつおこなっている。そのときにこれら変数が必要。
~(一週目にはMAXtmまで全部調べてそこで最長の距離をだすよう...
~それを起点に復元できる。
~しかし、二週目以降にMAXtm4testの分だけ復元するということ...
~最大値ではなくて、復元できているところの続きを復元すると...
~続きを始めるためにposA,posB,posCを保存しているということ...
*main関数について [#o7f3d72a]
**main関数の構造 [#m82eb693]
1.何回かかけて復元をしなければならないのでそれを繰り返す{
2.tm = 0から順番にはじめ、表を使いまわして作るべきとこ...
3.ある時刻tmの表をつくるために,[i][j][k]について構成す...
駅にいるか列車にいるかの8パターンに場合分けして
それぞれで更新をしている
}
}
4.復元作業。
}
このような形になっています。
**3.の内側の処理について [#v54d251b]
for(A=-1; A<...という書き方をしており、-1からスタートしま...
~-1はそのままの場所にとどまるという意味を持っています。
(岸本)
終了行:
[[caution]]
[[sc12note]]
サンプル攻略のために
*サンプルプログラムの方針/基本戦略 [#p0637eb1]
(ここの章の話はスライドにも書いているはずです)
目標は最長距離の出力およびそれを実現する移動経路の再現で...
**最長距離のみの出力 [#m454417c]
ある時刻tmに起こりうるA,B,C三人の状態について考える。
~そのために、ある時刻tmにAはどこにいるかを考える。
~このとき、Aは駅にいるか、ある列車にいるかのどちらかの状...
~よって、Aの存在する場所はNst(駅数) + Ntr(その時間に存在...
~つまり最大でMAXst + MAXntr( = MAXss)だけの大きさを確保し...
したがって、3人の場所を考えると、最大でMAXss * MAXss * MA...
~この大きさの表に、ある時刻tmで、A,B,CがそれぞれposA,posB...
~[posA][posB][posC]に保存していくことを考える。
~最大値のみを求めるのであれば、この大きさの表を1200回(MAX...
**最長距離に至るためのルートの復元 [#i8253d40]
話は簡単で、
~先ほどの表を時間ごとに拡張したものを考え、
~[tm][posA][posB][posC]に、最長距離とその最長距離を実現す...
~最終的な答えから手繰っていって答えを求めることができます。
**大きすぎるデータ [#p3c056c4]
実は[posA][posB][posC]ではちゃんと保持することはできます...
~[tm][posA][posB][posC]までを保存しようとすることはできま...
そこで、しかたがないので確保できるギリギリの[MAXtm4test][...
~とりあえずこれでやりくりをして、求めた表をたどってMAXtm4...
その手繰った場所からもう一回MAXtm4test手繰るためにもう一...
...
という作業を繰り返して最終的に3人のたどった道のりを復元し...
**これに関して細かい話 [#z791baf7]
こういう動的計画法で表を更新する際に
~ある一つの状態から次の状態の遷移を考えて更新するか、
~ある一つの状態を更新するためにひとつ前の状態を考えるか、
~の二通りの考え方があります。
実は当初は前者で実装していましたが、
~GPUで高速にするには不適当です(そのあたりは作成者はちゃん...
したがって、前者型の実装を後者型の実装に変更した経緯があ...
*変数・配列に関して [#zbdfa26e]
**まずは必要なものを確認 [#c57ef4a4]
さて、以上の基本戦略を成し遂げるために何が必要かを考えて...
1-1.
~[MAXss]に書き込まれている数字<=>今いる場所(列車ならば列...
~の変換をできるようにする
1-2.
~さらに列車についてはもともとの列車番号ではなく、その時間...
~このため、(ある特定の時刻における列車番号)<=>(最初に与え...
の変換もできるようになる必要があります。
2-1.
~表を更新するためには
~ある時刻tmのある駅stにどんな列車が来るのかを知る必要があ...
2-2.
~さらにいま列車にいるとして、そのひとつ前の時刻にどこかの...
~もしくは、ひとつ前の時刻でも列車に乗っているのか
~も調べる必要があります
**それぞれの実現の仕方 [#t17c476d]
1-1.
~これについては、ある数字xを
~0<=x<Nstのときに、駅の番号をそのまま意味していることにし、
~Nst<=xのときに、この時間での便宜的な列車の番号を意味して...
この変換については例えばvalid関数でみかけることができます...
1-2.
~これは少々厄介です。
~便利のためにもある列車tに対して、
~先述の「便宜的な列車番号」は出現する任意の時刻で同じ数字...
こういうことから、この処理に使う表は実際のプログラム中で...
tidTmTr[MAXtm][MAXntr] : ある時間tmおよび、「便宜的な...
smalltidTr[MAXtid] : ある列車が与えられるとき、そ...
この表を作る部分を実装している部分がinput2tablesの一番最...
同じ数字を割り振りたい制約から、列車が遅く消滅する順に
~(本当は列車が早く現れる順の方がわかりやすそうですが)
~みていって、使用可能な数字があればそこに一気に割り当てさ...
ここの部分を実装するためにはある列車が登場する時刻および...
~このために使うのが以下の表です
bgntmTr[MAXtid] : ある列車の登場時刻
endtmTr[MAXtid] : ある列車の消滅時刻
以上の表を完成させる処理はそれぞれの列車を読み込む部分で...
2-1.
この処理をするための部分が
moveData[MAXst][MAXtm][MAXtd]
となっています。
~要するに、ある駅st に ある時刻tm で到着する列車の情報を...
「出会う」ことの定義から、列車はこの場合運行表をまるまる...
~駅stにたどりつくひとつ前の駅の情報および列車の番号を保存...
(サンプルプログラムでは色々保存してしまっていますが…)
moveDataの作成はinput2tables関数の真ん中あたり(bgntmTr,en...
また、moveDataを使う際には次の表を頻繁に用います
cnttrStTm[MAXst][MAXtm]
これで到着数を管理しておいて、変なところにアクセスしない...
~(つまり、コメント部分が間違っているようです)
2-2.
ここで用いるのは以下の表です。
stTmTr[MAXtm][MAXtid] : ある時刻tm , ある列車tidはどの駅...
これを用いればすぐに駅かどうかの判定を行うことができます。
~この表は最初に-1に初期化しておき、あとはmoveDataの表を作...
**その他のわかりづらそうな変数 [#pa64d36d]
nowApos , nowBpos , nowCpos
main関数の最初に宣言されている変数で、復元に使います。
~具体的には、MAXtm4testの大きさだけ復元をした後に、
~その次復元する際にどこにA,B,Cがいるのかを覚えておいて、...
~覚えつつおこなっている。そのときにこれら変数が必要。
~(一週目にはMAXtmまで全部調べてそこで最長の距離をだすよう...
~それを起点に復元できる。
~しかし、二週目以降にMAXtm4testの分だけ復元するということ...
~最大値ではなくて、復元できているところの続きを復元すると...
~続きを始めるためにposA,posB,posCを保存しているということ...
*main関数について [#o7f3d72a]
**main関数の構造 [#m82eb693]
1.何回かかけて復元をしなければならないのでそれを繰り返す{
2.tm = 0から順番にはじめ、表を使いまわして作るべきとこ...
3.ある時刻tmの表をつくるために,[i][j][k]について構成す...
駅にいるか列車にいるかの8パターンに場合分けして
それぞれで更新をしている
}
}
4.復元作業。
}
このような形になっています。
**3.の内側の処理について [#v54d251b]
for(A=-1; A<...という書き方をしており、-1からスタートしま...
~-1はそのままの場所にとどまるという意味を持っています。
(岸本)
ページ名: