AtCoder Beginner Contest 109 に出場した

はじめに

こんばんはtikedaです。先週の9/8(土)にAtCoderのABC109が開催されたので、久々に出場しました。
最近、競プロのモチベがダダ↓↓↓だったのですが、@chokudaiさんにtweet(以下参照)を「いいね！」されてしまい、出ることに...

もちべあがってきた
今日はAtCoderでるぞい
— tikeda🐾 (@tikeda_meu) September 8, 2018

しかし今回は初めて全完できたので、ドヤ顔して記事を書くことができるのである(は?)

A

問題は以下を参照。
A - ABC333

AとBをかけたものが奇数か偶数かで判定すればよい。

僕のコードは以下で、ACを得た。

//#include <bits/stdc++.h>
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <climits>
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define ROF(i, j, k) for(int i = (int)(j); i >= (int)(k); --i)
#define FORLL(i, n, m) for(long long i = n; i < (long long)(m); i++)
#define SORT(v, n) sort(v, v+n)
#define REVERSE(v) reverse((v).begin(), (v).end())

using namespace std;
using ll = long long;
const ll MOD=1000000007LL;
typedef pair<int, int> P;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }

int
main(void){  
  int a, b;
  cin >> a >> b;

  if( (a*b)%2 == 0){
    cout << "No" << endl;
  }
  else{
    cout << "Yes" << endl;
  }
 
  return 0;
}

B

問題は以下を参照。
B - Shiritori

Bのくせに案外難しいめうと思ったが、map使って数える + 文字列のお尻と次の文字列の頭が一致しているか判定するのをすぐ思いつき実装した。実装に、ちょっと時間かかったのが残念なところ。

//#include <bits/stdc++.h>
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <climits>
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define ROF(i, j, k) for(int i = (int)(j); i >= (int)(k); --i)
#define FORLL(i, n, m) for(long long i = n; i < (long long)(m); i++)
#define SORT(v, n) sort(v, v+n)
#define REVERSE(v) reverse((v).begin(), (v).end())

using namespace std;
using ll = long long;
const ll MOD=1000000007LL;
typedef pair<int, int> P;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }

map<string, int> mp;

int
main(void){  
  int n;
  cin >> n;
  string s[n];
  
  string p_s;
  int p_s_l;

  REP(i, n) cin >> s[i];
  
  REP(i, n){
    if( i > 0 && p_s[p_s_l-1] != s[i][0]){
      cout << "No" << endl;
      return 0;
    }    
    //cout << p_s[p_s_l - 1] << endl;    
    if(mp[s[i]] == 0){
      mp[s[i]]++;
    }
    else{
      cout << "No" << endl;
      return 0;
    }
    p_s = s[i];
    p_s_l = p_s.length();
  }
  cout << "Yes" << endl;
  return 0;
}

C

問題は以下を参照。
C - Skip

個人的に一番時間をかけてしまった問題で、難しかっためう + 1WA。はじめは愚直にシミュレーションしてみた。Xから各y_iに対して距離(差の絶対値)を計算し、ソートした後に、最も近い距離をDの最大値として1ずつ減らしながらシミュレーションを行った。このやり方でACしたという話も聞いたので、自分の実装力の無いが故にどこかしらでバグってWAとなったと思われる。ここで諦めて頭をつかうことにした。先程の距離を計算する際に、Xと各y_iの距離らの最大公約数が解となることに気づいたので、そのように実装したらACをした。コーナーケースと思われるn=1の時は、単純にy_0とXの差の絶対値を取るだけで良いので、そのように実装した。

//#include <bits/stdc++.h>
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <climits>
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define ROF(i, j, k) for(int i = (int)(j); i >= (int)(k); --i)
#define FORLL(i, n, m) for(long long i = n; i < (long long)(m); i++)
#define SORT(v, n) sort(v, v+n)
#define REVERSE(v) reverse((v).begin(), (v).end())

using namespace std;
using ll = long long;
const ll MOD=1000000007LL;
typedef pair<int, int> P;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }

