ABC109 感想

色文字が感想の内容です

•  A問題

　a*bが偶数ならcを何にしてもa*b*cは偶数ですし,a*bが奇数ならc=1とすればa*b*cは奇数です。雨降ってる～

• B問題

　N個の文字列を要素に持つ配列をつくり、i番目の文字列の最後の文字とi+1番目の文字列の最初の文字が等しいかをすべて調べます。

　注意が必要なのは、(しりとりなので)同じ文字が２回登場するとダメなので、

• 2重ループをまわして調べる(O(N^2))

• sortしてcountする(O(NlogN))

• mapを使って出た文字を記録する(O(NlogN))

などをして確認します。同じ文字が2回登場しちゃダメなのを忘れて1WA,悲しい

• C問題

　スタート地点から各地点への距離を求め、最大公約数をとります。最大公約数を取る時なんですが、

1 int gcd(int a,int b){

2   if(a<b)swap(a,b);

3   while(b){

4     int r=a%b;a=b;b=r;

5   }

6   return a;

7 }

という関数をいつも書いてます。4行目が流れるように書けて好きなんですよね。

• D問題

　奇数個のところは動かして損はないので、どんどん掃きだしていくように、

→→→→→→→→→→→→→→→→→→→→→→→→↓

↓←←←←←←←←←←←←←←←←←←←←←←←←

→→→→→→→→→→→→→→→→→→→→→→→→↓

↓←←←←←←←←←←←←←←←←←←←←←←←←

...

と見ていき、偶数個なら放置、奇数個なら次のマスに1渡す、という操作をすると、無駄がなくてよいです。こういう問題、いつも操作回数を出力するのを忘れるので反省したいですね...(2WA)

• 全体的感想

　前回前々回の狂気ABCと比べ、標準的なABCだったと思います。twitterのタイムラインを見ていると、みんな楽しそうでした。