SRM 627 Div2 oo- unrated -> 1176

TopCoder SRM

するめ。初参加。challangeとかのことは一応知ってる状態。

英語の問題をどれだけ早く読み解けるかという壁が立ちはだかった。読めても今のところは1000点はだめだっただろうな。

250 ManySquares

概要

いろんな長さのまっすぐな棒がある。組み合わせて作れる正方形の最大数。ただし1辺を構成するのに1本しか使えない。

入力

  • 棒の長さの列sticks
    • 列の長さは1..50
    • 棒の長さは1..1000

出力

  • 作れる正方形の数（非負整数）

解法

結局同じ長さの棒4本に対して正方形1つになるので、端から集計していって、4本毎に個数に1足す。

class ManySquares {
  public:
  int howManySquares(vector <int> sticks) {
    map<int,int> hash;
    int ans = 0;

    rep(i,sticks.size()){
      hash[sticks[i]]++;
      if(4 == hash[sticks[i]]){
        hash[sticks[i]] = 0;
        ans++;
      }
    }

    return ans;
  }
};

500 HappyLetterDiv2

何かのゲーム。最初にフィールド内に何人かプレイヤーがいて、各プレイヤーが英小文字をひとつずつ持っている。各ターンに異なる文字を持つプレイヤーが2名選ばれてフィールドから除外する操作を、選べなくなるまで繰り返す。残ったプレイヤーがいるなら、プレイヤーの持っている文字は全て同じになるので、その文字が勝利文字。いなければ、勝利文字はない。

最初の段階でゲームがどのように進行しても必ず勝利文字になる文字が特定できるらしい。できるならその文字を、できなければピリオドを返せ。

入力

  • 最初にフィールド内にいるプレイヤーの文字を結合した文字列letters。
    • 文字列長は1..50
    • 各文字は'a'..'z'

出力

  • 必ず勝利文字になるような文字が存在するなら、その文字。しなければ、ピリオド。

解法

過半数を占める文字があればそれが勝利文字、なければ選び方によって変動するのでピリオド。半分丁度ではプレイヤーが残らないので勝利文字にならない。

class HappyLetterDiv2 {
  public:
  char getHappyLetter(string letters) {
    map<char,int> hash;
    int maxCount = 0;
    char mostPopular = '.';

    rep(i,letters.size()){
      hash[letters[i]]++;
      if(maxCount<hash[letters[i]]){
        maxCount = hash[letters[i]];
        mostPopular = letters[i];
      }
    }

    if(maxCount <= letters.size()/2){
      return '.';
    }else{
      return mostPopular;
    }
  }
};

1000 BubbleSortWithReversals

概要

  • 非負整数列Aをバブルソートするときに、swapする動作の回数を最小にしたい。
  • ソートする前に次の操作をK回まで行ってよい。
    • Aの部分列の順序を反転する。ただし、各回で選ぶ部分列は独立であること。

入力

  • 非負整数列A
    • 長さは2..50
    • 各値は2..50
  • 自然数K

出力

  • swap操作の最小回数（非負整数）

解けてないので解けたら更新。