今回、ある理由からC問題はKotlinを使ってみました。
A – 流行
文章の通りです。入力*2を出力すればOKです。
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
cin>>N;
cout<<2*N<<endl;
}
B – 回転
180度回転するということは、Y軸X軸ともに反転するということです。
なので、以下のように出力すればOKです。
c3,3 c3,2 c3,1 c3,0 c2,3 c2,2 c2,1 c2,0 c1,3 c1,2 c1,1 c1,0 c0,3 c0,2 c0,1 c0,0
#include<bits/stdc++.h>
using namespace std;
int main(){
char c[4][4];
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
cin>>c[i][j];
}
}
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
cout<<c[3-i][3-j];
if(j==3) cout<<endl;
else cout<<" ";
}
}
}
C – 入れ替え
一番簡単な方法は愚直にシミュレーションする方法ですが、O(N)のためTLEしてしまいます。
部分点のN<=50ではTLEしないため、部分点は取得できます。
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
cin>>N;
int c[6]={1,2,3,4,5,6};
for(int i=0;i<N;i++){
swap(c[i%5],c[i%5+1]);
}
cout<<c[0]<<c[1]<<c[2]<<c[3]<<c[4]<<c[5]<<endl;
}
制限時間ギリギリでACしちゃいました＼(^o^)／
さすがC++ですね。O(10^9)でも簡易な処理だと2s以内で終わっちゃうようです。
これだと消化不良感があるので、上記コードをKotlinで書きなおしました。
fun main(args: Array<String>) {
val n = readLine()!!.toInt()
val c = arrayOf(1,2,3,4,5,6)
for(i in 0 until n){
var tmp=c[i%5]
c[i%5]=c[i%5+1]
c[i%5+1]=tmp
}
for(i in 0 until 6){
print(c[i])
}
}無事(?)TLEしました。
ここから速度改善をします。
Nを増やしたときの動きを観察します。
N=1 213456 N=2 231456 N=3 234156 ... N=29 123465 N=30 123456 N=31 213456
どうもN=30でループしているようです。
つまり、31回の操作後の配列=1回の操作後の配列となります。
30回操作することは無駄であるため、%30で剰余を取った数だけシミュレーションすればOKです。
fun main(args: Array<String>) {
val n = readLine()!!.toInt()%30
val c = arrayOf(1,2,3,4,5,6)
for(i in 0 until n){
var tmp=c[i%5]
c[i%5]=c[i%5+1]
c[i%5+1]=tmp
}
for(i in 0 until 6){
print(c[i])
}
}D – マーブル
R,G,Bそれぞれのマーブルを一番近い場所に愚直に置いていくやり方が良さそうです。
(Rなら、-100,-99,-101,-98,-102…と順に近いほうに送っていく)
この解法で1<=RGB<=40の30点はOKです。
#include<bits/stdc++.h>
using namespace std;
int main(){
int R,G,B;
cin>>R>>G>>B;
int ans=0;
R--;
G--;
B--;
for(int i=1;R>0;i++){
ans+=i*min(2,R);
R-=2;
}
for(int i=1;G>0;i++){
ans+=i*min(2,G);
G-=2;
}
for(int i=1;B>0;i++){
ans+=i*min(2,B);
B-=2;
}
cout<<ans<<endl;
}
ただ、満点解法の場合NGです。というのもマーブルの数が多い場合、どこかでぶつかってしまうからです。
全探索を単純にするとTLEのため、一つ基準のマーブルを決め、それを全探索します。
真ん中のマーブルの位置が決まれば、左右のマーブルは簡単に決まりそうだったため、Gのマーブルをどこに置くかを全探索。それを元にR,Bのマーブルの位置を決めて最小を取る…
としたかったのですが、以下のACコードをご参照ください。
#include<bits/stdc++.h>
using namespace std;
int main(){
int R,G,B;
cin>>R>>G>>B;
int ans=INT_MAX;
//900,1000,1100で考える
for(int i=1000-G;i<=1000+1;i++){
int tR=R;
int tB=B;
int f[2000]={0};
int c=0;
for(int j=i;j<=i+G-1;j++){
f[j]=1;
c+=abs(1000-j);
}
if(f[900]==0) {
f[900]=1;
tR--;
}
bool tobi=true;
for(int j=1;tR>0;j++){
if(f[900+j]==0&&tobi){
f[900+j]=1;
tR--;
c+=j;
}
else tobi=false;
if(tR<=0) break;
if(f[900-j]==0){
f[900-j]=1;
tR--;
c+=j;
}
if(tR<=0) break;
}
if(f[1100]==0) {
f[1100]=1;
tB--;
}
tobi=true;
for(int j=1;tB>0;j++){
if(f[1100+j]==0){
f[1100+j]=1;
tB--;
c+=j;
}
if(tB<=0) break;
if(f[1100-j]==0&&tobi){
f[1100-j]=1;
tB--;
c+=j;
}
else tobi=false;
if(tB<=0) break;
}
ans=min(c,ans);
c=0;
for(int j=0;j<2000;j++) f[j]=0;
for(int j=i;j<=i+G-1;j++){
f[j]=1;
c+=abs(1000-j);
}
tR=R;
tB=B;
if(f[900]==0) {
f[900]=1;
tR--;
}
for(int j=1;tR>0;j++){
if(f[900+j]==0){
f[900+j]=1;
tR--;
c+=j;
}
if(tR<=0) break;
if(f[900-j]==0){
f[900-j]=1;
tR--;
c+=j;
}
if(tR<=0) break;
}
if(f[1100]==0) {
f[1100]=1;
tB--;
}
for(int j=1;tB>0;j++){
if(f[1100+j]==0){
f[1100+j]=1;
tB--;
c+=j;
}
if(tB<=0) break;
if(f[1100-j]==0){
f[1100-j]=1;
tB--;
c+=j;
}
if(tB<=0) break;
}
ans=min(c,ans);
}
cout<<ans<<endl;
}
ヤバそうでしょ？実際ヤバいです。
Gは連続している(GGGRGGGみたいに割り込む配置や、GGG空GGGみたいに間に何も入っていない箱がない)のが最適と考え、連続区間を-G～Gの範囲内で動かしました。
残りのRとBは近いところにマーブルを置いていくのですが、この際、飛越を許容するかしないかの2パターン求めました。(RRRGGGRRBBBみたいなパターン)
全探索の場合、思いのほか考えるケースが多かったです。
Atcoderの公式解説を見たのですが、DPで求めるのが一番素直かな？と思いました。
(後で解いておきます＞ ＜)
コメント
[…] […]