# 芝浦ばちゃ#4

# A - ABC333

# 概要

  • 整数A,BA, Bが与えられた時に, A×B×CA \times B \times Cが奇数となるようなCCが存在するか判定せよ

# 解法

  • 少し考えると, A,B,CA,B,Cの積が奇数 \Longleftrightarrow A,B,CA,B,Cは全てが奇数である
  • したがって, AABBが両方奇数の時はYes, それ以外はNo

# 提出コード

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64

signed main() {
  int a,b;
  cin>>a>>b;
  bool ok = (a%2 && b%2);
  cout<<(ok?"Yes":"No")<<endl;
  return 0;
}

# B - AtCoDeerくんとボール色塗り / Painting Balls with AtCoDeer

# 概要

  • NN個のボールをKK種類の色で塗る
  • 隣り合ったボールは異なっていなければならない
  • この時の塗り方は何通りあるか求めよ

# 解法

  • 端のボールの塗り方がKK通り, その隣のボールの塗り方はK1K-1通り, その隣もK1K-1通り, (以下略)
  • したがって, 塗り方はK(K1)...K * (K-1) * ...としていけば求められる

# 提出コード

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64

signed main() {
  int n,k; cin>>n>>k;
  int ans = k;
  for(int i=0;i<n-1;++i) {
    ans *= (k-1);
  }
  cout<<ans<<endl;
  return 0;
}

# C - pushpush

# 概要

  • 長さNNの数列aaが与えられて, nn回つぎの操作を行った後にできる数列bbを求めよ
    • ii番目の要素を数列bの末尾に追加する
    • 追加した後に数列bbを逆向きにする

# 解法

  • 愚直に操作をすると, O(n2)O(n^2)になる
  • すこし考えると, iiが奇数の時には末尾に, iiが偶数の時には先頭に追加すればよいことがわかる
  • ただし, 操作する回数nが奇数の時は出力する数列が逆向きになっているので注意

# 提出コード

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64

vector<int> ans;
signed main() {
  int n;cin>>n;
  deque<int> q;
  for(int i=0;i<n;++i) {
    int a;cin>>a;
    if(i%2) {
      q.push_front(a);
    }else{
      q.push_back(a);
    }
  }

  for_each(q.begin(), q.end(), [](int x){
                                 ans.push_back(x);
                               });
  
  if(n%2==1) reverse(ans.begin(),ans.end());
  
  bool isFirst = true;
  for(int i=0;i<n;++i){
    if(isFirst) isFirst = false;
    else cout<<" ";
    cout<<ans[i];
  }
  cout<<endl;
  
  return 0;
}

# D - Match Matching

# 概要

  • NN本のマッチを使って作れる整数の最大値を求めよ
  • ただし, 数字 1,2,3,4,5,6,7,8,9 を1つ作るには、それぞれちょうど 2,5,5,4,5,6,3,7,6 本のマッチ棒を使う

# 解法

  • 典型的なDP
  • 考え方はつぎの通り
  1. NN本のマッチを使って作れる整数の最大値」を求めたい

  2. 仮に11という数字を使用する時,
    N1N-1本のマッチを使って作れる最大値」が分かれば,
    NN本のマッチを使って作れる整数の最大値」も求められるはず

  3. さらに11という数字を使用する場合,
    N2N-2本のマッチを使って作れる最大値」が分かれば,
    N1N-1本のマッチを使って作れる整数の最大値」と「NN本のマッチを使って作れる最大値」も求められるはず

  4. これを何回も繰り返すと,
    00本のマッチを使って作れる最大値(これは当然0)」が分かれば,
    00NN本のマッチを使って作れる最大値」がわかるはず!

  • この上で, DPテーブルをつぎのように定義する
dp[i] := ちょうどi本のマッチを使って作れる整数の最大値(文字列)
  • すると, DPの遷移はつぎのようになる
dp[i] = max(dp[i], 足したい数字 + dp[i-{足したい数字を作るための本数}])
  • ただし, 文字列で比較するので自分でmax関数の代わりを作る必要がある
  • この部分の実装は, 過去のABCのB問題で出題されているので解いてみると良いかも

# 提出コード

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64

string dp[10101];
int cost[10] = {10101010101,2,5,5,4,5,6,3,7,6};


bool check(string p, string q){
  if(p.size()==q.size()) return p>q;
  return p.size() > q.size();
}

signed main() {
  int n,m;cin>>n>>m;
  vector<int> a(m);
  for(int i=0;i<m;++i) cin>>a[i];

  // 降順にソート
  sort(a.begin(), a.end());
  reverse(a.begin(), a.end());
  
  fill_n(dp,10101,"0");
  dp[0] = "";
  for(int i=0;i<=n;++i){
    for(int j=0;j<m;++j){

      if(i-cost[a[j]]>=0){
        if(dp[i-cost[a[j]]]=="0") continue;

        string tmp = to_string(a[j]) + dp[i-cost[a[j]]];
        // 新しく作った整数が元のものより大きかったら更新
        if(check(tmp, dp[i])) {
          dp[i] = tmp;
        }
      }
    }
  }

  string ans = dp[n];
  cout<<ans<<endl;
  
  return 0;
}

# References

Last Updated: 2019-9-5 12:38:33