ABC118 に参加した話

問題

下記リンク

atcoder.jp

解答

A問題

  cin >> a >> b;
  if(b%a == 0) cout << a+b << endl;
  else cout << b-a << endl;

B問題

mapに挿入、n個あるものをカウントして出力

int k[31], a[31][31];
map<int, int> mp;

int
main(void){  
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int n, m;
  string s;

  cin >> n >> m;
  REP(i, n){
    cin >> k[i];
    REP(j, k[i]){
      int tmp;
      cin >> tmp;
      mp[tmp]++;
    }
  }
  int cnt = 0;
  for(auto itr = mp.begin(); itr!=mp.end(); itr++){
    if(itr->second == n) cnt++;
  }
  cout << cnt << endl;
  return 0;
}

C問題

A_iの中から小さい数を取り出してmodをとる これを繰り返し、できなくなったら終了 最小値を出力

const int INF = 1e9;
int n;
ll a[100100];

int mini = INF;

int
main(void){  
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  cin >> n;
  REP(i,n) {
    cin >> a[i];
    if(a[i] < mini) mini = a[i];    
  }
  bool f = true;
  while(f){
    int tmp = mini;
    int cnt = 0;
    REP(i, n) {
      if(a[i]%mini != 0){
    a[i] %= mini;
      }
      else{
    cnt++;
      }
    }
    if(cnt == n) break;
    REP(i, n) mini = min((int)a[i], mini);
  }
  cout << mini << endl;
  return 0;
}

D問題

(時間内に解けなかった) 考えたことは、DPで解けそう→dp[i][j]で長さ最大の文字数を入れればいけそう→経路の復元方法が分からない→貪欲 という流れで貪欲を書いたが、RE

正解は、string型の一次元DPに文字列ごと保持する 文字列長が最大となるものを管理しつつ、長さが同じ場合は辞書順比較で小さいものを常に管理する (他の方のコードを参考にさせていただきました)

//解説AC
//https://atcoder.jp/contests/abc118/submissions/4292391

int num[]={0,2,5,5,4,5,6,3,7,6};
int a[10];
int n,m;

void cng(string &t, string p){
  if(t=="0") t=p;
  else if(t.size() < p.size())t=p;
  else if(t.size() == p.size()){
    if(t<p) t=p;
  }
}

int
main(void){  
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  REP(i,m) cin >> a[i];

  string dp[100100];

  REP(i, n+1) dp[i] = "0";

  dp[0] = "";
  REP(i, n+1){
    if(dp[i] == "0") continue;
    REP(j, m){
      cng(dp[i+num[a[j]]], dp[i]+(char)(a[j]+'0'));
    }
  }
  cout<<dp[n]<<endl;
}

感想

D問題、解けない問題ではないので、頑張って解きたかった... 引き続き精進します

学んだこと

- 文字列の辞書順比較はoperator >, <で可能

例えば '9' > '11' はtrueになる

- (char)(a[j]+'0')でint->char変換