夢追い人

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

522Div2.Easyと523本番

522 Div.2 Easy

二点を選んだときその四角形の中に入る他の点の数の最大を求める。
やるだけ

class PointErasingTwo {
public:
   int getMaximum( vector <int> y ) {
    int result = 0;
    for (int i=0; i<y.size(); i++) {
        for (int j=i+1; j<y.size(); j++) {
            int large = max(y[i], y[j]), small = min(y[i], y[j]);
            int cnt = 0;
            for (int k=0; k<y.size(); k++) if (i<k&&k<j&&small<y[k]&&y[k]<large) cnt++;
            result = max(result, cnt);
        }
    }
    return result;
   }
};

523 Div.2 Easy

四近傍でアルファベット順にAから辿って行ったらZに辿りつけるかという問題。
単純なDFS。

class AlphabetPath {
public:
   bool solve(vector<string> maps, int x, int y) {
    int d[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
    if (maps[x][y]=='Z') return true;
    bool res = false;
    char nch = maps[x][y] + 1;
    for (int i=0; i<4; i++) {
        int nx = x + d[i][0], ny = y + d[i][1];
        if (nx>=0&&nx<maps.size()&&ny>=0&&ny<maps[0].length()&&maps[nx][ny]==nch) {
            res = solve(maps, nx, ny);
        }
    }
    return res;
   }
   string doesItExist( vector <string> letterMaze ) {
    for (int i=0; i<letterMaze.size(); i++) {
        for (int j=0; j<letterMaze[i].length(); j++) {
            if (letterMaze[i][j]=='A') {
                if (solve(letterMaze,i,j)) return "YES";
                else return "NO";
            }
        }
    }
   }
};

523 Div.2 Medium

a,b,c,d,x,y,upperBoundはすべて正の整数とする。
このときx,yを変化させた時1からupperBoundまででのa+bxとcdyの和集合の要素の数を求めよという問題。
色々と引っ掛け要素満載でこいつのせいでDiv.1もDiv.2もチャレンジ祭りになった。。。

ちなみに引っかかったので復讐で直したコード

class CountingSeries {
public:
   long long countThem( long long a, long long b, long long c, long long d, long long upperBound ) {
    ll res = 0;
    if (upperBound>=a) res += (upperBound-a)/b+1;
    if (upperBound>=c) {
        ll temp = c;
        for (int i=0;; i++) {
            if (temp<a||(temp-a)%b!=0) res++;
            temp *= d;
            if (d == 1) break;
            if (temp>upperBound) break;
        }
    }
    return res;
   }
};

523 Div.2 Hard

ブロックの問題
明らかにDPなんだけど時間もなく漸化式立てられずおわった。

結果

oxx 828 -> 896
焦らされたorz