12月5日

解いた問題

技術室億プログラミングコンテスト#4 Day1 a- ヘビがヘビー

技術室億プログラミングコンテスト#4 Day1 B- Long Long Ago

ABC142 E-Get Everything

abc064 D-Insertion

技術室億プログラミングコンテスト#4 Day1 B- Long Long Ago

problem

解法

k(王様の顎の長さ）を超えない中で、最大の要素の番号を取得する

技術室億プログラミングコンテスト#4 Day1 a- ヘビがヘビー

problem

解法

一瞬、っていうか数秒は？？ってなる問題。とりあえず平均ってどういうものだったか考えてみる。 N匹の蛇が全員大きさWだったら、その平均はWになる。

平均を超える蛇を多くしたいのであれば、蛇の重さはWを少し超えるものと、ほぼ0であるものだけにすればよさそうだと考える。

そこで、N-1匹がWの大きさ、一匹だけが0.0000000001みたいな小さな値だったら,平均はWよりも小さくなっている。この時、N-1匹の大きさをもう少しだけ大きくしてあげれば、平均はさっきよりは大きくなるけど、それでもWを超えないで、N-1匹をWより大きくすることができる。でうまく調整すれば、平均をWにできる。

今回、平均をWにしたときのN匹の重さを出せ。みたいな問題ではないので、このように1匹の蛇だけめちゃくちゃ軽くしてやれば、残りのN-1匹はWを超えるようにできる。よって答えはN-1となる。

abc142 e- Get Everything

problem

写経AC

解法

集合を二進数で管理するDP. シフト演算 1 ( << 2) では、001 となるように、1( << n)では、前にn個の0を追加する。みたいなことができる理解したような理解してないようなって感じ。その分際でいうのもなんだけど、bitDPの練習としてはかなりいい問題な気がする。

配るDPで、まず{}空集合の状態から遷移をさせていく。

#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;

bool coY() {cout <<"Yes"<<endl;}
bool coN(){cout <<"No"<<endl;}

const int INF = 1001001001;

int n,m;
string s;
//Write From this Line

const int mod = 1e9+7;
int main()
{
    cout << setprecision(10);
    cin >> n >> m ;
    vector<pair<int,int>> key;
    rep(i,m){
        int a , b ;
        cin >> a >> b ;
        int s = 0 ;
        rep(j,b){
            int c ;
            cin >> c;
            c-- ;
            s |= 1<<c;//c=3 なら0001になる
        }
        key.emplace_back(s,a);
    }

    vector<int> dp(1<<n, INF); //2^n 箱の数の2乗のテーブルが必要

    dp[0] = 0 ;
    //ここについて説明！！！！！！！！！！！！！！！！！！！！！
    rep(s,1<<n){
        debug(s);
        rep(i,m){
            int t = s | key[i].first;
            int cost = dp[s] + key[i].second;
            dp[t] = min(dp[t],cost);
        }   
    }
    //ここまでについて説明！！！！！！！！！！！！！！！！！！！！！！！！！
    int ans = dp.back();
    if (ans == INF) ans = -1 ;
    cout << ans << endl;

}

超抜粋

説明するよっていってる部分を見ていこう

1行目から順に rep(s,1 << n ) まずこれは for(int s = 0 ; s < (1 << n ) ; s++)　を意味する（あってますよね？ s <( 1<< n)は、2ⁿ になるまでループを回すってことだ。

その次 int t = s | key[i].first ; このtは、今作るdpが、どの箱を開けれるようにするものなのかを示す論理和で、sが、1つ前の状態で、それとi番目のカギを使うことで、tであらわされるような箱の状態が得られるというわけだ。

その次の行 int cost = dp[s] + key[i].second; sの状態に、カギの値段を足したものをコストとしてその次の行で、それが安いものなら更新する。って感じ

解説写経なんだけど、よくできたコードですなあ…（ほれぼれ）

abc064 D-Insertion

problem

解法

' ( ' や　' ) ' を加える（挿入する）位置は先頭か末尾、

' ( ' なら先頭 ,' ) ' なら後ろに入れるです

赤が挿入するもの、黒が元の文字列です。

)が出てくるたびに、それに対応する　始まりかっこ（　が　足りているかを見ます。足りていないなら、一番前に（　を　足すことにします。（が足したい数だけ入っている変数が　下のコードの　start です。変数Tには、閉じかっこの数みたいなのが入っているけど閉じかっこではない（でも必要なもの）（なんて説明したらいいかわからん）

で、最後にstartと文字列を足したものをいったんansとして、 ans の（　と　）の数を数えて（　の数　－　）　の数が足りていない）の数なのでその個数だけ）を足してやればいい。

ん～～むずいねこれ

int main()
{
    cin >> n ;
    cin >> s; 

    int hazi = 0 , tozi = 0 ;
    int T = 0 ;
    string start ="";
    rep(i,n){
        if(s[i] == ')'){
            tozi ++ ;
            T ++ ;
        }
        else hazi ++ ;

        if(s[i] == ')'){
            if(T > hazi){
                start += '(' ;
                T -- ;
            }
        }
    }
    string ans = start + s  ;
    //ここまで作り終わったのを見て、足りない分だけ閉じを足す
    hazi = 0 , tozi = 0;
    rep(i,ans.size()){
        if(ans[i] ==')'){
            tozi ++;
        }else hazi ++;
    }
    int k = hazi - tozi ;
    rep(i,k){
        ans += ')';
    }

    cout << ans << endl;
}