12月9日　精進録 - 草体にぼ日記

12月9日

　無限精進（しなさい）

　まえがき

なんだよ、昨日のコンテスト実質 unrated （パフォーマンス=rateのため変動なし) やる気あるの？精進しないとBでバグらせて思ったとおりの実装ができません。泣きた

頑張ろうね… - 解いた問題

ABC076C - Dubious Document 2

ABC041C - 背の順

ABC029 C- Brute-force Attack

ARC016 B- 音楽ゲーム

AGC005 A- STring

ABC147 C -HonestOrUnkind2

ABC108 C- Trianglular Relationship 写経AC

ABC033 C- 数式の書き換え

CODE FESTIVAL 2016 qual C B-K Cakes

AGC011 B - Colorful Creatures

ABC076C- Dubious Document 2

problem

解法

substrを使う問題辞書順で一番始めのものを出力したいので、できる限り前の方には'a'を入れるようにしたい。だから、可能な限りヒントの文字列tを入れる場所は後ろのほうにしたい。

ｔを可能な限り後ろに入れたとき、sのtと一致しない部分は'a'にして出力すればいい

ABC041C-背の順

解法

秒速ACした vector<pair<int,int>> を作る。要素は<身長、出席番号> これを慎重大きい順にソートしたあと、順番に出席番号を取って出力すればいい

ABC029 C- Brute-force Attack

解法

何だこれは next_permutationの手動実装か？？？？

とりあえず頑張ったから俺のコードを見ろ！！

#include <bits/stdc++.h>

using namespace std;
using ll =long long;

#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cout << #x << " = " << (x) << endl;
ll n,m;
//Write From this Line
int main()
{
    cin >> n ;    
    string start = "" ;
    rep(i,n){
        start += 'a';
    }
    //出力する回数は3 ^ n;
    for(int i = 0 ; i < pow(3,n); i++){
        cout << start << endl;
        char c = start[n-1] ;
        c ++ ;
        start[n-1] = c ;
        int now = 1;
        while( c >= 'd'){
            start[n-now] = 'a';
            now ++ ;
            char d = start[n-now];
            d += 1 ;
            start[n-now] = d ;
            c = start[n-now] ;
        }
    }
}

難しいね acに１を足したら ad -> ba っていうような変換をするみたいなことをしたよしんど！ｗｗｗ

再起関数を使うとうまくいくらしい（再帰関数使えるやつとかレッドコーダだろ…）

ARC016 B- 音楽ゲーム

problem

解法

oが出てきたとき、上の行、同じ列のものがoだったらプラスしない

0行目を見ているときは、添字エラーしないように注意しようね

AGC005 A- STring

problem

解法

Sが出てきたとき、それよりも右にTがあるなら消せる左から、Sが出てくるたびにcountSを＋する Tが出てくるたびに、countSを見て、それが０より大きいいなら、Tより左にSがあるということなので消せるSとTの組が一つありましたよ。というふうに報告していく（minusに１を＋する）

 cin >> s ;
    n = s.size();
    //Sが出てくるたびに消そ
    //sのあとに出てくるTの数を数える
    //STTのとき、２つ目のTはカウントしなくていい
    int minus = 0 ;
        int countS = 0;
        rep(i,n){
            if(s[i] =='S'){
                countS++;
            }
            else if(s[i] == 'T'){
                //Tが出てきたとき、一緒に消せるSがあるならminusにプラス１してcountSを１へらす
                if(countS > 0){
                    minus ++ ;
                    countS --;
                }
            }
        }
        cout << n - minus*2 << endl;
}

ABC147 C -HonestOrUnkind2

problem

お気持ち

本番中、なんかきつそうだなって思って1分くらいしか見ないで飛ばしてしまった。そのためbit全探索っぽいな。とすら思うことが出来なかった。

最近bit全探索をよく見かけるので、おそらくレートの適正がbit全探索を練習するぐらいになっていると思うので頑張るぞ。

解法

bit全探索で、n人に対して正直者か嘘つきかを決める例えばn=8のとき mask = 11001100なら、 0,1,4,5番目の人は嘘つき 2,3,6,7番目の人は正直者だとする。このとき、2,3,6,7番目の人の証言を見て、証言の中に 0,1,4,5番目の人が正直者、もしくは2,3,6,7番目の人が嘘つきと言っている証言が存在しなければ 全ての証言に矛盾はないので、maskのbitの立っている数が、そのmaskに対しての正直者の人数。 mask = 0000000 から11111111までを試して、一番立っているbitが多いところが答えです！！がんばった！偉い！天才かもしれない！

