Asa's Blog

AHC003

Tags: AtCoder  AHC  Competitive-Programming 

Published on 2021.06.01. Last Modified on 2020.06.10.

ABC203 に引き続き、AHC003を振り返ります。

問題概要

  • クエリが1000個与えられるので、30x30のグラフで、最短経路を予測。
  • 出力したら flush しないと TLE になる。
  • 出力されたら[出力されたパスの長さ $ b_k $ × 乱数(0.9~1.1) $ e_k $ ]が標準入力に入る。
  • 同じところを何回も通ったり、はみ出したり、ちゃんとゴールにつけてなかったりすると WA で0点。
  • 得点は、 $ \mathrm{round}(2312311\times \sum_{k=1}^{1000}0.998^{1000-k} \frac{a_k}{b_k}) $ 。なお、最短経路が $ a_k $ で、出力パスが $ b_k $ 。
  • 実行時間制限は 2sec、メモリ制限は1024MB。
  • 暫定テストでは100個のテストケース。1つ当たり $ 10^9 $ 点で、 満点は $ 10^{11} $ 点。

実装してみる

一応 こちらから 私の実装を見れます。

エイリアス定義など

私は main() 関数前に以下の定義をしています。型宣言等でわからないところがあったら参照していただければ。

#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ull1d = vector<ull>;
using ull2d = vector<ull1d>;
using ull3d = vector<ull2d>;
#define loop(i,n) for(ull i=0;i<n;i++)
#define rloop(i,n) for(ll i=n-1;i>=0;i--)
#define all(vec) vec.begin(),vec.end()

試しにとりあえず直線的に移動する

提出 #22779476 - AtCoder Heuristic Contest 003
とにかく同じ行になるまで上下どっちかに移動して、そのあとゴールへ一直線する寸法です。とりあえず出力後に入る $ b_k \times e_k $ は無視します。

int main(){
  loop(b,1000){
    ll sx,sy,tx,ty; cin >> sy >> sx >> ty >> tx;
    string res = "";
    if(sy > ty){ loop(c,sy-ty){ res+="U"; } }
    if(sy < ty){ loop(c,ty-sy){ res+="D"; } }
    if(sx > tx){ loop(c,sx-tx){ res+="L"; } }
    if(sx < tx){ loop(c,tx-sx){ res+="R"; } }
    cout << res << endl;
    fflush(stdout);
    ll point; cin >> point;
  }
  return 0;
}

これで 63,179,310,956 点得られました。これでも63%とれるみたいです。

$ b_k \times e_k $ を使う

提出 #22783808 - AtCoder Heuristic Contest 003
$ b_k \times e_k $ は実質経路の長さなので、最短経路を求めるにはこれを使わないわけにはいかないという。

string res = "";
ull x,y;
void move(char mode){
  switch (mode){
    case 'U': res += "U"; y--; break;
    case 'D': res += "D"; y++; break;
    case 'L': res += "L"; x--; break;
    case 'R': res += "R"; x++; break;
  }
  return;
}

ull3d Graph(30,ull2d(30,ull1d(4,0)));
// Graph[i][j] = {Up, Down, Left, Right}

