文系ギャルが0から始める競技プログラミング#18

Intro

この記事は不定期連載です。
↓最初の一本はこちら↓
文系ギャルが0から始める競技プログラミング#0

↓直前の記事はこちら↓
文系ギャルが0から始める競技プログラミング#17

・ABC086C

AtCoder Beginners Selectionのラスト！！！！
ついに終わりました。

めっちゃぐぐったりヘルプを出したりしながら出てきたことを覚えていくスタイルを取っていたので…めちゃめちゃ勉強になりました。

というわけでラスト行ってみたいと思います！

問題文
シカのAtCoDeerくんは二次元平面上で旅行をしようとしています。
AtCoDeerくんの旅行プランでは、時刻0に点(0,0)を出発し、1以上N以下の各iに対し、時刻tiに点(xi,yi)を訪れる予定です。
AtCoDeerくんが時刻tに点(x,y)にいる時、時刻t+1には点(x+1,y),(x−1,y),(x,y+1),(x,y−1)のうちいずれかに存在することができます。
その場にとどまることは出来ないことに注意してください。
AtCoDeerくんの旅行プランが実行可能かどうか判定してください。

制約
1≤N≤10^5
0≤xi≤10^5
0≤yi≤10^5
1≤ti≤10^5
ti<ti+1(1≤i≤N−1)
入力は全て整数

入力
入力は以下の形式で標準入力から与えられる。
N
t1 x1 y1
t2 x2 y2
:
tN xN yN

出力
旅行プランが実行可能ならYesを、不可能ならNoを出力してください。

―ABC086C - Traveling

シカのAtCoDeerくんだって旅行しているというのに、ライブDVD見ながらGW引きこもってるわたしです。

た、楽しいもん！

問題を整理します。
AtCoDeerくんは(0,0)をスタートし１（秒？時間？）に１進むっぽいことがわかります。

１しか移動できないので、
①目的地に対して時間がなさすぎるパターン…(≒素人の北海道旅行みたいなプラン)はNGだし、
②うろうろしても時間と目的地が合わないパターンもNGです。
①を見つけるのは簡単として、②はどうしてやろうか…というところで試行錯誤。
時間が偶数のときは、位置（距離？）も偶数だと気付きました。
うろうろしてもたどり着かないパターンは、これで説明がつきそうです。

①、②それぞれの条件を判定し、"No"と出力したあとgotoを使って全部すっ飛ばす処理を思いつきます。

①

if(x[i]+y[i]>t[i]){
           cout << "No" << endl;
           goto out;

②

}else{
           if(t[i]%2==0){
               if((x[i]+y[i])%2!=0){
                   cout << "No" << endl;
                   goto out;
               }
           }else{
               if((x[i]+y[i])%2==0){
                   cout << "No" << endl;
                   goto out;
               }

（Yes/Noで出力しなきゃいけないのにYES/NOで出しててハマった）
gotoはスパゲッティ化するから使わないほうがいいっていうのが世の意見っぽいですね。。。気をつけよう。

ループを元気に飛び越える能力が欲しくてググってたらgotoっていうの出てきたから使ったけど、人によっては絶対使うなクソってテンションなのなんで？使わないほうが良いの？

— マリー (@CBOX360) April 28, 2019

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
   int N;
   cin >> N;
   
   int t[100000] = {};
   int x[100000] = {};
   int y[100000] = {};
   t[0] = 0;
   x[0] = 0;
   y[0] = 0;
   
   for(int i=1;i<=N;i++){
       cin >> t[i] >> x[i] >> y[i];
       
       if(x[i]+y[i]>t[i]){
           cout << "No" << endl;
           goto out;
       }else{
           if(t[i]%2==0){
               if((x[i]+y[i])%2!=0){
                   cout << "No" << endl;
                   goto out;
               }
           }else{
               if((x[i]+y[i])%2==0){
                   cout << "No" << endl;
                   goto out;
               }
               
           }
       }
   }
   
   
   cout << "Yes" << endl;
out:
   return 0;
}

はい！優勝！優勝ギャルですよ！！！
天才ギャル！！！！ひゃふーーーー！

けんちょんさんの元記事から、例題を中心にバリバリ解いていこうと思います！
目指せ全完ギャル！のまえに着色〜〜〜！

Outro

#19に続く！(不定期連載です。)

これは成功と挫折を繰り返し、
タピオカ片手に難問を解く、
ギャルプログラマが生まれるまでの物語である…。