ll gcd( ll m, ll n )
{
    if ( ( 0 == m ) || ( 0 == n ) ) return 0;
    while( m != n )
    {
        if ( m > n ) m = m - n;
        else  n = n - m;
    }
    return m;
}

ll lcm(ll a, ll b){
  if( (a==0) || (b==0)) return 0;

  return (a/gcd(a,b)*b);
}

int
main(void){  
  int n;
  cin >> n;
  ll X;
  cin >> X;
  
  ll x[n];
  ll s_x[n+1];

  REP(i, n){
    cin >> x[i];
    s_x[i] = x[i];
  }
  s_x[n] = X;  
  
  if(n == 1){
    cout << abs(x[0]-X) << endl;
    return 0;
  }
  
  SORT(s_x, n+1);
  SORT(x, n);

  ll diff[n];
  REP(i, n){
    diff[i] = s_x[i+1]-s_x[i];
    //cout << diff[i] << endl;
  }

  REP(i, n-1){
    diff[i+1] = gcd(diff[i], diff[i+1]);
    //cout << diff[i+1] << endl;
  }

  cout << diff[n-1] << endl;

  return 0;
}

D

問題は以下を参照。
D - Make Them Even

問題を読んだときに、いつかABCのC問題辺りでやったリバーシを思い出した。(問題がいつか忘れた。) 解法はいくつか存在するが、僕は以下のように解いた。

左端から右端を除く列へ、そのマスが奇数であれば-1, 右隣りのマスを+1する。
右端の列を上から下へ、そのマスが奇数であれば-1, 下のマスを+1する。

図解すると以下のようになる。

→→↓
→→↓
→→○

これでもWAをくらってしまったのだが、出力の際に行数nを入れ忘れたのが原因である。
許すまじn。

コードは以下。

//#include <bits/stdc++.h>
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <climits>
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define ROF(i, j, k) for(int i = (int)(j); i >= (int)(k); --i)
#define FORLL(i, n, m) for(long long i = n; i < (long long)(m); i++)
#define SORT(v, n) sort(v, v+n)
#define REVERSE(v) reverse((v).begin(), (v).end())

using namespace std;
using ll = long long;
const ll MOD=1000000007LL;
typedef pair<int, int> P;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }

int a[575][575];

int ans1[250000];
int ans2[250000];
int ans3[250000];
int ans4[250000];

int
main(void){  
  int H, W, itr=0;
  cin >> H >> W;

  REP(i, H){
    REP(j, W){
      cin >> a[i][j];
    }
  }

  REP(i, H){
    REP(j, W-1){
      if(a[i][j]%2 != 0){
    a[i][j]--;
    a[i][j+1]++;
    //cout << i+1 << " " << j+1 << " " << i+1 << " " << j+2 << endl;
    ans1[itr] = i+1;
    ans2[itr] = j+1;
    ans3[itr] = i+1;
    ans4[itr] = j+2;
    itr++;
      }
    }
  }

  REP(i, H-1){
    if(a[i][W-1]%2 != 0){
      a[i][W-1]--;
      a[i+1][W-1]++;
      //cout << i+1 << " " << W << " " << i+2 << " " << W << endl;
      ans1[itr] = i+1;
      ans2[itr] = W;
      ans3[itr] = i+2;
      ans4[itr] = W;
      itr++;      
    }
  }

  cout << itr << endl;
  REP(i, itr){
    cout << ans1[i] << " " << ans2[i] << " " << ans3[i] << " " << ans4[i] << endl;
  }
  
  return 0;
}

最後に

ここまで見てくださってありがとうございました。参加が5回目？か6回目？ぐらいでようやっと茶色の半分に到達しました。まずは水色になれるよう精進します。めう。それにしてもモチベーションが維持できないのでPaizaの問題でも解こうかな...辛い

motacaplaのめう

日頃得られた知見と気付きをdumpするところ

AtCoder Beginner Contest 109 に出場した

はじめに

A

B

C

D

最後に