int main(){
  loop(b,1000){
    ll sx,sy,tx,ty; cin >> sy >> sx >> ty >> tx;
    res = "";
    x = sx, y=sy;
    while(y!=ty || x!=tx){
      ull1d now = Graph[y][x];
      if(y==ty && x>tx){ loop(c,x-tx){ move('L'); } }
      else if(y==ty && x<tx){ loop(c,tx-x){ move('R'); } }
      else if(x==tx && y>ty){ loop(c,y-ty){ move('U'); } }
      else if(x==tx && y<ty){ loop(c,ty-y){ move('D'); } }
      else if(x>tx && y>ty){
        if(now[0] == 0){ move('U'); } else if(now[2] == 0){ move('L'); }
        else if(now[0] < now[2]){ move('U'); } else{ move('L'); }
      }
      else if(x>tx && y<ty){
        if(now[1] == 0){ move('D'); } else if(now[2] == 0){ move('L'); }
        else if(now[1] < now[2]){ move('D'); } else{ move('L'); }
      }
      else if(x<tx && y>ty){
        if(now[0] == 0){ move('U'); } else if(now[3] == 0){ move('R'); }
        else if(now[0] < now[3]){ move('U'); } else{ move('R'); }
      }
      else if(x<tx && y<ty){
        if(now[1] == 0){ move('D'); } else if(now[3] == 0){ move('R'); }
        else if(now[1] < now[3]){ move('D'); } else{ move('R'); }
      }
    }
    cout << res << endl;
    fflush(stdout);

    ull point; cin >> point;
    point /= res.size();
    x = sx, y=sy;
    loop(i,res.size()){
      switch(res[i]){
        case 'U':
          Graph[y][x][0] = max(Graph[y][x][0], point);
          Graph[y-1][x][1] = max(Graph[y-1][x][1], point);
          y--;
          break;
        case 'D':
          Graph[y][x][1] = max(Graph[y][x][1], point);
          Graph[y+1][x][0] = max(Graph[y+1][x][0], point);
          y++;
          break;
        case 'L':
          Graph[y][x][2] = max(Graph[y][x][2], point);
          Graph[y][x-1][3] = max(Graph[y][x-1][3], point);
          x--;
          break;
        case 'R':
          Graph[y][x][3] = max(Graph[y][x][3], point);
          Graph[y][x+1][2] = max(Graph[y][x+1][2], point);
          x++;
          break;
      }
    }
  }
  return 0;
}

ここで何をしているかというと、

  1. すべての地点に対して上下左右の経路を0で初期化
  2. 自分がゴール地点にいない限り、今ゴールの左上にいるなら、右か下の経路の短いほうへ行く。右上なら左か下、左下なら右か上、右下なら左か上、といった具合に移動。
  3. 出力し、すぐに flush する
  4. 得点を歩数で割って、各経路に max(経路, 得点÷歩数) を代入する。訪れていない場合、(経路)=0となっているため、必ず[得点÷歩数]が入る仕組み。
  5. 繰り返し…

これだと 69,388,118,612 点。得点率は6%くらい上がりました。

全探索してみる

提出 #22787318 - AtCoder Heuristic Contest 003
もっと得点ほしい!!ってなったので、1歩先ではなく、ある程度先まで読める全探索でやってみます。

ull3d Graph(30,ull2d(30,ull1d(4,0)));
// Graph[i][j] = {Up, Down, Left, Right}

ull leng(string mode, ull x, ull y){
  ull ret = 0;
  loop(i,mode.size()){
    switch(mode[i]){
      case 'U':
        if(Graph[y][x][0] != 0){ ret += Graph[y][x][0]; }
        else{ ret += 10000; }
        y--;
        break;
      case 'D':
        if(Graph[y][x][1] != 0){ ret += Graph[y][x][1]; }
        else{ ret += 10000; }
        y++;
        break;
      case 'L':
        if(Graph[y][x][2] != 0){ ret += Graph[y][x][2]; }
        else{ ret += 10000; }
        x--;
        break;
      case 'R':
        if(Graph[y][x][3] != 0){ ret += Graph[y][x][3]; }
        else{ ret += 10000; }
        x++;
        break;
    }
  }
  return ret;
}

