今回のコンテストはたこ焼きコンテストとなっています。
A – おいしいたこ焼きの作り方
算数の問題ですね。xごとに1個ずつ作れるので、yをxで割って切り捨てた数が答えになります。
#include<bits/stdc++.h>
using namespace std;
int main(){
int x,y;
cin>>x>>y;
cout<<y/x<<endl;
}
B – おいしいたこ焼きの食べ方
最小値を出力する問題。
これも特に言うことはないかと思います。
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
cin>>N;
int mn=INT_MAX;
for(int i=0;i<N;i++){
int T;
cin>>T;
mn=min(mn,T);
}
cout<<mn<<endl;
}
この方法でやる場合は、minの初期値に注意です。
C++なら、INT_MAXでint型の最大値が持ってこれるので、迷えばこれでOKかと思います。
(+1でも足すとオーバーフローしちゃうので、その点は注意です。)
C – おいしいたこ焼きの売り方
B1秒後に一人目が来たときに、売れるたこ焼きが複数ある場合、どれを売るのが正解か？というところが悩みどころかと思います。
正解は、T秒以内で最も早くできたたこ焼きを売るのが正解です。
遅くできたたこ焼きより、早くできたたこ焼きの方がB2,B3..秒後にTを越えるタイミングが早いです。
つまり、その後に来る人が買える可能性が低くなります。
同じたこ焼きを売らないように、フラグ周りに気を付けながら実装していきます。
#include<bits/stdc++.h>
using namespace std;
int main(){
int T,N;
cin>>T>>N;
int A[N];
for(int i=0;i<N;i++){
cin>>A[i];
}
int M;
cin>>M;
int B[M];
for(int i=0;i<M;i++){
cin>>B[i];
}
int c=0;
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
if(B[i]-A[j]>=0&&B[i]-A[j]<=T){
c++;
A[j]=-100000;
break;
}
}
}
if(c==M) cout<<"yes"<<endl;
else cout<<"no"<<endl;
}
D – おいしいたこ焼きの焼き方
直ぐに思い浮かぶのは愚直解です。
全通りの四角形を試して、その中でP以下の面積であるものから最大を選びます。
50*50=2500から2点を選ぶため、2500C2=3123750通り
クエリが最大2500です。
よって、愚直解では最大ケースで8.0*10^9ほどの計算量になりTLEしてしまいます。ただ、部分点のN<=5は取れます。
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
cin>>N;
int D[N][N];
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
cin>>D[i][j];
}
}
int Q;
cin>>Q;
while(Q-->0){
int P;
cin>>P;
int ans=0;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
for(int k=0;k<N;k++){
int c[N];
if(i+k>=N) break;
int sum=0;
for(int l=0;l<N;l++){
if(j+l>=N) break;
if((k+1)*(l+1)>P) break;
if(k==0) c[l]=D[i+k][j+l];
else c[l]+=D[i+k][j+l];
//cout<<i<<","<<j<<","<<k<<","<<l<<","<<c[l]<<endl;
sum+=c[l];
ans=max(ans,sum);
}
}
}
}
cout<<ans<<endl;
}
}
ACしちゃいました＼(^o^)／
ABC004のC – 入れ替えもそうでしたが、部分点解でACするの辞めてくれ＞ ＜
ということで、奥の手Kotolinで書きなおしました。
fun main(args: Array<String>) {
val n = readLine()!!.toInt()
val D = List(n) {
readLine()!!.split(" ").map(String::toInt)
}
val Q = readLine()!!.toInt()
for(q in 0 until Q){
val P = readLine()!!.toInt()
var ans=0
for(i in 0 until n){
for(j in 0 until n){
val c = Array<Int>(n, {0})
for(k in 0 until n){
if(i+k>=n) break;
var sum=0;
for(l in 0 until n){
if(j+l>=n) break
if((k+1)*(l+1)>P) break
c[l]+=D[i+k][j+l]
sum+=c[l]
if(ans<sum) ans=sum
}
}
}
}
println(ans)
}
}無事(?)TLEしました。高速化していきましょう。
といっても簡単で、毎クエリごとに計算せず、全範囲(最大2500C2=3123750通り)を求めて、n*n以下の最大を事前計算しておくだけです。
こうすることで、毎クエリの計算が事前計算を呼び出すだけのO(1)になり、計算量がグッと減ります。
fun main(args: Array<String>) {
val n = readLine()!!.toInt()
val D = List(n) {
readLine()!!.split(" ").map(String::toInt)
}
var ans=Array<Int>(n*n+1, {0})
for(i in 0 until n){
for(j in 0 until n){
val c = Array<Int>(n, {0})
for(k in 0 until n){
if(i+k>=n) break;
var sum=0;
for(l in 0 until n){
if(j+l>=n) break
c[l]+=D[i+k][j+l]
sum+=c[l]
if((k+1)*(l+1)>n*n) break
if(ans[(k+1)*(l+1)]<sum) ans[(k+1)*(l+1)]=sum
}
}
}
}
for(i in 1 until n*n+1){
if(ans[i]<ans[i-1]) ans[i]=ans[i-1]
}
val Q = readLine()!!.toInt()
for(q in 0 until Q){
val P = readLine()!!.toInt()
println(ans[P])
}
}おまけ：二次元累積和の解説
Dの解説用に書きましたが、私が書いていたコードはそもそも範囲を高速に求められていたためボツ。消すのもアレなので、供養として置いておきます。
範囲を高速に求める方法に累積和があります。
1次元の累積和は以下のようなものです。
A1 A2 A3 A4 A5...AN 累積和：A1 A1+A2 A1+A2+A3 A1+A2+A3+A4 A1+A2+A3+A4+A5...A1+A2+A3+A4+A5+...+AN A3～A7の範囲を求めたい場合、 A7の累積和(A1+A2+...A7)-A2の累積和(A1+A2) をすればA3+A4+A5+A6+A7が残り、A3～A7の範囲になる。
これを二次元に拡張します。
ここの範囲を求める場合 . . . . . . . . . . . . x x . . . x x . . . . . . 以下の計算をまずする x x x x . x x x x . x x . . . x x x x . x x x x . x x . . . x x x x . - . . . . . - x x . . . x x x x . . . . . . x x . . . . . . . . . . . . . . . . . . 左上の2*2のエリアが1回余分に引かれているので x x . . . x x . . . . . . . . . . . . . . . . . . を加えれば、答えになる。 事前に左上からの累積を計算すればO(1)で範囲が求められる！
コメント