SRM450 DIV2

問題を理解するのに10〜15分かかっちゃうな…。

250pt

0と1からなる文字列が与えられる。nビット目を0か1に変換することが可能で、
nビット目を変換したとき、0〜nビット目まで全て同じ値に変換される仕様。
0000の2ビット目を1に変換すると0111になり、さらに1ビット目を0に変換すると0100になる。
全てが0にセットされたビット列から与えられた文字列を生成するまで最小変換回数を返す。


解法例：
上位ビットから順に、0→1、1→0に変わるときにカウントすればおｋ

class StrangeComputer
{
public:
  int setMemory(string mem){
    int ans=0;
    char c='0';
    for(int i=0;i<mem.size();i++){
      if(mem[i]=='1' && c=='0'){ans++; c='1';}
      else if(mem[i]=='0' && c=='1'){ans++; c='0';}
    }
    return ans;
  }
};

500pt

プレイヤーは2人でn個積まれた石の山を1〜n個の石を取って0にしていきながら、最後の石を取った人物を答える。
先手はAlice。複数の山がある場合はi番目の山を0にしないと他の山の石は取れない。
どちらのプレイヤーも最適な石の取り方をする。


解法例：
複数の山があるとき、最後の山で先手を取れば全部取って勝ちになります。
つまり、最後の1つ手前の山の最後の石を相手に取らせればよい。
山に石が何個あっても、石を取る方法は石を全部取るor1個だけ石を残すの2択に落ち着きます。
このとき、石を全部取るor1個だけ残すという主導権を握る人物が最後の1つ手前の山の
最後の石を取らせる順番を決めることが出来るので、この主導権を先に握った人物が勝ちます。

class OrderedNim
{
public:
  string winner(vector<int> layout){
    int ans=1;
    for(int i=0;i<layout.size()-1;i++){
      if(layout[i]==1)ans=!ans;
      else break;
    }
    return ans?"Alice":"Bob";
  }
};

反省

最後の1つ手前の山で最後の石を相手に取らせればいいのだから、山に対して常に先手を維持すればいい
という間違った論理を展開してしまいチャレンジされたorz
途中までは良いけれど、そこから間違った考えに及んだとき検証する能力が足りない＆
間違った選択肢が存在してる時点で条件が整理されてない、考えが及んでいない。
という自己分析。うーん、プログラミング以前の問題だな…どうすればいいんだろう。