ブログのタイトルのインパクトでアクセス数が増える
ってことに気づきました．ブログの中身とブログのタイトルなんて関係なくていいです．
ブログって実は記事は読まれなくて，タイトルしか見てないんですよね．
今日の競プロのパートもクソ雑です．
今日の一曲．
<iframe width="560" height="315" src="https://www.youtube.com/embed/h-KuoHHjGRs" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>
声ともで知り合った女の子に好きな曲を聞いたらこれだった．
はい，解いた問題の目次
- ABC205 D- Kth Excluded(#anchor1)
- ABC202 D- aab aba baa(#anchor2)
- 未定３(#anchor3)
- 未定④(#anchor4)
- 未定⑤(#anchor5)
今日の競技プログラミング
ABC205 D- Kth Excluded
[二分探索,K番目,含まれない数]
厄介ですねえ，解くのに240時間くらいかかりました．
頭ぐしゃぐしゃのまま書いたら通っちゃいましたって感じです．ほかの方の記事を見ることをお勧めします．正直この問題に関してはおれのブログを読んでも得られることはないと思います．
二分探索を使ってやっては見ましたが正直良く分かりません．
int main() { int n, q; cin >> n >> q; vector<ll> a(n); rep(i,n) cin >> a[i]; SORT(a); // 二分探索してみる while(q--){ ll k; cin >> k; ll l = -1, r = n; while(r - l > 1){ ll mid = (l + r) / 2; ll num = a[mid]; ll kosu = num - (mid+1); if(kosu < k) l = mid; else r = mid; } //printf("l = %lld, r = %lld\n", l , r); k -= a[l] - (l+1); cout << a[l] + k << endl; } }
ACコード
とりあえず，数列Aについて，ソートしてもいいっすよね．します．
A = {3, 6, 7,9}としましょうか．A[i]を見たときに，K番目がA[i]よりも小さい数かどうかというのが実は判定できます．
例えば，K=5としましょう．今，Aに含まれない数で5番目の小さい数は， 1,2,4,5,8…8ですね．
- i = 0 のときの判定
A[0] = 3ですが，3以下の数に「Aに含まれない数で5番目に小さい数」が含まれているかどうかは，次のようにして判定できます．
- Aがソートしてあるので，「A[0] = 3以下の数でAに含まれているもの」は(i+1) = 1個ある（3だけ) ．
- 「３以下の数で，Aに含まれていないもの」は，a[0] - (i+1) = 3-1=2個ある(1と2)
まず1で3以下でAにふくまれている物の数を取得する
次に，2で，3以下でＡに含まれていない物の数を取得する．って感じの流れになっています
今，「3以下でAに含まれていない数の個数」は2だったので，3以下に目的(K=5)のやつはないっすね．
- i = 3 のときの判定
A[3] = 9です．9以下に「Aに含まれない数で5番目に小さい数」があるかを判定します．
- i=3なので，「A[3]=9以下の数でAに含まれているもの」は，(i+1) = 4個ある．(3,6,7,9)
- 「9以下で，Aに含まれていないもの」は，A[3] - (i+1) = 9 - 4 = 5個ある．
5個！？！？マジ！？！？ってことは「Aに含まれない数で5番目に小さい数」は9以下ってことが分かる．
で，今ちょっと説明のためにB[i] := A[i]以下でAに含まれていないものの数．としておきますか，B[0] = 2で，B[3] = 5 です． B全体は B=[2,4,4,5]です．
B[i] != B[i+1]のときを考えてみましょう，具体的に,B[2] != B[3]なので，ここを見ます．
A[2] (=7)以下でAに含まれていない物の数は4個，A[3] = (9) 以下でＡに含まれていないもんのの数は5個．ということは，7と9の間の数(8)はAに含まれていない数であるということが分かります．
こんな感じでB[i] < K, B[i+1] <= Kって感じのiを見つけたら，もう答えは目前です．
B[i+1] - B[i] を B[i]に足した値が答えな気がします．
多分．あんま理解できていないのでこの辺で終わりにしておきましょう．他の人の解説読んできます^^;
あ，そうそう，こんな感じのiを見つけるときに二分探索を使います．B[i]はiが大きいほど大きくなる単調増加性があるので二分探索が使えるよ．
ここで書いた通りのコードが貼ったコードと一致してるかは知りません．頑張ってね．
ABC202 D-aab aba baa
[組み合わせ，辞書順,]
提出AC
キタナイです．n choose mは計算だるいから関数にしてみた．
ll ncm(ll n, ll m){
ll child = n;
ll mother = 1;
ll mul = 1;
rep(i,m){
mul *= child;
child--;
if(mul % mother == 0){
mul /= mother;
mother++;
}
}
return mul;
}
その上でmain関数が下のようなかんじ
int main() { cin.tie(0); ios_base::sync_with_stdio(false); ll a, b, k; cin >> a >> b >> k; // まずは{a+b}C{a}を計算する ll child = a+b; ll mother = 1; ll mul = ncm(a+b,a); int n = a + b; int N = a + b; string ans = ""; rep(i,N){ if(a > 0 && b > 0){ // i文字目を'a'にすると何通りの文字列ができるか // n - 1 文字のうち a-1箇所が'a' n-a C a-1 ll A = ncm(n-1, a-1); if(A >= k){ a--; ans.push_back('a'); } else { b--; k -= A; ans.push_back('b'); } n--; } else { if(a > 0) rep(j,a)ans.push_back('a'); else rep(j,b) ans.push_back('b'); break; } } cout << ans << endl; }
動きとしては，1文字目からa+b文字目までを順に決めていく．
10番目の文字列を作りたいとき，i文字目を'a'にしたものが5個あるようなら，5番目までしか作れないので,i文字目は'b'だなって確定させていく感じ．