ABC108 C- Trianglular Relationship

problem

解法

写経ACです。某んちょんさんの記事で理解した（ような気がしなくもなくもなくもなくもない）自分で考えても全く手が動かなかった。とりあえず考察で出てくる最初の式が a + b ≡b + c ≡c + a ≡ 0 (mod k ); なんだけど、これすら浮かびませんでした。とりあえずこの式を出すところから始まる。自分出といた訳じゃないのであまり多くを出す言いたくないのでおしまい。

ABC033 C- 数式の書き換え

problem

解法

項の数（だっけ？？）は、＋が出てくる回数足す１項なので、それぞれの項について負になることはないので、　0かそれ以外かを見てあげればいい。（ a * b みたいなところは１項だから、＋の数足す１が項の数だね）

実装は案外かんたん

int main()
{
    cin >> s; 
    bool zero = false ;
    int ans = 0 ;
    rep(i,s.size()){
        if(s[i] == '0'){
            zero = true;
        }
        else if(s[i] == '+'){
            if(zero){
                zero = false;
            }
            else{
                ans ++ ;
                zero = false;
            }
        }
    }
    if(!(zero)){
        ans ++ ;
    }
    cout << ans << endl;
}

が出てきてから、次に+が出てくるまでにzero があれば、その区間では ? * ? * 0 * ? みたいなことが行われているのでその項は0になっている。

zeroがなければ、その区間では ? * ? * ? * ? 　の計算が行われている（？は０以外）ので、１つの？を0にしてやる必要がある。

いじょう！

CODE FESTIVAL 2016 qual C B-K Cakes

解法

一番たくさんある種類の🍰をTのケーキって呼ぶと、 T以外のケーキをまず並べてその間にケーキを入れてい毛羽、答えはTのケーキの個数 - それ以外のケーキの個数＋１（と０のうち大きい方）って求めた。

でもそうするよりも、まず　Tのケーキを並べる

🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰🍰 で、その間にT以外のケーキを入れて、何個のTを隣合わないようにできるかって考えていくのがいい。 T以外のケーキをまあ、a , b, c みたいな感じでやっっていく a = 2 , b = 2 , c = 10みたいな時を考える。とりあえず左から順にぽぽぽいってTが隣り合わないようにすりゃいい。　　 🍰a🍰a🍰b🍰b🍰c🍰c🍰c🍰c🍰c🍰c🍰c で、まだcが3個？余ってるから 🍰ca🍰ca🍰cb🍰b🍰c🍰c🍰c🍰c🍰c🍰c🍰c っていう感じで、aを入れたところらへんにまた入れていけばいい

この方がわかりやすい。T個のケーキがあるとき、隙間はT-1個と端が２個あるから、a,b,cはTの個数よりも少ないので、絶対に隣合わないように並べられる。

AGC011 B - Colorful Creatures

problem

解法

とりあえずソート小さいやつが束になって、結局一番大きいやつまでも食べることができるなら、小さいやつにも勝機はある（相手を俺色に染め上げることができる）

1 2 4 5 100000000000000000 のとき、前の４人のクリーチャーで、は、どの色になることもできます。しかし、前の４人のクリチャーが集まったところで、大きさはたかが 1 + 2 + 4 + 5 = 12 にしかなれません。これだと２４の大きさのクリーチャーまでしか吸収できないため、結局大きさが1000000000000000のクリーチャーの色にしかなれない。

ちなみに前の４クリーチャーでどの色にもなれるっていうのは、５の色になれるってことはわかると思う。１の色になれるっていうのはつまり

1 が　2 を食う（ 2 <= 1 * 2 だから食える）これで今１の色で大きさが３になった。だから大きさ６まで食える。つまり４も５も食えるだから１の色を採用できる！みたいな感じこれを頑張って実装したのが下

const int mod = 1e9+7;
int main()
{
    cin >> n;
    vector<int> a(n);//ookisa
    rep(i,n) cin>>a[i];
    SORT(a);
    ll start = 0 ;
    ll ans = 0 ; 
    rep(i,n){
        if(start * 2 >= a[i] ){
            ans ++ ;
        }
        else{
            ans = 0 ;
        }
        start += a[i];
    }
    ans ++ ;
    cout << ans << endl;
}

そろそろねよっと