paiza POH enshura #_poh ミッションRENA いもす法(C(picoc互換)/C++/C#/F#/Scala/etc)


http://qiita.com/cielavenir/items/1751c4b57f63b4892593 の続きです。

POH enshura。
ミッションMINAMIは普通に1列ずつ処理すれば解けます。
ミッションRENAは、順当に解くなら、1枠ずつ拾って0で埋めるのを繰り返せば良いです(なでしこプログラムもそういった実装になっているようです)。
しかし、0で埋めたものをまた拾うのは無駄であります。

我々には[いもす法](http://imoz.jp/algorithms/imos_method.html)という大きな武器があるではありませんか。
いもす法を使えば、2回配列を舐めるだけで拾うべきセルの一覧を得ることができます！！

|言語|タイム(最長)|URL|
|:--|:--|:--|
|C|0.01|https://paiza.jp/poh/enshura-rena-ending/c652aec8|
|C++|0.01|https://paiza.jp/poh/enshura-rena-ending/8b42416c|
|D|0.01|https://paiza.jp/poh/enshura-rena-ending/5c789193|
|Go|0.01|https://paiza.jp/poh/enshura-rena-ending/81cfbb2f|
|Swift|0.01|https://paiza.jp/poh/enshura-rena-ending/96d7ec41|
|Rust|0.01|https://paiza.jp/poh/enshura-rena-ending/51560a14|
|ObjC|0.02|https://paiza.jp/poh/enshura-rena-ending/742cb086|
|Python|0.02|https://paiza.jp/poh/enshura-rena-ending/81f275ed|
|C#|0.03|https://paiza.jp/poh/enshura-rena-ending/6c44e819|
|Python3|0.03|https://paiza.jp/poh/enshura-rena-ending/5941a42d|
|VB|0.03|https://paiza.jp/poh/enshura-rena-ending/c925bf8c|
|F#|0.04|https://paiza.jp/poh/enshura-rena-ending/fff57fe1|
|JavaScript|0.05|https://paiza.jp/poh/enshura-rena-ending/f0b457e1|
|Java|0.08|https://paiza.jp/poh/enshura-rena-ending/616fb1ed|
|Ruby|0.09|https://paiza.jp/poh/enshura-rena-ending/29341f2e|
|Bash|0.09|https://paiza.jp/poh/enshura-rena-ending/db861eb5|
|Kotlin|0.09|https://paiza.jp/poh/enshura-rena-ending/38a967f8|
|CoffeeScript|0.13|https://paiza.jp/poh/enshura-rena-ending/4e4159e3|
|Scala|0.37|https://paiza.jp/poh/enshura-rena-ending/d450ad87|

問題サイズがいもす法を使わなくとも解けるサイズのため、ほとんどランタイム起動時間の差になってしまった気がする。

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](https://github.com/zsaleeba/picoc)を使うとchmod +x可能。
ミッションMINAMIがpicoc互換でないのは複文が使えないためfor文を書きづらいことがあったからです。`for(;;i++,s++)`が撥ねられる。

```c: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#

```csharp: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](https://github.com/cielavenir/paiza_solutions/blob/master/poh2/poh2.fs)しておきました。

```fsharp: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

```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](https://github.com/cielavenir/paiza_solutions/tree/master/poh5)をご参照下さい。