A. Candies and Two Sisters
問題文
n個のキャンディをAliceとBettyで以下の条件を満たすように分ける
1. Aliceがキャンディをa個貰う
2. Bettyがキャンディをb個貰う
3. AliceはBettyよりも多くキャンディを貰う
4. すべてのキャンディを2人のどちらかが必ず貰う
これらをすべて満たすような分け方の数を数えよ
解法
を出力する
提出コード
void solve(){ ll n; cin >> n; cout << (n - 1) / 2 << endl; }
B. Construct the String
問題文
正の整数n, a, bが与えられる
長さがnの文字列を構築することを考える
ただし、構築した文字列の長さがaの全ての部分文字列にb個の異なる文字を含むような文字列を1つ出力せよ
解法
長さがaの文字列をabcddd...のようにb個の異なる文字からなるよう適当に作る
その後a個前の文字を順に末尾にくっつけていけばいい
void solve(){ int n, a, b; cin >> n >> a >> b; char c = 'a'; string ans = ""; for(int i=0;i<a;i++){ if((c - 'a' + 1) < b){ ans += c; c++; } else ans += c; } for(int i=a;i<n;i++) ans += ans[i-a]; cout << ans << endl; }
C. Two Teams Composing
問題文
n人の生徒から丁度2つのチームを作りたい
i番目の生徒の持っているskillがで与えられる
一つ目のチームの生徒のskillは全て異なる
二つ目のチームの生徒のskillは全て同じ
このような条件を満たすように丁度2つのチームを同じ人数となるように作りたい
この時、作ることが可能なチーム人数の最大を答えよ
解法
重複無しのskillの個数（distinct）と、同一skillの最大数（ma）を数える
distinct - 1がmaよりも大きかったらmaまでしか作れない
ma - (distinct - 1 ) が 2よりも大きかったら distinct + 1まで、そうでなければdistinctまでしか作れない
提出コード
void solve(){ int n; cin >> n; vector<int> a(n); vector<int> cnt(n+1); REP(i,n){ cin >> a[i]; cnt[a[i]]++; } if(n == 1){ cout << 0 << endl; return; } int distinct = 0, ma = 0; REP(i,n) if(cnt[i+1]){ distinct++; chmax(ma, cnt[i+1]); } distinct--; if(distinct >= ma) cout << ma << endl; else{ ma -= distinct; if(ma >= 2) cout << distinct + 1 << endl; else cout << distinct << endl; } }
D. Anti-Sudoku
問題文
の数独パズルの正答が与えられる
これらの1要素を最大9回まで変更することで以下の条件を満たすようにする
1. 全てのマスの要素は1以上9以下
2. 各列は同じ要素を最低2つ持つ
3. 各列は同じ要素を最低2つ持つ
4. 各ブロックに同じ要素を最低2つ持つ
このような条件を満たす答えが必ず存在することが保証されるので、そのうち1つを出力せよ
解法
ギャグ…
各列・各行がそれぞれ独立となるようにマス9個を選ぶ
そのマスに対して今書かれている数字+1に置き換える
これで終わりなんだけど、1が書かれているマスを2に書き換えるとかでも大丈夫だね（これTLで見たけど天才すぎる）
提出コード
void solve(){ vector<string> fi(9); REP(i,9) cin >> fi[i]; if(fi[0][0] == '9') fi[0][0] = '1'; else fi[0][0]++; if(fi[1][4] == '9') fi[1][4] = '1'; else fi[1][4]++; if(fi[2][8] == '9') fi[2][8] = '1'; else fi[2][8]++; if(fi[3][1] == '9') fi[3][1] = '1'; else fi[3][1]++; if(fi[4][5]== '9') fi[4][5] = '1'; else fi[4][5]++; if(fi[5][6] == '9') fi[5][6] = '1'; else fi[5][6]++; if(fi[6][2] == '9') fi[6][2] = '1'; else fi[6][2]++; if(fi[7][3] == '9') fi[7][3] = '1'; else fi[7][3]++; if(fi[8][7] == '9') fi[8][7] = '1'; else fi[8][7]++; REP(i,9){ REP(j,9) cout << fi[i][j]; cout << '\n'; } }
E2. Three Blocks Palindrome (hard version)
問題文
E1は制約だけが違うので省略
n個の正の整数からなる数列aが与えられる
three blocks palindromeを定義する
three blocks palindromeは最大でも2つの異なる要素からなる次のような配列
x, yは0以上の整数
数列aの部分列（連続じゃなくても良い）のうち、three blocks palindromeを満たす最大の長さを求めよ
解法
使う文字列の最大が高々2つまでなので全探索することを考える
各文字に対して、その文字のindexと累積和を取っておく
その後、どの文字を何個両端に使うかを探索し、間に入れられる文字とその個数を全探索する
これ計算量見積もりづらいね
提出コード
void solve(){ int n; cin >> n; vector<int> a(n); REP(i,n){ cin >> a[i]; --a[i]; } vector<vector<int>> idx(200); vector<vector<int>> cum(200, vector<int>(n+1)); REP(i,n){ REP(j,200) cum[j][i+1] = cum[j][i]; cum[a[i]][i+1]++; idx[a[i]].emplace_back(i); } int ans = 0; REP(i,200){ int sz = idx[i].size(); chmax(ans, sz); if(sz <= 1) continue; REP(j,sz){ if(idx[i][j] >= idx[i][sz-j-1]) break; int len = 0; REP(k, 200){ chmax(len, cum[k][idx[i][sz-j-1]] - cum[k][idx[i][j]+1]); } chmax(ans, (j+1) * 2 + len); } } cout << ans << endl; }
おわりに
E誤読して一生問題文の理解が出来なくて終わってしまった
