D問題が解けず300点の258位でした……。まだ解く速さを強く意識しようという段階でもない気はするので、点数を求めるという意味でせめてD問題の部分点は取りたかったですね。
以下各問感想
A問題『お茶』
消費時間 2分くらい 特になし
B問題『ディスプレイ』
消費時間 5分くらい+WA1回 両方のディスプレイを90度回転させたW1==W2の条件を落としていて一回WA出しました。なぜかどちらか1つだけ回すか、両方そのままかの3パターンしか考えていませんでした。残念。
C問題『単調増加』
消費時間 50分くらい+WA1回
そこから何個の単調増加数列が取れるかを後ろからメモしていけばいいんだろうなと考えました。ただちょっと問題なのは、計算量をとくに見積もったわけではなくたぶん大丈夫だろうみたいな感じで方針を立ててしまっているので、ちゃんとこれがになってることとか与えられる
の大きさがどうとか考えられるようにならなくてはいけませんね。WA出したのも、ansをlong longで宣言していなかったからで、そういった感覚の鈍さがそのまま現れています。
解説動画だと尺取り法を使っていて、計算量の考え方がとてもわかりやすかったです。
#include <bits/stdc++.h> #define REP(i,n) for (int i=0;i<(n);i++) using namespace std; int main() { int n; long long int ans=0; scanf("%d",&n); vector<int> a(n),m(n); REP(i,n){ scanf("%d",&a[i]); m[i]=1; } for(int i=n-1;i>=1;i--){ if(a[i]>a[i-1]){ m[i-1]+=m[i]; } ans+=m[i]; } ans+=m[0]; printf("%lld\n",ans); }
D問題『プレゼント』
ある箱に何個の箱が入るかを上手くメモしていけば解けるんだろうと思いましたが、メモを更新していく順番が間違っているせいか更新の際の対象をうまく取れていないのか、部分点すら取れませんでした。サンプルは通るだけに原因がわかりにくくて直せませんでした。
構造体のソートの仕方がちゃんとわかっておらず、まだおっかなびっくりで書いているので自在にやりたいことをコードに落とし込めません。というか整数2つの組ならpairとか使うべきなのか。慣れなきゃなぁ。
#include <bits/stdc++.h> #define REP(i,n) for (int i=0;i<(n);i++) using namespace std; struct box{ int h,w; bool operator<( const box& right) const { return h == right.h ? w < right.w : h < right.h; } }; int main() { int n; scanf("%d",&n); vector<box> b(n); vector<int> m(n); REP(i,n){ int w,h; scanf("%d %d",&w, &h); b[i].w = w; b[i].h = h; m[i]=1; } sort(b.begin(),b.end()); for(int i=n-2;i>=0;i--){ int tmp=0; for(int j=0;j<n;j++){ if(b[j].h>b[i].h && b[j].w>b[i].w){ tmp=max(tmp,m[j]); } } m[i]+=tmp; } printf("%d\n",m[0]); }
