yamake's blog

主に競プロ、たまに自転車

2/6 ~ 2/12 解いた問題

Codeforces Round #705 C K-th beautiful String

問題概要:

　長さ n の文字列 s が与えられます。s 中に各文字の現れる数がそれぞれ k 回で割り切れる時、その文字列は美しいと呼びます。
　文字列 s の文字を自由に変換し、辞書順で s 以上の文字列の中で辞書順最小の美しい文字列を求めなさい。美しい文字列に変換することができなければ -1 を出力しなさい。

考えたこと:

　とりあえず、n \% k > 0 のとき、-1 を出力し、それ以外では美しい文字列を作ることができる（zz...z は辞書順で s 以上かつあ、美しいため）。
　美しい文字列の辞書順の lower_bound みたいな気持ちになった。元の文字列が美しければそのまま出力、元の文字列が美しくない場合を考える。s と共通な prefix ができるだけ長くなるように構築すると良さそう。実装がちょっと面倒くさいかも（？）。

解法:

　s と共通な prefix の長さを決め打ちして、構築を後ろから探索し、最初にできるところで構築をして出力。具体的には、足りない文字の数を数えておいて、自由に変更できる文字の数のほうが足りない文字の数より多くなったら ok。
　構築は vector に足りない文字を必要な数突っ込んで、自由に変更できる文字数が余れば 'a' だったり、変更する suffix の先頭の文字より 1 大きい文字を k 個 vector に追加して、ソートしてあとはよしなに。

提出コード

AGC016 B - Colorful Hats

問題概要

　日本語なので割愛

考えたこと

　こんなん無理やん。全ての猫同士が N-2 匹分の情報を共有していると考えると、a_i の種類数はあんまり多くないかもしれない。よく考えると、minmax の差は 1 以下になるね。"自分と同じ色の帽子を被っている他の猫がいるかどうか" に着目して場合分けをすると解けますね。

解法

　丁寧丁寧丁寧に場合分けをします。具体的な分け方は editorial か解答コードを見てもろて......。

提出コード

Educational Codeforces Round 109 E - Assimilation IV

問題概要

　n 個の都市と、m 個の街があり、全ての都市 i と街 j の間の距離 d_{i,j} が与えられます。1 ... n の順列 p に対して、d_{p_i,j} \leq n-i+1 \ (1\leq i\leq n) となる i が存在する街 j の数を順列 p のスコアと呼びます。全ての順列 p に対して、得られるスコアの平均値を求めなさい。（わかりづらかったら問題に飛んでください＞＜）

考えたこと

　n \leq 20 はもう bitDP って言ってるようなものじゃんｗｗｗ。なんやかんやあって O(N2^N+M) くらいに落ち着くでしょ。対戦ありがとうございました！！！→落ち着きませんでした ＼ ^ｑ^ ／。
　よく考えるとそれぞれの街から得られるスコアへの寄与は独立しているので、M 回の独立した計算が必要になりそう。
　考える街を固定した時、各都市と条件を満たすか？の和集合が真になるときスコアが 1 増えると考えると、包除か？結局この形の包除は N2^N くらいの計算が必要だから違いそう、、、よく考えると全体から否定の積集合を引いても良いな。

解法

　平均値ではなく総和を考えて n! で割ることにします。各街について考えて、"その街がスコアを 1 増やさない" 順列の個数を数えて n! から引くことによって総和が得られます。
　具体的には各街について、\Pi_{i=1}^{N}(d_{x,j} > n-i+1 となっている x の数 - i) を求め、n! から引いた値の総和が求めたいものになります。
　最後に得られた総和を n! で割ることにより、正答が得られます。

提出コード（atcoder/all を展開しているので長いです。）

atcoder/all の展開を省いたコード

#include <bits/stdc++.h>

using namespace std;
#define rep(i,n) for(long long i=0;i<n;++i)
#define rep1(i,n) for(long long i=1;i<=n;++i)
#define rrep(i,n) for(long long i=n-1;i>=0;--i)
#define debug(output) if(debugFlag)cout<<#output<<"= "<<output<<endl
using lint = long long;
typedef pair<int,int> P;
const bool debugFlag=true;
const lint linf=1.1e18;const lint inf=1.01e9;
constexpr int MOD=1000000007;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }

#include<atcoder/all>
using namespace atcoder;
using mint = modint998244353;

mint calc(vector<int> a){
    int n=a.size();
    mint res=1;
    sort(a.rbegin(),a.rend());
    int p=0;
    int buf=0;
    rep(i,n){
        while(p<n&&a[p]>n-i){
            ++buf;++p;
        }
        res*=buf--;
    }
    return res;
}

signed main(){
  int n,m;cin>>n>>m;
  vector<vector<int>> a(m,vector<int>(n,0));
  rep(i,n)rep(j,m)cin>>a[j][i];
  mint res=0;
  mint np=1;
  rep1(i,n)np*=i;
  rep(i,m)res+=np-calc(a[i]);
  res/=np;
  cout<<res.val()<<"\n";
  return 0;
}


もすーんバチャ #322

久々にもすーんバチャを走りました。5 問目で実装をミスり、29 分頃にバグを取れて提出したらオーバーフローして、そこを直したけど、間違えて Python で提出してしまい、提出制限で最後の提出ができずに負けました......。
6 問目までは upsolve するので、7 問目はまあ、そのうち......。