int main(){
  loop(b,1000){
    ll sx,sy,tx,ty; cin >> sy >> sx >> ty >> tx;
    string res = "";
    ll x = sx, y=sy;
    while(x!=tx || y!=ty){
      if(y==ty && x>tx){ loop(c,x-tx){ res += "L"; x--; } }
      else if(y==ty && x<tx){ loop(c,tx-x){ res += "R"; x++; } }
      else if(x==tx && y>ty){ loop(c,y-ty){ res += "U"; y--; } }
      else if(x==tx && y<ty){ loop(c,ty-y){ res += "D"; y++; } }
      else{
        string best = ""; ll nx,ny; ull bestRoute=0;
        int bitLoop = min((ll)8,min(abs(x-tx),abs(y-ty)));
        loop(i,1<<bitLoop){
          string mode = ""; ll mx=0,my=0;
          if(x>tx && y>ty){
            // U or L
            loop(j,bitLoop){
              if(i & 1<<j){ mode += "U"; my--; }
              else{ mode += "L"; mx--; }
            }
          }
          else if(x>tx && y<ty){
            // D or L
            loop(j,bitLoop){
              if(i & 1<<j){ mode += "D"; my++; }
              else{ mode += "L"; mx--; }
            }
          }
          else if(x<tx && y>ty){
            // U or R
            loop(j,bitLoop){
              if(i & 1<<j){ mode += "U"; my--; }
              else{ mode += "R"; mx++; }
            }
          }
          else{
            // D or R
            loop(j,bitLoop){
              if(i & 1<<j){ mode += "D"; my++; }
              else{ mode += "R"; mx++; }
            }
          }
          ull tmpL = leng(mode,x,y);
          if(tmpL > bestRoute){
            bestRoute = tmpL;
            best = mode;
            nx = mx; ny = my;
          }
        }
        res += best;
        x += nx; y += ny;
      }
    }
    cout << res << endl;

    fflush(stdout);
    ull point; cin >> point;
    point /= res.size();
    x = sx, y=sy;
    loop(i,res.size()){
      switch(res[i]){
        case 'U':
          Graph[y][x][0] = max(Graph[y][x][0], point);
          Graph[y-1][x][1] = max(Graph[y-1][x][1], point);
          y--;
          break;
        case 'D':
          Graph[y][x][1] = max(Graph[y][x][1], point);
          Graph[y+1][x][0] = max(Graph[y+1][x][0], point);
          y++;
          break;
        case 'L':
          Graph[y][x][2] = max(Graph[y][x][2], point);
          Graph[y][x-1][3] = max(Graph[y][x-1][3], point);
          x--;
          break;
        case 'R':
          Graph[y][x][3] = max(Graph[y][x][3], point);
          Graph[y][x+1][2] = max(Graph[y][x+1][2], point);
          x++;
          break;
      }
    }
  }
  return 0;
}

これで $ \min(8, \vert x-tx \vert , \vert y-ty \vert) $ 歩先まで読んで、一番経路が短い(と思っていた)ものを求めます。
同じ行・列になった場合、ゴールまで直進します。
訪れていない場合は、経路を10,000に設定して、優先的に選ばれるようにしています。

結果、52,326,846,043 点。落ちてるやん。
9歩先を読んでも、61,387,035,970 点。

そして気づく

「あっ。最短経路を求めるやつやん。なんで訪れてない場合10,000にして経路長いほう選んでるんだ…。」

提出 #22842801 - AtCoder Heuristic Contest 003
で訂正(したつもり)。

ull3d Graph(30,ull2d(30,ull1d(4,0)));
// Graph[i][j] = {Up, Down, Left, Right}

ull leng(string mode, ull x, ull y, ull tx, ull ty){
  ull ret = 0;
  loop(i,mode.size()){
    switch(mode[i]){
      case 'U':
        if(y<=ty){ return 1e10; }
        else if(Graph[y][x][0] != 0){ ret += Graph[y][x][0]; }
        y--;
        break;
      case 'D':
        if(y>=ty){ return 1e10; }
        else if(Graph[y][x][1] != 0){ ret += Graph[y][x][1]; }
        y++;
        break;
      case 'L':
        if(x<=tx){ return 1e10; }
        else if(Graph[y][x][2] != 0){ ret += Graph[y][x][2]; }
        x--;
        break;
      case 'R':
        if(x>=tx){ return 1e10; }
        else if(Graph[y][x][3] != 0){ ret += Graph[y][x][3]; }
        x++;
        break;
    }
  }
  return ret;
}

int main(){
  double prevScore = 0;
  loop(b,1000){
    // 省略
    fflush(stdout);
    ull point; cin >> point;
    double tmpScore = point;
    point = 1e10 - (point - (prevScore/0.998));
    point /= res.size();
    prevScore = tmpScore;
    x = sx, y=sy;
    loop(i,res.size()){
      switch(res[i]){
        case 'U':
          Graph[y][x][0] = max(Graph[y][x][0], point);
          Graph[y-1][x][1] = max(Graph[y-1][x][1], point);
          y--;
          break;
        case 'D':
          Graph[y][x][1] = max(Graph[y][x][1], point);
          Graph[y+1][x][0] = max(Graph[y+1][x][0], point);
          y++;
          break;
        case 'L':
          Graph[y][x][2] = max(Graph[y][x][2], point);
          Graph[y][x-1][3] = max(Graph[y][x-1][3], point);
          x--;
          break;
        case 'R':
          Graph[y][x][3] = max(Graph[y][x][3], point);
          Graph[y][x+1][2] = max(Graph[y][x+1][2], point);
          x++;
          break;
      }
    }
  }
  return 0;
}

