ああああああゴミカスーーーーーーーーーーーーーーーーー
100+0+43+100+7=250です
非公式順位表見た感じだと門番の位置です。追い出されるか入れるかどうか...
コンテスト中のムーブ
カス
最初10分
Aを見る。いつもより難しくない？と言いながら現在地の左右で分けて実装。O(N)
この時点で0:08:02
#include <bits/stdc++.h>
#include "atcoder/all"
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using namespace atcoder;
#define all(a) a.begin(),a.end()
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> P;
constexpr ll inf=1ll<<61;
constexpr ll mod=998244353;
int main(){
int n,a;cin>>n>>a;
string s;cin>>s;
deque<int>Q1,Q2;
rep(i,n){
if(s[i]=='#'){
if(i<a)Q1.push_back(i);
else Q2.push_back(i);
}
}
ll ans=0,cur=a-1;
for(int i=0;;i++){
if(Q1.size()+Q2.size()==0)break;
if(i%2==0){
if(Q2.size()){
ans+=Q2.front()-cur;
cur=Q2.front();
Q2.pop_front();
}
else{
ans+=n-cur;
cur=n;
}
}
else{
if(Q1.size()){
ans+=cur-Q1.back();
cur=Q1.back();
Q1.pop_back();
}
else{
ans+=cur+1;
cur=-1;
}
}
}
cout<<ans<<endl;
}
間100分
Bを見る。 何これ。 下の方はいじらずに済む、ランレングス圧縮すれば同じ... などと色々考えてみるも全く分からない。困ったのでCを見る。何これ。 一見DPだがよく見ると不可能そうに見える。Dを見る。 自明。 とりあえずBを考えるだけ考えると、以下のような解法 (※嘘です！！！) が思いつく。
- 操作を逆から見ても、先頭からある部分までをひっくり返すという動作は同じである。
- 後ろの方の一致している部分はいじらずに済むので、その部分は適宜切り捨てる。
- 同じ文字をつないでいるところを切っても嬉しくないので、操作回数はランレングス圧縮した後の文字列-Xである。このXは完成時の文字列に異なる文字の接合部がどれだけ入っているかによって決まる定数である。
これを実装するとサンプルが通るので投げる。WA。 (0:56:35)
少し列挙してみると、ACBのようなケースでバグることがわかる。確かに前後の情報までは持てないので、諦めてDへ行く。
Dを見た瞬間二分探索がわかるので、書こうとする。実装することは単純だが、打ち切りの条件や計算量削減のために複数人をまとめて処理するパートで頭が破壊され、バグにバグを重ねて書き上げたのは 1:51:49 の時点だった。書いている途中は「このままだと2回予選に通って尚且つ黄色コーダーなのに予選100点という情けない成績で最後のJOIを終えてしまうかもしれない......」と焦りに支配されていて、まともにコードが書けなかったように思える。
デバッグ用に上限を100にしていて1ペナを食らうが、再提出したら無事に通った。70分を残して200点を取れたので、ひとまず再起可能であることを信じて安心する。
#include<bits/stdc++.h>
#include"atcoder/all"
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> PP;
typedef vector<ll> vi;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(),v.end()
constexpr ll inf=1ll<<61;
constexpr ll mod=998244353;
ll a[100006],b[100006],cpb[100006];
int main(){
ll n,k;cin>>n>>k;
rep(i,n)cin>>a[i];
rep(i,n)cin>>b[i];
ll lb=0,ub=2e18;
while(ub-lb>1){
ll mi=(ub+lb)/2;
ll res=0;
rep(i,n){
if(a[i]>=mi)res++;
cpb[i]=b[i];
}
if(!res){
int now=0,cur=-1;
ll nk=0;
while(now<n){
ll tm=0;
cur=-1;
do{
if(cur==-1)tm+=a[now];
else tm+=a[now]-a[now-1];
if(tm>=mi){
nk++;break;
}
ll d=mi-tm;
if(cpb[now]<d){
tm+=cpb[now];
cpb[now]=0;
cur=now;
now++;
if(now==n){
nk++;break;
}
}
else{
cpb[now]-=d;
nk++;
if(cur==-1&&d){
nk+=cpb[now]/d;
cpb[now]%=d;
}
if(cpb[now]==0)now++;
break;
}
}while(tm<mi&&now<n);
}
if(nk>k)res++;
}
if(res)lb=mi;
else ub=mi;
}
cout<<ub<<endl;
}
ラスト70分
ノータッチだったCをよく読むと、43点まではセグ木で取れることが分かったので、適当な提出からセグ木をコピーしてきて書き始める。DPの境界を合わせるのに苦労し、何とか2:27:17 時点で43点を獲得。このまま100点を目指しても時間が無いと思ったので、あらかじめ見ておいたEの自明部分点をお守りに取りに行く。焦りからか大量の誤読を発生させ、書きあがったのは 2:44:25時点だった。この時点で250点だったので、最後を信じてCへ戻ると、N<=4000制約の残り35点がすぐに思いついた。10分で書けるところまで書こうとしたものの、ちょうど全体像が書きあがった時点でタイムアップとなってしまった。
コンテスト後
全完や407点、300点台も大量にいたので半ば諦めていた。実際に今も半分諦めている。
もうどうにもならん
