[non titled]

トレーディングとイラスト練習と空間と

9月18日 HackerRankの問題 New Year Chaosを考える

ポイントはわいろを渡すのは2回までだけど、わいろを受け取る回数は無制限ということ。だから、前にいくのは2人分だけど、後ろにいくのは何人分でも問題なくなる。なぜなら、最初の人が一番最後尾に移動したとしても、それは自分でわいろを渡して移動したのではなく、わいろを受け取って移動させられたものだから。

 

この条件を満たすかチェックするのが

q[i] - (i+1) > 2

評価された値が

  • マイナスなら、それは要素が不利な位置に移動している
  • 0なら、要素は移動していない
  • 0<q[i]-(i+1)<2なら要素はルールを満たす範囲でわいろを使って有利な位置に移動している
  • q[i]-(i+1)>2ならルールを破らないと成り立たない

 

1 2 3 4 5→ 2 3 4 5 1 なら2が1にわいろを、そして3が1にわいろを...というようにして1は最後尾になる。この並び方はわいろを2回まで渡して良いというルールを破らずに実現できる。

 

1 2 3 4 5→5 1 2 3 4 だと5は元の位置に戻るには主体的に4回移動しないと成り立たない。つまりわいろを4回渡さないと出来ないことになる。これはルール違反。

5が元の位置に戻るために必要な移動というのは5がわいろを渡すという行動以外では成り立たない。なぜなら、わいろを渡してわざわざ後ろに行く人間はいないから。だから仮に1 2 3 4 5→1 2 3 5 4 となったのなら5が4にわいろを渡した以外ありえない。

 

また、この問題においては考えている要素以外でどんな入れ替えが起ころうと、順番が何であろうと影響はない。 1 2 4 3 5と2 1 3 4 5の2つの数列が与えられたとき、5から見て前の数列が何であろうと5には関係がない。