10歩先を読んでも、61,387,035,970 点。
入力される得点をなぜか point = 1e10 - (point - (prevScore/0.998)) としていたため、実質的には最長経路を求めることになり、あまり伸びず…。

平均値をとってみる

提出 #22907260 - AtCoder Heuristic Contest 003
入力は $ b_k \times e_k $ であることに気付いたため、先ほどの部分を削除。$ \max $ 関数だと外れ値に当たった時怖いな…と考えて、相加平均をとることにしました。

ull3d Graph(30,ull2d(30,ull1d(4,0)));
// Graph[i][j] = {Up, Down, Left, Right}

ull leng(string mode, ull x, ull y, ull tx, ull ty){
  ull ret = 0;
  loop(i,mode.size()){
    switch(mode[i]){
      case 'U':
        if(y<=ty){ return 1e10; }
        else if(Graph[y][x][0] != 0){ ret += Graph[y][x][0]; }
        y--;
        break;
      case 'D':
        if(y>=ty){ return 1e10; }
        else if(Graph[y][x][1] != 0){ ret += Graph[y][x][1]; }
        y++;
        break;
      case 'L':
        if(x<=tx){ return 1e10; }
        else if(Graph[y][x][2] != 0){ ret += Graph[y][x][2]; }
        x--;
        break;
      case 'R':
        if(x>=tx){ return 1e10; }
        else if(Graph[y][x][3] != 0){ ret += Graph[y][x][3]; }
        x++;
        break;
    }
  }
  return ret;
}

int main(){
  loop(b,1000){
    ll sx,sy,tx,ty; cin >> sy >> sx >> ty >> tx;
    string res = "";
    ll x = sx, y=sy;
    while(x!=tx || y!=ty){
      if(y==ty && x>tx){ loop(c,x-tx){ res += "L"; x--; } }
      else if(y==ty && x<tx){ loop(c,tx-x){ res += "R"; x++; } }
      else if(x==tx && y>ty){ loop(c,y-ty){ res += "U"; y--; } }
      else if(x==tx && y<ty){ loop(c,ty-y){ res += "D"; y++; } }
      else{
        string best = ""; ll nx,ny; ull bestRoute=1e10;
        int bitLoop = min((ll)10, abs(x-tx)+abs(y-ty));
        loop(i,1<<bitLoop){
          string mode = ""; ll mx=0,my=0;
          if(x>tx && y>ty){
            // U or L
            loop(j,bitLoop){
              if(i & 1<<j){ mode += "U"; my--; }
              else{ mode += "L"; mx--; }
            }
          }
          else if(x>tx && y<ty){
            // D or L
            loop(j,bitLoop){
              if(i & 1<<j){ mode += "D"; my++; }
              else{ mode += "L"; mx--; }
            }
          }
          else if(x<tx && y>ty){
            // U or R
            loop(j,bitLoop){
              if(i & 1<<j){ mode += "U"; my--; }
              else{ mode += "R"; mx++; }
            }
          }
          else{
            // D or R
            loop(j,bitLoop){
              if(i & 1<<j){ mode += "D"; my++; }
              else{ mode += "R"; mx++; }
            }
          }
          ull tmpL = leng(mode,x,y,tx,ty);
          if(tmpL < bestRoute){
            bestRoute = tmpL;
            best = mode;
            nx = mx; ny = my;
          }
        }
        res += best;
        x += nx; y += ny;
      }
    }
    cout << res << endl;

    fflush(stdout);
    ull point; cin >> point;
    point /= res.size();
    x = sx, y=sy;
    loop(i,res.size()){
      switch(res[i]){
        case 'U':
          Graph[y][x][0] = (Graph[y][x][0] + point)/2;
          Graph[y-1][x][1] = (Graph[y-1][x][1] + point)/2;
          y--;
          break;
        case 'D':
          Graph[y][x][1] = (Graph[y][x][1] + point)/2;
          Graph[y+1][x][0] = (Graph[y+1][x][0] + point)/2;
          y++;
          break;
        case 'L':
          Graph[y][x][2] = (Graph[y][x][2], point)/2;
          Graph[y][x-1][3] = (Graph[y][x-1][3], point)/2;
          x--;
          break;
        case 'R':
          Graph[y][x][3] = (Graph[y][x][3], point)/2;
          Graph[y][x+1][2] = (Graph[y][x+1][2], point)/2;
          x++;
          break;
      }
    }
  }
  return 0;
}

