SHIINBLOG

AtCoder Beginner Contest 135

はい. AtCoder Beginner Contest 135 です

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;
}



まとめ

今回は,C問題までしか解けなかった上に, D 問題が全然分からなくて焦って C の再提出などして,
たくさんペナルティーもらってしまったので,ダメダメでした.

緑になれるかな〜と思っていたのにむしろレート下がりました_(:3」∠)_