夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

538

xx- 0.0pt

1112->1014(-98)
猛省

Easy

再帰で書いてWA
翌々考えてみると最悪オーダーがO(2^n)のコードで何やってんだって話ですねw
for文で回します。
TLEの僕はともかく?をまとめて処理してしまって間違えてる人いたので注意しましょう(途中の最大を答える問題なので・・・)

class LeftOrRight {
public:
    int maxDistance( string program ) {
        int r=0, l=0;
        int res=0;
        for (int i=0; i<program.length(); i++) {
            if (program[i]=='R') {
                r++;
                l--;
            } else if (program[i]=='L') {
                r--;
                l++;
            } else {
                r++;
                l++;
            }
            res=max(res,max(abs(r),abs(l)));
        }
        return res;
    }
};

Medium

正直これが競技中に思いついた人たち尊敬してます(笑)
問題は各自見てもらうとして、今回使う法則は奇数と偶数の数列があったときそれを任意の順番に並べ各連続二項間の差および、最初の要素の値を足すと以下のことが成り立つという事

  1. 奇数だけの場合かならず合計も奇数
  2. 偶数だけの場合かならず合計も偶数
  3. 両方からなる場合合計は奇数も偶数もありうる

1、2はやってみれば確かにそうなることがわかります。
3はどうでしょうか?これは合計を奇数にしたいなら最初に偶数をかためてあとに奇数をかためる、偶数ならその逆にすることで成立します。
証明は実は簡単で、奇数の出てくるタイミングは最初の項か偶奇が変わる二項間の差のときだけであるので、最初を偶数列で固めると奇数が出てくるのは一回のみになり合計も奇数、奇数列で固めると奇数の出てくるタイミングが二回になり合計が偶数となるわけです。
ただこれを競技中に思いつけと言われても・・・ねぇw

class EvenRoute {
public:
    string isItPossible( vector <int> x, vector <int> y, int wp ) {
        int sz=x.size();
        for (int i=0; i<sz; i++) {
            if ((abs(x[i])+abs(y[i]))%2==wp) return "CAN";
        }
        return "CANNOT";
    }
};

Hard

読んでない

猛省

猛省します
とりあえず精進するためにも片付けがんばらなくては(^_^;)