ゴール地点の座標を超えていた場合、経路の長さを $ 10^{10} $ にすることで選ばれないようにして、経路長さ更新は相加平均 $ {a+b} \over 2 $ にしてみました。
10歩先を読んで、73,881,366,834 点。爆上がりしました。
あとは実行時間制限とのチキンレース。10歩で288msだったので、実行時間ギリギリを攻めます。
11歩で 74,551,308,026 点(550ms)、12歩で 75,212,574,804 点(970ms)、13歩で 76,004,221,978 点(1969ms)。
本番で TLE になったら怖いので、12歩にロールバックしました。

またも気づく

経路長さの更新時、

  switch(res[i]){
    case 'U':
      Graph[y][x][0] = (Graph[y][x][0] + point)/2;
      Graph[y-1][x][1] = (Graph[y-1][x][1] + point)/2;
      y--;
      break;
    case 'D':
      Graph[y][x][1] = (Graph[y][x][1] + point)/2;
      Graph[y+1][x][0] = (Graph[y+1][x][0] + point)/2;
      y++;
      break;
    case 'L':
      Graph[y][x][2] = (Graph[y][x][2], point)/2;
      Graph[y][x-1][3] = (Graph[y][x-1][3], point)/2;
      x--;
      break;
    case 'R':
      Graph[y][x][3] = (Graph[y][x][3], point)/2;
      Graph[y][x+1][2] = (Graph[y][x+1][2], point)/2;
      x++;
      break;
  }

としていました。

「あっ、LR の場合の処理、正しく書けてないやん…」

提出 #23020247 - AtCoder Heuristic Contest 003
これを訂正して、12歩先を読んで、81,150,992,107 点(1084ms)。夢の8割に到達…!

相乗平均をとってみる

提出 #23020788 - AtCoder Heuristic Contest 003
何を思ったか、 相乗平均をとってみました。

switch(res[i]){
  case 'U':
    Graph[y][x][0] = sqrt(Graph[y][x][0])*sqrt(point);
    Graph[y-1][x][1] = sqrt(Graph[y-1][x][1])*sqrt(point);
    y--;
    break;
  case 'D':
    Graph[y][x][1] = sqrt(Graph[y][x][1])*sqrt(point);
    Graph[y+1][x][0] = sqrt(Graph[y+1][x][0])*sqrt(point);
    y++;
    break;
  case 'L':
    Graph[y][x][2] = sqrt(Graph[y][x][2])*sqrt(point);
    Graph[y][x-1][3] = sqrt(Graph[y][x-1][3])*sqrt(point);
    x--;
    break;
  case 'R':
    Graph[y][x][3] = sqrt(Graph[y][x][3])*sqrt(point);
    Graph[y][x+1][2] = sqrt(Graph[y][x+1][2])*sqrt(point);
    x++;
    break;
}

オーバーフローのことを一応考えて、それぞれについて sqrt してます。
結果、62,207,792,606 点。経路長を0で初期化したことが原因のようです。
1で初期化するよう訂正した結果、77,153,634,281 点。相加平均には敵わず…。
相加平均にロールバックしました。

そして終了…。

結果

3,000件あるテストケースで、それぞれについて1,000,000,000 ( $ 10^9 $ ) 点が満点になるので、全部の満点は $ 3.0 \times 10^{12} $ になります。
そして私が得た得点は、2,442,902,260,623 点。81.4%の得点率で、519位でした。
8割得点しましたが、未提出者(0点)で860位なので半分以下みたいです。

(2021.06.08追記)Perfは1309で、レーティング(β)は307→644と、+337でした。
https://www.dropbox.com/s/sf66bk4vizdnqmf/result_ahc003.csv?dl=0

(2021.06.10追記)システムリジャッジが終了した結果、得点は変わらず、520位に。Perfは1308と1下がりましたが、新レーディングは変わらず+337で644のようです。

もっと問題文を理解できるようにしたりアルゴリズムを学んだりして、ABCはもちろんAHCでも高得点を狙っていきたいですね…。

AHCは、とにかく Try & Error してみるのが重要なのかも。

keyboard_arrow_up