24日目：Beginner 040
24日目(2019/9/9)
AtCoder Beginner Contest 040
解けた問題
A: 赤赤赤赤青
n/2で分岐して、小さければx-1を、大きければN-xを出力したよ。
B: □□□□□
与えられた数値において、作ることができる最大の正方形の一辺はsqrt(n)で求まるので、
最大値をsqrt(n)+1とおいて、一辺の長さを1~最大値まで増やして、いま現状の最小より小さくなったら、更新を繰り返したよ。
#include <iostream> #include <vector> #include <cmath> using namespace std; int main(void){ int n; cin >> n; int l = sqrt(n); int min=1000; for(int i=1;i<l+1;i++){ if(int(n/i) - i + n%i < min){ min = int(n/i) - i + n%i; } } cout << min << endl; return 0; }
解けなかった問題
C:柱柱柱柱柱
多分DPの問題だとは思うんだけど、うまく実装できなかった。
最終地点のコストを0として、(abs(a[i]-abs[i-1])と(abs(a[i]-abs[i-2])で小さい方を加算していく形で最小コストを求めようとしたけどテストケースを全部パスすることはできませんでした。
解説を見てみる
C
予想通りDPでした。後ろからではなく前から順に求めていき、それぞれの計算は2パターンから選択すればいいみたい。
23日目：Beginner 39
23日目(2019/9/9)
AtCoder Beginner Contest 039
解けた問題
A:高橋直体
表面積の合計だから、A*(B+C)+B*Cを2倍にしたものを出力したよ！
B:エージェント高橋君
cmathをインクルードして、sqrt(sqrt(N))で求められたよ。
C:ピアニスト高橋君
まず、ピアノで連続で白になっているところは、ミ->ファとシ->ドの二種類です。
だからそこに注目して、連続でWが出てきたタイミングをスタートとして、4個目と5個目が等しければ、今はドに、6個目と7個目が等しければ今はファにいることがわかります。白鍵盤をカウントしておいて、今現在の位置から白鍵盤の数を引けば求まりますね！
// C++のテンプレート #include <iostream> #include <string> #include <algorithm> #include <vector> using namespace std; int main(void){ string S; cin >> S; string MS[7] = {"Do","Re","Mi","Fa","So","La","Si"}; char temp=S[0]; int count=0; for(int i=1;i<S.length();i++){ if(temp != S[i]){ //前と異なるなら判別基準にならない。 temp = S[i]; if(temp == 'W') count++; continue; } if(temp == S[i]){ //前と同じなら if(S[i+6]==S[i+7]){ //今ファで、シとドが等しい場合 cout << MS[(9-count)%7] << endl; } if(S[i+4]==S[i+5]){ //今ドで、ミとファが等しい場合 cout << MS[(13 - count) % 7] << endl; } break; } } }
22日目： Beginner 140
22日目(2019/9/8)
AtCoder Beginner Contest 140
10:00開始で、11時には予定が入っていたので、
45分くらい取り組みました！久々のリアタイ参加！
A~C問題を解いてレーティングは315(+67)になりました。
んー…フル参加できたらD問題くらいまでは解けたかもしれないと考えるとちょっと悔しいかもだけど順調に上がってきたので文句なしです！
振り返っていこう。
解けた問題
A: Password
3桁のパスワードを設定するらしい。
1~N以下の数字のみを使うらしいので、N*N*Nを出力すればいいですね！
B:Buffet
ビュッフェってこう書くんだ…。
まず情報を整理すると、Aで出てくる順番がわかる。
なので、i回目の食事に得られる満足度はB[A[i]]で与えられる
連続で食べた時のボーナスA[i-1]+1 == A[i]のときに、C[A[i-1]-1]を満足度に加算するように実装しました。
// C++のテンプレート #include <iostream> #include <string> #include <algorithm> #include <vector> using namespace std; int main(void){ int N; cin >> N; vector<int> A(N); vector<int> B(N); vector<int> C(N-1); for(int i=0;i<N;i++){ cin >> A[i]; } for(int i=0;i<N;i++){ cin >> B[i]; } for(int i=0;i<N-1;i++){ cin >> C[i]; } int sat = B[A[0]-1]; for(int i=1;i<N;i++){ sat += B[A[i]-1]; if(A[i-1]+1 == A[i]){ sat += C[A[i-1]-1]; } } cout << sat << endl; }
C : Maximal Value
max(Ai,Ai+1)<=Bを満たすので、まず左右の要素A[0],A[N-1]は、B[0]とB[N-2]になるなぁ、と考え、その間の要素を埋めていこうと考えました。
で、ルールを考えると、
| A | B[0] | min(B[0],B[1]) | min(B[1],B[2]) | min(B[2],B[3]) | |||
| B | B[0] | B[1] | B[2] |
となることに気づいたので、実装しました。
// C++のテンプレート #include <iostream> #include <string> #include <algorithm> #include <vector> using namespace std; int main(void){ int N; cin >> N; vector<int> A(N); vector<int> B(N-1); for(int i=0;i<N-1;i++){ cin >> B[i]; } int max=B[0]; int sum=B[0]; for(int i=0;i<N-1;i++){ if(i==N-2){ sum += B[i]; }else{ sum += min(B[i],B[i+1]); } } cout << sum << endl; }
解けなかった問題
D:Face Produces Unhappiness
この問題に取り組む時点で30分くらい経過していたので、残り10分ほどでした。
同じ向きを多くの人が向いている状態を作り出すにはどうしたら良いか、色々考えたけど良い手法が思いつかず…。
解説を見てみる
向きを変える操作を行うと、一回につき最大で2人を幸福にすることができる。ということにまず気づけなかった（注目しなかった）のが多分最大の敗因。 端の部分以外は、この操作を行うことによって、2人ずつ増やすことができ、端では1人のみを増やすことができるので、その回数を考えてみると答えが出てくるみたいですね。
21日:Beginner 038
21日目(2019/9/6)
AtCoder Beginner Contest 037
解けた問題
A:お茶
stringで受け取って、str[string.size()-1]で分岐！
B:ディスプレイ
高さを揃えたいということは、ディスプレイの縦か横のサイズが一緒ならばよいので、W1==W2||W1==H2||H1==W2||H1==H2を満たせばいいね
C:単調増加
与えられた数列に対して、左を固定して、条件を満たす限り右を伸ばす。
条件を満たさなくなったら、右から左を引いた長さr-l+1を底辺に、右から左を引いた長さ+1r-l+1を高さとして、三角形の面積を足していくイメージ！
| 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|
| 3,3 | ||||
| 2,2 | 2,3 | 2,5 | ||
| 1,1 | 1,2 | 1,3 | 1,4 | 1,5 |
組み合わせを三角形のイメージで捉えて加算していく方法を取りました。
// C++のテンプレート #include <iostream> #include <string> #include <algorithm> #include <vector> using namespace std; int main(void){ int N; cin >> N; vector<int> a(N); for(int i=0;i<N;i++) cin >> a[i]; long temp=a[0],l=0,r=0,count=0; for(int i=1;i<N;i++){ if(temp<a[i]){ r=i; // 条件を満たすなら右を伸ばす。 }else{ //三角をイメージ。 count += (r-l+1)*(r-l+2)/2; // temp,l,rを更新 l = i; r = i; } if(i==N-1){ count += (r - l + 1) * (r - l + 2) / 2; } temp = a[i]; //cout << i << ":l " << l << " :r " << r << " :count "<< count << endl; } cout << count << endl; }
解けなかった問題
D:プレゼント
箱がたくさん与えられて可能な限りマトリョーシカにする問題。
サンプルケースはパスしたんだけど、テストケースでWA...
とりあえず書いたコードがこっち（WAです)
// C++のテンプレート #include <iostream> #include <string> #include <algorithm> #include <vector> using namespace std; class Box{ public: int h,w; Box(int height,int width){ h = height; w = width; } bool operator< (const Box &another) const{ return h < another.h; } }; int main(void){ int N; cin >> N; vector<Box> boxs; int h,w; for(int i=0;i<N;i++){ cin >> h >> w; boxs.push_back(Box(h,w)); } // for(int i=0;i<N;i++) // cout << boxs[i].h << boxs[i].w << endl; sort(boxs.begin(),boxs.end()); // cout << "----end sort ---" << endl; // for (int i = 0; i < N; i++) // cout << boxs[i].h << boxs[i].w << endl; vector<int> width_min; int temp_min = boxs[0].w; for (int i=1;i<N;i++){ if(boxs[i-1].h == boxs[i].h){ //一個前と同じなら最小を更新していく。 if(temp_min > boxs[i].w){ temp_min = boxs[i].w; } }else{ //一個前と異なるなら、最小をpushする。 width_min.push_back(temp_min); temp_min = boxs[i].w; } if(i == N-1){ width_min.push_back(temp_min); } } // for(int i=0;i<width_min.size();i++){ // cout << width_min[i] << " " ; // } // cout << endl; int max_count = 0; int temp=-1; for(int loop=0;loop<width_min.size();loop++){ if(width_min[temp]<width_min[loop]&&temp!=-1){ continue; }else{ temp = loop; } int count = 1; int idx = loop; for (int i = loop+1; i < width_min.size(); i++) { if (width_min[idx] < width_min[i]) { count++; idx = i; } } if(max_count < count){ max_count = count; } } cout << max_count << endl; }
この時考えていたのは、まず箱の高さでソート、次に箱の幅で、高さが同じものの中から最小のものを取り出し、vectorにpush_backする。
次に取り出した箱の横幅のなかで最小なものから、Ai<A(i+1)（要素番号が小さいほうが小さい)を満たすものの中で最大のものを見つける…、と答えになるかなって思って、ここで2重ループを使わずに実装する方法が思いつかなかった…
間違ってるのが前のフェーズからなのか、あとからなのかはまだわかってないです、とりあえず解説見てみよう。
解説を見てみる
D
DP(動的計画法)で考える。
メモ化再帰(外部変数にメモしつつ、同じものを処理しないようにする)を用いる。
dp[i]:=i番目の箱を一番外側として、何重の入れ子にできるかを考えてゆくと、最大数が求まる。(O(N2))
これで部分点は取れる。
まずはメモ化再帰実装できるところからかなぁ。
20日目：Beginner037
20日目(2019/9/5)
AtCoder Beginner Contest 037
解けた問題
A:饅頭
数買うだけなら、安い方を限界まで買えばいいよね。ってことでif文で分岐して、大きい方でCを割った結果を出力したよ。
B:編集
問題サイズがそこまで大きくなかったので二重ループで回しても間に合うな、と思って順当に更新していって出力しました。
#include <iostream> #include <vector> using namespace std; int main(void){ int N,Q; cin >> N >> Q; vector<int> a(N); int L,R,T; for(int i=0;i<Q;i++){ cin >> L >> R >> T; for(int j=L-1;j<R;j++){ a[j] = T; } } for(int i=0;i<N;i++){ cout << a[i] << endl; } }
C:総和
問題サイズ的に二重ループを回したら間に合わないなって思って、二重ループにならない方向性で考えました。
端っこの方からKまでは、1~K個と順番に足す回数が増えていき、
K番目からN-K-1番目まではK個足して、
N-K~N-1まではK~1まで減っていく、という考えでかけたものを足して出力、細かいところでめちゃくちゃミスしたなぁ…。
重なる場合とかも考慮してあげよう。
#include <iostream> #include <vector> using namespace std; int main(void){ int N,K; long long sum=0; cin >> N >> K; vector<long long> a(N); for(int i=0;i<N;i++){ cin >> a[i]; } int judge = K > N-K+1 ? N-K+1 : K; for(int i=0;i<(N+1)/2;i++){ // // cout << i <<":"<<a[i] << "|" << N-i-1 << a[N-i-1] << endl; if (i<judge){ sum += a[i]*(i+1); if(i!=N-i-1) sum += a[N-i-1]*(i+1); }else{ sum += a[i]*judge; if(i!=N-i-1) sum += a[N-i-1]*judge; } } cout << sum << endl; }
解説を見てみる
今日はC問題まで解きました。
C問題は、全体の和を求めておいて実装する方法もあるみたい。
S[0]=a[0]~a[K-1]までの和を求めて、S[1] = S[0]-a[0]+a[K]みたいな方法で和を求めてももしかしたら計算時間的に余裕あるかもな～なんて思いました。
19日目 Beginner 36
19日目(2019/9/4)
AtCoder Beginner Contest 036
解けた問題
A:お茶
Aという単位で買うなら
(A+B-1)/Aを出力すれば求める答えが出ます
B:回転
vector<string> s(N)として定義して、文字列を受け取る。最近ちょっとvectorの扱いにもなれてきたかな？
内部でデータを保持してないといけないわけでもないので、string型をchar型の配列としてみて、回転したあとの順番で出力しました。
// C++のテンプレート #include <iostream> #include <string> #include <algorithm> #include <vector> using namespace std; int main(void){ int N; cin >> N; vector<string> s(N); for(int i=0;i<N;i++) cin >> s[i]; for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ cout<<s[N-j-1][i]; } cout << endl; } }
C:座圧
とりあえず、問題を理解するのにちょっと時間がかかりましたｗ
つまるところ、この問題の内容を読み解いていくと、
- aの要素を小さい順に出力しよう。
- ただし、同じ値のときはそれは同じ値として表示しよう。
ということなので、もとのindexを保持しつつ、データをソートして、ソートしたときに小さい順に重複したものは同じ値として値を保持して、元の順番で出力しよう。ってことですね。
Dataクラスを宣言して、メンバ変数として、index,data,順番を保持する変数をもたせました。sort関数で使うために、operator<をオーバーロード。dataでソートできるよにしました。
実装はこんな感じ！（もっとスマートな書き方はありそうですね）
```cpp // C++のテンプレート
include
include
include
include
using namespace std;
class Data{ public: int index; int data; int s; bool operator< (const Data &another) const{ return data < another.data; } Data(int i,int d,int sort){ index = i; data = d; s=sort; } };
int main(void){ int N; cin >> N; vector a; vector b; int temp; for(int i=0;i<N;i++){ cin >> temp; a.push_back(Data(i, temp,0)); } sort(a.begin(),a.end());
a[0].s = 0;
for(int i=1;i<N;i++){
if(a[i-1].data==a[i].data)
a[i].s = a[i-1].s;
else
a[i].s = a[i-1].s+1;
}
for (int i = 0; i < N; i++)
{
//cout << a[i].index << ":" << a[i].data << ":" << a[i].s <<endl;
b.push_back(Data(a[i].data,a[i].index,a[i].s));
}
sort(b.begin(),b.end());
for(int i=0;i<N;i++){
cout << b[i].s << endl;
}
} ```
解けなかった問題
D:塗り絵
んー、これが頂点染色問題って呼ばれるやつなのかな？アルゴリズムを何も覚えてなくて、どう実装したら良いんだろうってなりました。入力例を見る限り組合せ爆発のように通りが増えていきそうなので、一つ一つ数えるのは絶望的だろうと思い、数学的に計算する方法を考えたけどよくわからず…。
解説を見てみる
C
連想配列 mapを使うといいらしい。勉強しておいたほうが良いかも！
D
問題として与えられているものは、木構造である。N-1なので確かに。この問題はtree DP（木構造の動的計画法?）の簡単な場合らしい。
18日目 Beginner 35
18日目(2019/9/3)
AtCoder Beginner Contest 035
解けた問題
A:テレビ
実装は雑だけど、4:3か16:9に限られるということだったので、float型で受け取って、W/Hが1.4より小さければ4:3,そうじゃなければ16:9を表示するようにしたよ。
B:ドローン
マンハッタン距離を求めるためにまず、int型でLR,UDというx軸、y軸を表す変数を定義して、LRUDそれぞれが出た回数によって、今分かる範囲でどの座標にいるのか求めた。
次に?の回数をカウントして、T==1なら、abs(LR)+abs(UD)に?の回数を加えて出力。これで部分点100点がもらえるはず。
101点をもらうためには、引き算をすれば良いのだけど、問題になるのはマンハッタン距離-?がマイナスになるときのはず。マイナスになった場合は、0になったときに、どこかには動かないといけないので、原点と距離1の場所を行ったり来たりするはず。とおもって、?-マンハッタン距離を2で割ったあまりによって、0か1に分岐して表示するようにしたよ。
// C++のテンプレート #include <iostream> #include <string> #include <algorithm> #include <vector> #include <cmath> using namespace std; int main(void){ string S; int T; int pos_x=0,pos_y=0; int LR=0,UD=0,Q=0; cin >> S >> T; for(int i=0;i<S.size();i++){ if(S[i]=='L'){ LR--; }else if(S[i]=='R'){ LR++; }else if(S[i]=='U'){ UD++; }else if(S[i]=='D'){ UD--; }else{ Q++; } } if(T==1){ cout << abs(LR)+abs(UD)+Q << endl; }else if(T==2){ int M_dist=abs(LR)+abs(UD); if(M_dist>=Q){ cout << M_dist - Q << endl; }else if((Q-M_dist)%2==0){ cout << 0 << endl; }else{ cout << 1 << endl; } } }
C:オセロ
L~Rの範囲がQ回与えられて、その範囲が向きが変わる問題。
きっと問題サイズ的にO(N2)になってしまうと100点解法ではないんだろうなぁと思い、lとrの出てきた数値をカウントして、出力するときに、countという変数にlが出たタイミングでlの数だけ足して、rが出たタイミングでrの数だけ引くようにしたものを2で割ったときのあまりを表示するようにしました。（説明下手）
これで二重ループを回避できるので、オーダーはNになって100点もらえました～！
// C++のテンプレート #include <iostream> #include <string> #include <algorithm> #include <vector> using namespace std; int main(void){ int N,Q; cin >> N >> Q; vector<int> left(N); vector<int> right(N); int l,r; for(int i=0;i<Q;i++){ cin >> l >> r; left[l-1]++; right[r-1]++; } int count=0; for(int i=0;i<N;i++){ count+=left[i]; count-=right[i-1]; cout << count%2 ; } cout << endl; }
解けなかった問題
今日はC問題まで解いたよ、日付変わっちゃうので焦ってブログ書いてますｗ
