C - タイル (Tile)

f:id:peroon:20200220021433p:plain

Quiz

https://atcoder.jp/contests/joi2011yo/tasks/joi2011yo_c

AC Code

https://atcoder.jp/contests/joi2011yo/submissions/10218261

Code (抜粋)

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    // input
    ll N; 
    cin >> N;
 
    ll Q;cin>>Q;
    while(Q--){
      ll x,y;cin>>x>>y;
      x--;y--;
      
      if(x>N/2){
        x = N-1-x;
      }
      if(y>N/2){
        y = N-1-y;
      }
 
      if(x>y) swap(x,y);
 
      if(x%3==0){
        p(1);
      }else if(x%3==1){
        p(2);
      }else{
        p(3);
      }
    }   
    return 0;
}

解法

  • 対称性を利用すると、全ての点は左上の領域に移動しても色が変わらない
  • x, yを入れ替えても色は変わらないので、x<=yとなるように移動してよい
  • このように移動した後は考えるパターン数が減るのでコードがシンプルになる