日記 20180920
日記 書いていきたいと思います
バイト
レジ打ち ストレスやばいね
漫画とか
進撃の巨人の23から26までを買いました めっちゃ面白いよ
あとやが君の5巻買った よんでないよ
フォートナイト
初めて配信した 人に見てもらうの楽しいんだけど恥ずかしい 人間って、不思議だな
人生
ファミマのトルティーヤおいしい でも400円 おひるごはんにしては少ない
いつか大金持ちになったらバイト前の朝食としてトルティーヤとコーヒー買いてえ
人生2
人と接する機会がなくて寂しい うくにきあくん、ねねにきあくん、遊びませんか びーとくんはいいや
人生3
お酒飲むと酔う バイトの後はすぐにお風呂で温水を浴びて体をほぐさないとフォートナイトしちゃだめですよ これはフォートナイトの欄に書きなさい
レヴュースタァライトについて
10話また見た 西條クロディーヌよすぎないか 彼女の純粋な心を思うと胸が熱くなる
うくにきあくんおいしかった？笑
うん
今日は楽しかった？笑
ふつう
日記 20180919
日記を書きます
競技プログラミング
ACPCのday1にチームlatte0119(メンバー:latte0119)の一員として出ました。
A:ひ
— らて (@LatteMalta) 2018年9月19日
B:ふ
C:み
D:読まず
E:F問題のコードを提出してみたらWAになりました
F:これはなんですか
G:作問者と話し合いをしたい
H:これはなんですか
Eの貪欲、正当性、なに
F,なに
Gについては、正直writerをブロックしたい
H,なに
うーん、あんまり競技プログラミングしない人間だけど、衰えは感じない(成長も)
ウクニキアについて
うくさんがアズリムタグで長文オタクツイートしてる様子をよく見るので、真似するようになった
まだ錬成に時間がかかる
フォートナイト
そこそこハイセンシにしてプレイしてた(dpi1000、感度xy0.10)
建築は楽だけどエイムがきつい(でも慣れてくるとタクティカルショットガンが使いやすいなあと感じた 逆にポンプが当たらない)
朝一の試合で楽にビクロイした(敵が弱い時間帯)
一戦目 noob三人抜き #PS4sharehttps://t.co/GIts421wZ6 pic.twitter.com/dXctJNCGzr
— 星見純那 (@latte0119_) 2018年9月19日
acpcの後にやけ酒してからまたフォートナイトした 時間帯的に敵のレベルがエぐ過ぎてきつかった
生命力 #PS4sharehttps://t.co/1fSVevMC6q pic.twitter.com/3CDlo4mv54
— らて (@LatteMalta) 2018年9月19日
これ結構うまくいった このシーンの前にも結構つらい場面があった(複数人から集中砲火されたり、漁夫がひたすらアサルトライフルで邪魔してきたり)んだけど、いつもみたいになげやりにならずに落ち着いて防御できたと思う 無駄死にしないのは大切
あと二連式ショットガンがちゃんと使えるようになってきたと思う(チート火力なのでつい使いたくなるんだけど、適切な距離とタイミングで撃たないとリスクがでかいので、そこらへんの見極めをするようになってきた 二連式キッズを卒業しよう)
屋根もちょいちょい使えるようになってきたよ
うくにきあくんおいしかった？笑
レヴュースタァライトについて
いい
今日は楽しかったですか
ふつう
CSA70- And or Max
なんか書きます
続きを読むjoi2018 本選
はじめに
うくにきあ ちょっと変えると やきにくや
JOI2017/2018予選
はじめに
うくにきあ
1問目
やる
#include<bits/stdc++.h> using namespace std; #define int long long #define rep(i,n) for(int i=0;i<(n);i++) #define pb push_back #define all(v) (v).begin(),(v).end() #define fi first #define se second typedef vector<int>vint; typedef pair<int,int>pint; typedef vector<pint>vpint; template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;} template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;} signed main(){ int N,A,B,C,D; cin>>N>>A>>B>>C>>D; cout<<min((N+A-1)/A*B,(N+C-1)/C*D)<<endl; return 0; }
2問目
連続する1の数+1が答えだとわかるため
#include<bits/stdc++.h> using namespace std; #define int long long #define rep(i,n) for(int i=0;i<(n);i++) #define pb push_back #define all(v) (v).begin(),(v).end() #define fi first #define se second typedef vector<int>vint; typedef pair<int,int>pint; typedef vector<pint>vpint; template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;} template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;} signed main(){ int N; cin>>N; vint A(N); rep(i,N)cin>>A[i]; int cur=0; int ans=1; while(cur<N){ if(A[cur]==0)cur++; else{ int nex=cur; while(nex<N&&A[nex])nex++; chmax(ans,nex-cur+1); cur=nex; } } cout<<ans<<endl; return 0; }
3問目
O(H^2 W^2)で全探索する。なんかもはや2問目の方が難しいんじゃないか
#include<bits/stdc++.h> using namespace std; #define int long long #define rep(i,n) for(int i=0;i<(n);i++) #define pb push_back #define all(v) (v).begin(),(v).end() #define fi first #define se second typedef vector<int>vint; typedef pair<int,int>pint; typedef vector<pint>vpint; template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;} template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;} int H,W; int A[33][33]; signed main(){ cin>>H>>W; rep(i,H)rep(j,W)cin>>A[i][j]; int ans=LLONG_MAX; rep(i,H)rep(j,W){ int sum=0; rep(k,H)rep(l,W){ sum+=min(abs(i-k),abs(j-l))*A[k][l]; } chmin(ans,sum); } cout<<ans<<endl; return 0; }
4問目
dp[i][j]:=i番目の切れ目までの切り方を確定させて、i番目の切れ目で切ることにして、かつこれまでの長さの最大値がjであるときの、"これまでの長さの最小値"の最大値、とする。
まあ下に貼ったコードのように遷移するとO(N^3 L) (L=max{L_i})で解ける。O(N^2L)とかでも解けるんだろうか、うーん
#include<bits/stdc++.h> using namespace std; #define int long long #define rep(i,n) for(int i=0;i<(n);i++) #define pb push_back #define all(v) (v).begin(),(v).end() #define fi first #define se second typedef vector<int>vint; typedef pair<int,int>pint; typedef vector<pint>vpint; template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;} template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;} const int INF=1231231231231231231ll; int N; int L[55]; int dp[55][55555]; signed main(){ cin>>N; rep(i,N)cin>>L[i+1]; rep(i,N)L[i+1]+=L[i]; memset(dp,-1,sizeof(dp)); dp[0][0]=INF; for(int i=0;i<N;i++){ for(int j=0;j<L[N];j++){ if(dp[i][j]==-1)continue; for(int k=i+1;k<=N;k++){ chmax(dp[k][max(j,L[k]-L[i])],min(dp[i][j],L[k]-L[i])); } } } int ans=INF; for(int i=0;i<L[N];i++)if(dp[N][i]!=-1)chmin(ans,i-dp[N][i]); cout<<ans<<endl; return 0; }
5問目
dp[k][i][j]=座標(i,j)の木を切り終えて、(0,0)から(i,j)まで長さkの道を歩んできたときの時間の最小値、とする。
まあ普通に4近傍に遷移していい感じにできるため、おわり。
下のコードではdijkstraしてますが、遷移がDAGになっているためふつうにdpでいいです。(気付かなかった)
#include<bits/stdc++.h> using namespace std; #define int long long #define rep(i,n) for(int i=0;i<(n);i++) #define pb push_back #define all(v) (v).begin(),(v).end() #define fi first #define se second typedef vector<int>vint; typedef pair<int,int>pint; typedef vector<pint>vpint; template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;} template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;} const int INF=1231231231231231231ll; int H,W; int A[33][33]; int dist[33][33][33*33]; using Taplis=tuple<int,int,int>; int dy[4]={-1,0,1,0}; int dx[4]={0,-1,0,1}; signed main(){ cin>>H>>W; rep(i,H)rep(j,W)cin>>A[i][j]; fill_n(**dist,33*33*33*33,INF); dist[0][0][0]=0; priority_queue<Taplis,vector<Taplis>,greater<Taplis>>que; que.push(make_tuple(0,0,0)); int ans=INF; while(que.size()){ int z,y,x,c,d; tie(c,z,d)=que.top(); que.pop(); y=z/W; x=z%W; if(dist[y][x][d]<c)continue; if(y==H-1&&x==W-1){ cout<<c<<endl; return 0; } if(d+1==H*W)continue; rep(dir,4){ int ny=y+dy[dir]; int nx=x+dx[dir]; if(ny<0||ny>=H||nx<0||nx>=W)continue; int nd=d+1; int nc=c+(2*d+1)*A[ny][nx]; if(dist[ny][nx][nd]<=nc)continue; dist[ny][nx][nd]=nc; que.push(make_tuple(nc,ny*W+nx,nd)); } } cout<<ans<<endl; return 0; }
6問目
最終的にJOI君(そういう名前じゃなかったかも)が得る数列(以下、最終数列と呼ぶ)のL番目がZであったとする。(このZが答え)
C(x):=最終数列における、x以下の値の数がL個以上ならtrue、そうでないならfalse
とすると、Zは、C(x)がtrueとなる最小のxに等しいとわかる。
また、C(x)には単調性があるため、結局二分探索すればいい。
あとは判定関数Cをどうやって実装するんですか？という話なんですけど、まあとりあえずO(N)で実装できます(完)
よって全体でO(NlogN)で解けた。
判定関数を実装するときのコツなんですけど、"ある数列のK番目の値がk以下"⇔"その数列にはk以下の数がK個以上含まれている"
と言い換えると見通しがよくなるかもしれません。
#include<bits/stdc++.h> using namespace std; #define int long long #define rep(i,n) for(int i=0;i<(n);i++) #define pb push_back #define all(v) (v).begin(),(v).end() #define fi first #define se second typedef vector<int>vint; typedef pair<int,int>pint; typedef vector<pint>vpint; template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;} template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;} int N,K,L; int A[222222]; bool C(int val){ int r=N; int c=0; int cnt=0; for(int i=N-1;i>=0;i--){ if(A[i]<=val)c++; while(c-(A[r-1]<=val)>=K){ c-=A[r-1]<=val; r--; } if(c>=K)cnt+=N-r+1; } return cnt>=L; } signed main(){ cin>>N>>K>>L; rep(i,N)cin>>A[i]; int lb=0,ub=N; while(ub-lb>1){ int mid=(ub+lb)/2; if(C(mid))ub=mid; else lb=mid; } cout<<ub<<endl; return 0; }
おわりに
難易度についてですが、去年よりは難しかった気がします。
というか、個人的に4問目がそこそこ難しいと感じました。
あと6問目はあまりJOIらしくないなあと感じました。
