AtCoder Beginner Contest 135 - zeronosu77108’s blog

A,B,C の3完でした．今回はペナルティーも多いしとても酷い…

f:id:zeronosu77108:20190729232834p:plain

A - Harmony

$A$ と $B$ のちょうど間の数字が $\mid A - K \mid = \mid B - K \mid$ になる数字なので，
$A$ と $B$ の和が偶数のときは解があって，そうでないときは IMPOSSIBLE となる．

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

long long main() {
  long long a,b;
  cin >> a >> b;
  if ( (a+b) %2==0) {
    cout << (a+b)/2 << endl;
  } else {
    cout << "IMPOSSIBLE" << endl;
  }
}

B - 0 or 1 Swap

問題文

「0回か1回の swap で昇順にすることができますか？」っていう問題．
$\{1,2,3,\cdots,N\}$ なので，入力を取りながら，何個 i と異なるかを数えておいて，それが2より大きければ 1回以下の swap では昇順にすることができません．

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

long long main() {
  long long n;
  cin >> n;
  long long count=0;

  for(long long i=1; i<=n; i++) {
    long long t;
    cin >> t;
    if(t != i) count++;
  }

  cout << (count>2 ? "NO" : "YES") << endl;
}

C - City Savers

問題文

$A _1$ と $A _ {N+1}$ がループしていないので，
前（もしくは後ろ）から全力で倒していけば良いです．

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
  long long n;
  long long ans=0;
  cin >> n;
  vector<long long> a(n+1);
  for(long long i=0; i<=n; i++) cin >> a[i];

  for(long long i=0; i<n; i++) {
    long long b;
    cin >> b;

    if(a[i] <= b) {
      ans += a[i];
      b -= a[i];
    } else {
      ans += b;
      b=0;
    }

    if(a[i+1] <= b) {
      ans += a[i+1];
      a[i+1]=0;
    } else {
      ans += b;
      a[i+1] -= b;
    }

  }
  cout << ans << endl;
}

D - Digits Parade

問題文

時間内に解けずに F 問題に手を出していました(もちろん F 問題は解けていません)．

解説を読もうと思ったら， DP と書いていたので，解けるかも！と考えたら，解けました．
かけ算と足し算はどのタイミングで mod 取っても良いので，位ごとに mod を取って DP できそうだなと思いました．

例えば， $44 \bmod 13$ の場合， $( ( 4 \ast 10 \bmod 13) + (4 \bmod 13)) \bmod 13$ みたいなことをしても言い訳ですね．

ということは，下位（もしくは上位）桁から 13 で割った余りがどこに行くかで DP を取っていけば良いと．

時間内に気がつきたかった…

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <string>


using namespace std;

const int mod = 1000000007;


int main() {
  string s;
  int dp[100005][13];
  cin >> s;
  int n = s.size();
  reverse(s.begin(),s.end());
  cout << s << endl; 

  int digit=1;
  dp[0][0] = 1;
  for(int i=0; i<n; i++) {

    // 未確定のとき
    if(s[i] == '?') {
      for(int d=0; d<10; d++) {
        for(int j=0; j<13; j++) {
          dp[i+1][(d*digit + j)%13] += dp[i][j];
          dp[i+1][(d*digit + j)%13] %= mod;
        }
      }
    } 
    // 確定しているとき
    else {
        int d = (s[i] - '0'); // 数値に変換
        for(int j=0; j<13; j++) {
          dp[i+1][(d*digit + j)%13] += dp[i][j];
          dp[i+1][(d*digit + j)%13] %= mod;
        }
    }

    // DPテーブル出力
    // for (int i=0; i<=n; i++) {
    //   for (int j=0; j<13; j++) {
    //     cout << dp[i][j] << " ";
    //   }
    //   cout << endl;
    // }
    // cout << endl;

    digit *= 10;
    digit %= 13;
  }

  cout << dp[n][5] << endl;
}

F - Permutation Oddness

問題文

なんとなく解けそう！と思ったんだけど，ダメでした．

なんか zアルゴリズムなどで点を列挙して， Union-Find するらしい．
両方知りませんでした．

僕が書いた雑なプログラムでもある程度通ってるの笑いました．
Union-Find は，さらっと勉強したので， zアルゴリズム勉強したいと思います．

コンテスト中に書いたプログラム

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <string>
#include <set>

using namespace std;

std::vector<long long> find_all(const std::string str, const std::string subStr) {
    std::vector<long long> result;
 
    long long subStrSize = subStr.size();
    long long pos = str.find(subStr);
 
    while (pos != std::string::npos) {
        result.push_back(pos);
        pos = str.find(subStr, pos + subStrSize);
    }
 
    return result;
}

int main() {
  string s,t;
  cin >> s; 
  cin >> t;

  string st = s;
  string tt = t;


  while(t.size()*2 > s.size()) {
    s += s;
  }

  vector<long long> ans = find_all(s,t);



  if(ans.size()>1 && ans[0]+t.size() == ans[1]) {
    cout << -1 << endl;
    return 0;
  }


  cout << ans.size() << endl;
}