とけろぐ

作戦ミス

常に現在地からの最短の(拾われていない)ゴミを拾っていくという作戦を立てた。

サンプルケースはすべて答えが合ったので堂々と提出

そしてWA

Σ(￣ロ￣lll)

これは誤りである。

例えば・・・

-3 -1 2 3 4

から3つのゴミを拾うとき(スタート:0(ゴミなし))

ゴミ2つまでは0→-1→-3と拾っていけるが、ゴミ3つめは-3→2と大移動をして拾わなければならない。

このときの総移動距離は8となる。

しかし0→2→3→4と進めば総移動距離は4となり半分で済む。

よってこの作戦ではノルマ分ゴミを拾うときの最短移動距離を常に正しく求めることができない。

正しい解法はyukicoder公式の解説ページに載っている。

https://yukicoder.me/problems/no/370/editorial

様々な場所で折り返してみて移動距離が最短になるところを選ぶというものである。

push_backの誤用

これはかなーり恥ずかしいミスである。

vector hoge(1000);
hoge.push_back(12);
cout<<hoge[0]<<endl;
//（12を期待したが…）
//出力:0

cout<<hoge[1000]<<endl;
//出力:12
//ここにいる！

要素数を指定して宣言すると、前からその数の要素が指定がなければ初期値0で確保される。

そのためpush_backするとその後ろに要素が追加されるのである。

それを失念していた。

他にもいろいろつまずいた気がする。

かなり苦戦したのでACのうれしさのあまりわざわざブログまで書いてしまった。