SRM658参加しました。

社会人になってから、あまり参加できるタイミングでのSRMがなく、ココ何回かご無沙汰でしたが、今回のSRMは休みの日の夜だったので参加出来ました。

ただ、疲れがたまっていたのかmid解いてる途中で寝落ちしてしまい、成績的にも微妙な結果になってしまいました。

(rating: 961 -> 960)

• 250 : AC
• 500 : no submit
• 1000 : no submit
• Challenge WA : 0

250 : InfiniteString

文字列sとtが与えられる。この文字列をそれぞれ無限につなげていった時、同じ文字列になるかどうかを判定せよ。

解法

この問題では、その文字列を先頭から比較していき、一方の文字列の終端に来たら先頭に戻し、両方の文字列で終端に到達するまで全ての文字が同じならば一致、その過程で一致しない箇所があれば一致しないという判定になります。

コード

class InfiniteString {
    public:
    string equal(string s, string t) {
      int i=0,j=0;
      while(i<s.size() && j<t.size())
        {
          if(s[i]!=t[j])
            return "Not equal";
          if(i==s.size()-1 && j==t.size()-1)
            break;
          i++;
          j++;
          if(i>=s.size())
              i=0;
          if(j>=t.size())
              j=0;
        }

        return "Equal";
    }
};InfiniteString.cpp

500 : MutaliskEasy

問題概要

SCVが複数あり、それぞれにHPが存在する。 1回に、1機のSCVに9ダメージ,別のSCV1機に3ダメージ,さらに別のSCV1機に1ダメージを与えることができる。 SCVのHP配列xが与えられるので、そのSCV全機のHPを0以下にするための最低ステップ数を返す。

解法

SCVの数は1~3機なので、全てのパターンで3機存在するとしてしまうことも可能です。(HP0の機体が複数あるとする)。 その後は、ダメージの与え方をDP等で探索すればできると思いますが、幾つか手法を試しているうちに寝落ちしてしまっていました。 後日、解き直ししたらのせます。

1000 : OddEvenTreeHard

同じく寝落ち。