ABC209参戦記 - chacoderのブログ

はじめに

2021年7月10日21:00-22:40に開催されたABC209に参戦しました。
結果は44:09 ABCD4完ノーペナでパフォーマンス1106　レーティングは前回835から+30の865になりました。
前回まで5回連続で冷えていたので久しぶりのレートアップです。

f:id:chacoder:20210711134125p:plain
f:id:chacoder:20210711134040p:plain

はじめに
A問題
Ｂ問題
C問題
D問題
E問題
終わりに

A問題

A - Counting
A以上B以下の整数を出力する問題です。
BがＡより小さい場合に注意して解きました。
1分15秒

Ｂ問題

B - Can you buy them all?
N個の商品をK円で全部買えますかという問題です。
偶数個が１円引きということで添え字と偶奇がずれることに注意します。
Ａ問題もＢ問題も簡単な問題でした。時間もまあまあ。
2分38秒、通算3分53秒

C問題

C - Not Equal
難しかったです。
最初５分ほど考えて解法を思いつかず、先にDを解いて戻ってきました。
落ち着いて考えるとソートしても結果は同じことに気づき昇順でソートして積を取ればよいことに気づきました。
0になるパターンに注意して実装しました。
トータルで12分ぐらいかかった感じ。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
static const ll mod=1000000007;

int main() {
  int n;
  cin>>n;
  vector<int>a(n);
  rep(i,n){
    cin>>a[i];
  }
  sort(a.begin(),a.end());
  ll ans=1;
  rep(i,n){
    if(a[i]<i+1){
      cout<<0<<endl;
      return 0;
    }
    ans*=(a[i]-i);
    ans%=mod;
  }
  cout<<ans<<endl;
  return 0;
}

D問題

D - Collision
グラフ問題です。
二部グラフになっているのでBFSで頂点の塗り分けをして同じ色の頂点か異なる色の頂点かで判別する方針で解きました。
BFSもだいぶ慣れてきて塗分けなどの作業もうまくできました。３から引いて１か２にするのがいい感じ。
デクリメントする場所を間違えていたのに気づかずバグとりに手間取り25分ぐらいかかりましたが解けてよかったです。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)

int main() {
  int n,q;
  cin>>n>>q;
  vector<int>to[n];
  rep(i,n-1){
    int a,b;
    cin>>a>>b;
    a--;b--;
    to[a].push_back(b);
    to[b].push_back(a);
  }
  vector<int>dist(n,-1);
  queue<int>que;
  dist[0]=1;
  que.push(0);
  while(!que.empty()){
    int v=que.front();
    que.pop();
    for(auto nv:to[v]){
      if(dist[nv] != -1) continue;
      dist[nv]=3-dist[v];
      que.push(nv);
    }
  }
  //rep(i,n) cout<<dist[i]<<endl;
  rep(i,q){
    int c,d;
    cin>>c>>d;
    c--;
    d--;    
    if(dist[c]==dist[d]) cout<<"Town"<<endl;
    else cout<<"Road"<<endl;
  }
  return 0;
}

E問題

E - Shiritori

一見して手に負えそうにない感じでしたが，時間一杯取り組みました。
グラフに落とすところまでやった。
あとは解説見て勉強します。

int main(){
  int n;
  cin>>n;
  string s[n];
  rep(i,n) cin>>s[i];
  vector<int>to[n];
  rep(i,n) rep(j,n){
    int ilen=s[i].length();
    if(s[i].substr(ilen-3,3)==s[j].substr(0,3)){
      to[i].push_back(j);
    }
  }