結果

f:id:ngtkana:20200323002539p:plain

56 分 + 1 ペナ全完、159 位です。一目瞭然なのですが、犯人はアナタ（ E 問題）です！

ただこればかりは、そもそもかなり難し目に感じてしまいましたから、立ち回りの問題でもなさそうです。順位表を覗くとキレイな傾斜のようですから、苦手分野でしょうか。もしくは、F が得意だったのでしょうか。

A - The Number of Even Pairs (00:01:01)

気持ち急ぎ目で実装しました。かなり早い方です。

偶数同士、奇数同士の場合の数を数えましょう。

lint x,y;std::cin>>x>>y;
std::cout<<(x*(x-1)/2+y*(y-1)/2)<<'\n';

B - String Palindrome (00:03:12)

回文判定は、リバースと比較です。前半と後半の回文判定は、片方でよいです。リバースした文字列がありますから、使いまわしてしまいましょう。

std::string s;std::cin>>s;
std::string t=std::string(s.rbegin(),s.rend());
lint n=s.length()/2;
std::cout<<(s==t&&s.substr(0,n)==t.substr(n+1,n)?"Yes":"No")<<'\n';

C - Maximum Volume (00:05:06)

立方体のときが一番大きいです。

double x;std::cin>>x;
std::cout<<x*x*x/27<<'\n';

D - Banned K (00:07:15)

ここまで 7 分台、かなり調子が良いです。

全体の場合の数を前計算しておいて、そこからの差分を毎回計算です。全体の場合の数は、重複度リストを、x -> x(x-1)/2 でマップして足し合わせると良いです。差分は、自分以外の個数ですから、重複度引く 1 です。

lint n;std::cin>>n;
std::vector<lint>a(n),b(n);
for(lint i=0;i<n;i++){
    std::cin>>a.at(i);a.at(i)--;
    b.at(a.at(i))++;
}
lint ans=std::accumulate(
    b.begin(),b.end(),0ll,[](lint x,lint y){return x+y*(y-1)/2;});
for(lint x:a){
    std::cout<<ans-(b.at(x)-1)<<'\n';
}

E - Dividing Chocolate (00:40:16 + (1))

致命的です……

水平方向の割り方をビット全探索です。これは、分割の各成分の終点の集合をキーにするとよいです。また、最後のビットが必ず立っているように、半分のところからスタートをすると良いです。

さて、水平方向の割り方を決めたら、垂直方向の割り方は貪欲法で決まります。可能な限り右に伸ばすを繰り返します。ただし、二進も三進も行かなくなった場合は、そこで不可能判定をして、次のビットセットに移りましょう。

実装はいろいろとありそうな雰囲気なのですが、下記は二次元累積和による実装です。不可能判定のところの分岐、実装によっては消せるのでしょうか。

lint h,w,K;std::cin>>h>>w>>K;
std::vector<std::vector<lint>>a(h+1,std::vector<lint>(w+1));
for(lint i=1;i<=h;i++){
    for(lint j=1;j<=w;j++){
        char c;std::cin>>c;
        a.at(i).at(j)=c-'0'+a.at(i-1).at(j)+a.at(i).at(j-1)-a.at(i-1).at(j-1);
    }
}
lint H=1ll<<h,ans=h*w;
for(lint bs=H/2;bs<H;bs++){
    lint now=__builtin_popcountll(bs)-2;
    for(lint i=0,j=0;j<=w;j++){
        for(lint k=0,l=1;l<=h;l++){
            if(!(bs>>l-1&1))continue;
            if(j==w||K<a.at(l).at(j+1)-a.at(l).at(i)-a.at(k).at(j+1)+a.at(k).at(i)){
                now++;
                if(i==j)goto Impossible;
                else{i=j;break;};
            }
            k=l;
        }
    }
    if(now<ans)ans=now;
    Impossible:;
}
std::cout<<ans<<'\n';

インデント波動拳！そして伝家の宝刀 † goto 文 † です。

実装面では、おそらく尺取り法パートが若干厄介で、ひとつ先読みをして、ダメそうならそこで止めるをする必要があります。このコードでも j だけが +1 されていますね。

それと、不可能判定は、一見何もしなくても勝手にできそうだと思（って WA をしたのはどこのどなたですか？）いがちなのですが、よく考えると無理なことがわかります。実装によっては気にしなくても良いのでしょうか。ここに場合分けが生じるのは、なんだかあまりキレイでないよいにも思えます。

F - Knapsack for All Segments (00:56:08)

1 時間切り！と思いきや、E のペナルティーがありますから、オーバーです。

合計が S になる部分集合を、( 左の空き + 1 ) × ( 右の空き + 1 ) で重み付けして足し合わせます。まず、重みづけがない場合の問題を考えましょう。これは、右端を全探索すればよいです。各場所が右端になるような、和が i であるような部分集合の数を、左から順に決めていくことができます。

さて、重みをつけるにはどうするとよいでしょう。まず、右側の重みは、答えに足し合わせるときに掛けると良いです。左側の重みは、集合が無から生まれるときに掛けましょう。

std::vector<lint>dp(S+1);
lint ans=0;
for(lint i=0;i<n;i++){
    lint x;std::cin>>x;
    for(lint j=S;j-x>=0;j--){
        add_assign(dp.at(j),dp.at(j-x));
    }
    if(x<=S)add_assign(dp.at(x),i+1);
    add_assign(ans,dp.at(S));
}
std::cout<<ans<<'\n';