http://qiita.com/cielavenir/items/1751c4b57f63b4892593 の続きです。
POH enshura。
ミッションMINAMIは普通に1列ずつ処理すれば解けます。
ミッションRENAは、順当に解くなら、1枠ずつ拾って0で埋めるのを繰り返せば良いです(なでしこプログラムもそういった実装になっているようです)。
しかし、0で埋めたものをまた拾うのは無駄であります。
我々にはいもす法という大きな武器があるではありませんか。
いもす法を使えば、2回配列を舐めるだけで拾うべきセルの一覧を得ることができます！！
問題サイズがいもす法を使わなくとも解けるサイズのため、ほとんどランタイム起動時間の差になってしまった気がする。
C++
paizapoh5_4b.cpp
#include <vector>
#include <cstdio>
char z[9999999];
int get(){
static int input_count=0;
int r=0;
for(;'0'<=z[input_count]&&z[input_count]<='9';)r=r*10+z[input_count++]-'0';
input_count++;
return r;
}
int main(){
fread(z,1,sizeof(z),stdin);
int W=get(),H=get(),Q=get();
std::vector<std::vector<int> >m(H);
std::vector<std::vector<int> >imos(H+1);
for(int h=0;h<H;h++){
m[h].resize(W);
imos[h].resize(W+1);
for(int w=0;w<W;w++){
m[h][w]=get();
}
}
imos[H].resize(W+1);
int s=0;
for(;Q--;){
int w1=get()-1,h1=get()-1,w2=get(),h2=get();
imos[h1][w1]+=1;
imos[h1][w2]-=1;
imos[h2][w1]-=1;
imos[h2][w2]+=1;
}
for(int h=0;h<H;h++)for(int w=1;w<W;w++)imos[h][w]+=imos[h][w-1];
for(int h=1;h<H;h++)for(int w=0;w<W;w++)imos[h][w]+=imos[h-1][w];
for(int h=0;h<H;h++)for(int w=0;w<W;w++)if(imos[h][w]>0)s+=m[h][w];
printf("%d\n",s);
}
C
ちなみにpicocを使うとchmod +x可能。
ミッションMINAMIがpicoc互換でないのは複文が使えないためfor文を書きづらいことがあったからです。for(;;i++,s++)が撥ねられる。
paizapoh5_4b.c
//usr/bin/env picoc $0 - $@;exit
#include <stdio.h>
char z[9999999];
int get(){
static int input_count=0;
int r=0;
for(;'0'<=z[input_count]&&z[input_count]<='9';)r=r*10+z[input_count++]-'0';
input_count++;
return r;
}
int m[100][100],imos[100][100];
int main(){
fread(z,1,sizeof(z),stdin);
int W=get(),H=get(),Q=get();
for(int h=0;h<H;h++){
for(int w=0;w<W;w++){
m[h][w]=get();
}
}
int s=0;
for(;Q--;){
int w1=get()-1,h1=get()-1,w2=get(),h2=get();
imos[h1][w1]+=1;
imos[h1][w2]-=1;
imos[h2][w1]-=1;
imos[h2][w2]+=1;
}
for(int h=0;h<H;h++)for(int w=1;w<W;w++)imos[h][w]+=imos[h][w-1];
for(int h=1;h<H;h++)for(int w=0;w<W;w++)imos[h][w]+=imos[h-1][w];
for(int h=0;h<H;h++)for(int w=0;w<W;w++)if(imos[h][w]>0)s+=m[h][w];
printf("%d\n",s);
return 0;
}
C#
paizapoh5_4b.cs
using System;
using System.Linq;
class PaizaPOH5_4b{
const int SIZE=9999999;
static byte[] z=new byte[SIZE];
static int input_count=0;
static int get(){
int r=0;
for(;'0'<=z[input_count]&&z[input_count]<='9';)r=r*10+z[input_count++]-'0';
input_count++;
return r;
}
static void Main(){
Console.OpenStandardInput().Read(z,0,SIZE);
int W=get(),H=get(),Q=get();
int[,] m=new int[H,W];
int[,] imos=new int[H+1,W+1];
for(int h=0;h<H;h++){
for(int w=0;w<W;w++){
m[h,w]=get();
}
}
int s=0;
for(;Q-->0;){
int w1=get()-1,h1=get()-1,w2=get(),h2=get();
imos[h1,w1]+=1;
imos[h1,w2]-=1;
imos[h2,w1]-=1;
imos[h2,w2]+=1;
}
for(int h=0;h<H;h++)for(int w=1;w<W;w++)imos[h,w]+=imos[h,w-1];
for(int h=1;h<H;h++)for(int w=0;w<W;w++)imos[h,w]+=imos[h-1,w];
for(int h=0;h<H;h++)for(int w=0;w<W;w++)if(imos[h,w]>0)s+=m[h,w];
Console.WriteLine(s);
}
}
F#
多次元配列を作る方法を今まで知らなかったのですが、Array2Dを使うのですね。勉強になりました。
ついでにpaizenもACしておきました。
paizapoh5_4b.fs
open System
let arg:String array=Console.ReadLine().Split(' ')
let W=int(arg.[0])
let H=int(arg.[1])
let Q=int(arg.[2])
let m:int [,]=Array2D.zeroCreate H W
let imos:int [,]=Array2D.zeroCreate (H+1) (W+1)
for h in 0..H-1 do
let arg:String array=Console.ReadLine().Split(' ')
for w in 0..W-1 do
m.[h,w]<-int(arg.[w])
let mutable s=0
for i in 0..Q-1 do
let arg:String array=Console.ReadLine().Split(' ')
let w1=int(arg.[0])-1
let h1=int(arg.[1])-1
let w2=int(arg.[2])
let h2=int(arg.[3])
imos.[h1,w1]<-imos.[h1,w1]+1
imos.[h1,w2]<-imos.[h1,w2]-1
imos.[h2,w1]<-imos.[h2,w1]-1
imos.[h2,w2]<-imos.[h2,w2]+1
for h in 0..H-1 do
for w in 1..W-1 do
imos.[h,w]<-imos.[h,w]+imos.[h,w-1]
for h in 1..H-1 do
for w in 0..W-1 do
imos.[h,w]<-imos.[h,w]+imos.[h-1,w]
for h in 0..H-1 do
for w in 0..W-1 do
if imos.[h,w]>0 then
s<-s+m.[h,w]
Console.WriteLine(s)
Scala
paizapoh5_4b.scala
//usr/bin/env scala $0 $@;exit
object Main{
def main(args:Array[String]){
val Array(w,h,q)=readLine().split(" ").map(_.toInt)
val m=Array.ofDim[Int](h,w)
val imos=Array.ofDim[Int](h+1,w+1)
for(i<-0 until h){
m(i)=readLine().split(" ").map(_.toInt)
}
var s=0
for(i<-0 until q){
val Array(w1,h1,w2,h2)=readLine().split(" ").map(_.toInt)
imos(h1-1)(w1-1)+=1
imos(h1-1)(w2)-=1
imos(h2)(w1-1)-=1
imos(h2)(w2)+=1
}
for(i<-0 until h)for(j<-1 until w)imos(i)(j)+=imos(i)(j-1)
for(i<-1 until h)for(j<-0 until w)imos(i)(j)+=imos(i-1)(j)
for(i<-0 until h)for(j<-0 until w)if(imos(i)(j)>0)s+=m(i)(j)
println(s)
}
}
他はgithubをご参照下さい。