SRM 477 :: DIV2

250と500を正答、撃墜成功1、失敗1　緑に戻った。

システムテストを見ると明らかだけど、250問題のコーナーケースで落としてる人がすごく多い。
250問題は0-baseじゃなくて1-baseで入力が与えられる。
解法として、2重ループ形式で組んだ場合、
0-baseのまま処理した人は、
1,1,{1}　のような最小ケースで落ちる。
ループが多かったりすると、
5,3,{4}　のケースで、正しい答えは0なのに、1回カウントしてしまう。

一度ソートしてから範囲を定めてカウントする解法だと、
start<=day[i] && day[i]<=end
startとendの値に依るけど範囲少なかったり多かったりするミスもいくつか見られた。

kまで一度カウントしてから
sum += memo[i];
sum -= memo[i-k];
のように計算量O(N)のコードを書いてる人もいた。貪欲法っぽい
添え字ミスしてる人も見られた。

500問題は落としてる人が少ない。
落としてる人は偶数奇数で分ける処理のときに、コピペが原因で落ちてた。

撃墜時＆バグ混入に注意するときは、コーナーケースを常に意識したほうが良い。
次からのSRMの日記は、撃墜ケースとバグ発生ポイントについて書いて行くことにする。

システムテストやチャレンジで落ちてるかどうかの一覧は前回のSRMしか閲覧できない？
みたいなので、撃墜ケースは次のSRMまでには一通りやっておかないと復習するのに手間がかかるｗ

// 0-base  1,1,{1}
for(int i=0; i<n-k+1; i++)
   for(int j=i; j<i+k; j++)
      if( day[j] )cnt++;


// 1回ループが多い　 5,3,{4}
for(int i=1; i<=n-k+1; i++)
   for(int j=i; j<=i+k; j++)

250pt

The king and the queen want to go on a vacation together. Since the queen seldom asks for anything, the king is more than willing to reschedule his meetings if they conflict with the vacation.
The vacation must last for K contiguous days, and must lie between day 1 and day N inclusive. You are given int[] workingDays, where each element is a day on which the king has a meeting scheduled. The king will have at most one meeting scheduled per day. Return the minimum number of meetings that must be rescheduled so that the king and the queen can have a happy vacation.
俺得英単語memo
seldom めったに〜しない、ほとんど〜ない
conflict 衝突する（動詞)
contiguous 隣接する

struct VacationTime{ 
  int bestSchedule(int N, int K, vector <int> workingDays){ 
    int day[1001]; 
    int ret = 999999999; 
    memset(day,0,sizeof(day)); 
    rep(i,workingDays.size())day[workingDays[i]]=1; 
    for(int i=1; i<=N-K+1; i++){ 
      int cnt = 0; 
      for(int j=i; j<K+i; j++){ 
        if( day[j] )cnt++; 
      } 
      ret = min(ret,cnt); 
    } 
    return ret; 
  } 
};

500pt

The king is trying to find new ways to generate revenue, and he is currently exploring tourism as one potential avenue. The kingdom is a group of islands, and the amount of revenue that can be generated depends on the combined total length of beaches on all the islands.
You are given a String kingdom consisting of '.' or '#' characters. '#' represents a land mass, whereas '.' represents water. kingdom[i][j] represents a regular-hexagon shaped area with each side of unit length. Since the cells are hexagonal in shape, the odd-numbered rows (0-based) are 'shifted' towards the right. A beach is a segment which has water on one side, and land on the other.
An example String and the corresponding image are given below to illustrate. The beaches are marked in red.
{"..#.##",
".##.#.",
"#.#..."}
Return the combined total length of beaches on all the islands.
俺得英単語memo
revenue 収入
currently 現在
exploring 探索
tourism 観光
avenue 大通り

int dx1[] = {0,  1, 1, 1, 0, -1}; 
int dy1[] = {-1, -1, 0, 1, 1, 0}; 
int dx2[] = {0,  -1, -1, -1, 0, 1}; 
int dy2[] = {-1, -1,  0,  1, 1, 0}; 

struct Islands{ 
  int beachLength(vector <string> kingdom){ 
    int H = kingdom.size(); 
    int W = kingdom[0].size(); 
    int ret = 0; 
     
    rep(i,H){ 
      rep(j,W)if( kingdom[i][j]=='#' ){ 
        rep(k,6){ 
          int tx = j + (i%2 ? dx1[k] : dx2[k]); 
          int ty = i + (i%2 ? dy1[k] : dy2[k]); 
          if( tx<0 || ty<0 || tx>=W || ty>=H )continue; 
          if( kingdom[ty][tx]=='.' ){ 
            //printf("___k:%d  %d %d --> %d %d\n",k,j,i,tx,ty); 
            ret++; 
          } 
        } 
        //printf("%d %d : %d\n",j,i,ret); 
      } 
    } 
    return ret; 
  } 
};