TopCoder SRM 525 過去問

TopCoder SRM 525 Div2 Easy と Medium を解きました。

Easy

幅2マス、長さNマスの道がある。マス目は、濡れている場合と乾いている場合がある。
左上からスタートし、右上まで、濡れたマスを通らないように移動したい。
移動は、縦、横、斜めが可能。
可能な場合はYESを、不可能な場合はNOを出力せよ。

解法

まぁ、やるだけです。

提出コード

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <cstdio>
#include <functional>
#include <numeric>

using namespace std;

#define REP(i,s,e) for (int i = int(s); i != int(e); i++)
#define rep(i,e) REP(i,0,e)
#define foreach(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ALL(c) (c).begin(), (c).end()

class RainyRoad {

 public: string isReachable(vector<string> road) {
  rep(i,road[0].length()) if(road[0][i] == 'W' && road[1][i] == 'W') return "NO";
  return "YES";
 }

};

Medium

長方形の上にコインが幾つか乗っている。
プレイヤーは一回につき、上下右左を選び、全てのコインをその方向に動かしてよい。
この操作によって、与えられた長方形からコインがはみ出た場合、コインは落ちて消える。
コインがK枚になるような最小の操作回数を出力せよ。なお、K枚に出来ない場合は-1を出力せよ。

解法

操作を何回行っても、残るのは長方形になる。(或いは何も残らない。。。)
部分長方形を考え、その長方形に対して何枚コインが残るかが分かれば、最小の命令回数は一意に定まる。
例えば、下の行を1つ、上の行を2つ削るような部分長方形を作る場合、下、上、上、上となり、命令回数は四回である。
下と上の順番を逆にしてしまうと、上、上、下、下、下となり、5回となってしまう。
反対側の辺も削るような長方形を作る場合、順番に注意。

提出コード

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <cstdio>
#include <functional>
#include <numeric>

using namespace std;

#define REP(i,s,e) for (int i = int(s); i != int(e); i++)
#define rep(i,e) REP(i,0,e)
#define foreach(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ALL(c) (c).begin(), (c).end()


int cum[51][51];

class DropCoins {

 public: int getMinimum(vector<string> board, int K) {
  int width = board[0].length();
  int height = board.size();
  int ans = -1;
  memset(cum,0,sizeof(cum));
  REP(i,1,height+1) REP(j,1,width+1){
   cum[i][j] = cum[i-1][j] + cum[i][j-1] - cum[i-1][j-1] + (board[i-1][j-1] == 'o');
  }
  rep(y,height) rep(x,width) REP(y2,y,height+1) REP(x2,x,width){
   int coins = cum[y2+1][x2+1] - cum[y2+1][x] - cum[y][x2+1] + cum[y][x];
   if(coins == K){
    int up = y, left = x, down = height - y2 - 1, right = width - x2 - 1;
    int move = 2*min(up,down) + max(up,down) + 2*min(left,right) + max(left,right);
    if(ans == -1 || ans > move){
     ans = move;
    }
   }
  }
  return ans;

 }

};

最近サボりがひどく、いざTopCoderを開いてもついついTwitterを見に行くなどしてしまっていたため、ニコ生で放送しつつ解くということを試しにやってみた。
すると、なんと放送初回から@chokudai 先生が視聴するというミラクルが発生。これにはおいらもびっくり。もっとも、放送している時は全然気付かなかったし、@chokudai 師匠のありがたいアドバイスも勘違いしていて迷走していたのだが(笑)

次はCodeForcesが近いので、久しぶりに出るつもり。