読者です 読者をやめる 読者になる 読者になる

紙媒体で管理するとなくなりがちなのでブログで進捗などを管理することにしました
※殆どの記事は自分自身のためだけにかいています.他人に見せられるレベルには至っていません...

enumerate

alphabet_list = ['a','b','c','d','e']
for i in range(len(alphabet_list)):
	print(alphabet_list[i])


for i,alphabet in enumerate(alphabet_list):
	print('%d %s'%(i+1,alphabet))

上のようにC++Javaのように添字に対応させるのではなく下のようにenumerateでやると便利.

for i,alphabet in enumerate(alphabet_list,1):
	print('%d %s'%(i,alphabet))

またenumerate(list,カウンタをスタートする番号)で1から始められる.

ABC035_C

一列に並んだオセロ(最初は全て黒)を指定された左と右の位置で反転を繰り返すという問題.
普通にやっていたら配列サイズ200,000、指定位置の個数や左,右の範囲が大きい場合でTLEを起こす.
普通にやった場合の解

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a[200010]={0};
    int n,q,l,r;
    cin>>n>>q;
    
    while(q--){
        cin>>l>>r;
        for(int i=l;i<=r;i++){
            a[i] = ~a[i];
        }
    }
    for(int i=1;i<=n;i++){
        cout<<(a[i]==0?0:1);
    }
    cout<<endl;
    return 0;
}

早くするには「いもす法」を使うらしい.
ここで例として(1,4),(2,5)が与えられる場合を考える.
f:id:umashika5555:20170312210120j:plain
上図の□は反転回数を表している.つまり1,5は1回反転なので白,2,3,4,は2回反転なので黒.
このように加算していく.これを早く処理する.
まず(1,4)が与えられた時にはじめの1を+1し終わりの次の数の5を-1する.
次に(2,5)が与えられた時にはじめの2を+1し終わりの次の数の6を-1する.
最後に累積和を取る.
すると上の処理と同じ結果になる.
f:id:umashika5555:20170312210320j:plain
これを使って実装したコードは下のようになった.

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,q,l,r,a[200010]={0};
    cin>>n>>q;
    while(q--){
        cin>>l>>r;
        a[l]++;
        a[r+1]--;
    }
    for(int i=1;i<n;i++){
        a[i+1]+=a[i];
    }
    for(int i=1;i<=n;i++){
        cout<<(a[i]%2?1:0);
    }
    cout<<endl;
    return 0;
}

分割統治法

分割統治法を用いて最大値を求める.

#include <bits/stdc++.h>
using namespace std;
int findMaximum(int A[],int left,int right)
{
	int u,v,m,x,l=left,r=right;
	m = (l+r)/2;
	if(l==r-1){
		return A[l];
	}else{
		u = findMaximum(A,l,m);
		v = findMaximum(A,m,r);
		x = max(u,v);
	}
	return x;
}


int main()
{
	int A[10]={5,2,1,10,100,3,1,82,-1,-40};
	cout<<findMaximum(A,0,10)<<endl;
	return 0;
}

lower_bound()

lower_bound()について

int A[14] = {1,1,2,2,2,4,5,5,6,8,8,8,10,15};
int *pos;
int idx;

pos = lower_bound(A,A+14,3);//3以上の値の先頭のものを指す
idx = distance(A,pos);//Aは0番目, posは5番目を指しているので5

ちなみに要素の最大値よりも大きい数を指定した場合

int A[14]={1,1,2,2,2,4,5,5,6,8,8,8,10,15};
int *pos;
pos = lower_bound(A,A+14,16);
cout<<*pos<<endl;//-1282435328

-1282435328という値が返ってきた.
lower_bound()で探索を行う.

if(A[*lower_bound(A,A+n,key)]==key)
	return distance(A,lower_bound(A,A+n,key))
else 
	return NOT_FOUND

配列上の初めてkeyを超える値がkeyならばその位置を返し,それがkeyでなければNOT_FOUNDを返す.

#include <bits/stdc++.h>
using namespace std;
#define NOT_FOUND -1
int search(int A[],int n,int key)
{
	int *pos = lower_bound(A,A+14,key);
	if(*pos==key)
		return distance(A,pos);
	else
		return NOT_FOUND;
}

int main()
{
	int A[14]={1,1,2,2,2,4,5,5,6,8,8,8,10,15};
	cout<<search(A,14,3)<<endl;//-1
	cout<<search(A,14,10)<<endl;//12
	return 0;
}

二分探索

#include <bits/stdc++.h>
using namespace std;
#define NOT_FOUND -1

int binary_search(int A[],int n,int key)
{
	int left = 0;
	int right =n;
	while(left<right){
		int mid = (left+right)/2;
		if(A[mid]==key){
			return mid;
		}else if(key<A[mid]){
			right = mid;
		}else{
			left = mid+1;
		}
	}
	return NOT_FOUND;
}

int main()
{
	int A[11] = {1,2,2,3,5,7,10,11,11,12,41};
	cout<<binary_search(A,11,2)<<endl;//2
	cout<<binary_search(A,11,4)<<endl;//-1
	cout<<binary_search(A,11,12)<<endl;//9
	return 0;
}

探索なので「ある」か「ないか」を返す.
探索している値が複数個ある場合は前から返すわけではないので注意.
binary_search(A,11,2)ではA[1],A[2]に2があり2を返している.

ABC037_C

二重ループ中の計算

#include <bits/stdc++.h>
using namespace std;
static const int MAX_N = 100000;
int main()
{
    int n,k,a[MAX_N],tmp;
    int *s;
    long long int res = 0;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n-k+1;i++){
        s = a+i;
        for(int j=0;j<k;j++){
            res += *(s++);// <----
        }
    }
    cout<<res<<endl;
    return 0;
}

←の部分は逆参照子の後にポインタsを一つ進めている.

1. res += *s;
   s++;

2. res += *s++;

3. res += *(s++);

のどれでも通すことができた.

より速い解
予めその数までの和を計算しておき,  S_{i} から S_{i+k}までの和はS_{i+k}-S_{i}という式を利用する.
O(N)で解ける.
最後にi = n-k のときにsum[(n-k)+k] -sum[n-k]なので二番目のfor文でi=nすなわちsum[n]も計算しておくことがポイント.

#include <bits/stdc++.h>
using namespace std;
static const int MAX_N = 100000;
int main()
{
    int n,k,a[MAX_N],sum[MAX_N];
    long long int res = 0;
    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>a[i];
    sum[0]=0;
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i-1];
    for(int i=0;i<n-k+1;i++)res+=sum[i+k]-sum[i];
    cout<<res<<endl;
    return 0;
}

下図はn=5,k=3
1,2,4,8,16の場合
最初の3つの和は青の高さまですなわちsum[3](青と緑の間)-sum[0](透明と黄の間)

f:id:umashika5555:20170310021804p:plain

画像二値化

ithat.me
このサイトを参考にしてPythonで実装した.
PILでGlayScaleにする方法はあるそうだが今回は敢えて使わずに実装した.

#coding:utf-8

from PIL import Image
from PIL import ImageDraw
from random import randint
from os.path import exists
from os import mkdir
from math import fabs
from random import random
from copy import deepcopy
from math import log

def drawPicture(Pic,size,result_file_path,result_file_name,sigma):
    im = Image.new("RGB",size)
    x_size = len(Pic[0])
    y_size = len(Pic[1])
    for x in range(x_size):
        for y in range(y_size):
            im.putpixel((x,y),Pic[x][y])
    if not exists(result_file_path):
        mkdir(result_file_path)
    result_file_name+="sigma_"+str(sigma)
    im.save(result_file_path+result_file_name,"PPM")
    del im


def main():
    #環境変数
    file_name = "Mandrill1.ppm"
    sigma     = int()
    result_file_path = "./binarizatino/result2/"
    result_file_name = ""

    #画像の読み込み
    print("original picture name:",file_name)
    im = Image.open(file_name)

    #RGBに変換
    rgb_im = im.convert('RGB')

    #画像サイズを取得
    size = rgb_im.size#(x:size[0],y:size[1])
    print("original picture size:",size)
    
    #画像のピクセルデータ
    Original = [[0 for _ in range(size[1])] for __ in range(size[0])]
    Original_luminance = [[0 for _ in range(size[1])] for __ in range(size[0])]
    Result   = [[0 for _ in range(size[1])] for __ in range(size[0])]
    Histgram = [0 for _ in range(256)]

    #オリジナル画像のピクセルRGBをリストOriginalに格納
    for x in range(size[0]):
        for y in range(size[1]):
            r,g,b = rgb_im.getpixel((x,y))#ピクセルを取得
            Original[x][y] = (r,g,b)

    #simple binarization
    white = (255,255,255)
    black = (0,0,0)
    sigma1 = float()
    sigma2 = float()
    n1 = int()
    n2 = int()

    for x in range(size[0]):
        for y in range(size[1]):
            luminance = 0.299*Original[x][y][0]+0.587*Original[x][y][1]+0.114*Original[x][y][2]#輝度 := 0.299×R + 0.587×G + 0.114×B (≒ 0.3R+0.6G+0.1B)
            Original_luminance[x][y] = luminance            
            Histgram[int(luminance)]+=1

    INF = 1e8
    res_max = -INF
    res_t   = -INF
    for t in range(256):
        w1 = 0 #クラス1の画素数
        w2 = 0
        s1 = 0
        s2 = 0
        m1 = 0
        m2 = 0
        for i in range(t):#class 1
            w1 += Histgram[i]
            s1 += Histgram[i]*i**2#gaso * (kido - heikin_kido)
        for i in range(t,256):#class 2
            w2 += Histgram[i]
            s2 += Histgram[i]*i**2

        if w1>0:
            m1 = s1/w1

        if w2>0:
            m2 = s2/w2

        tmp = w1*w2*(m1-m2)**2
        if tmp>res_max:
            res_max = tmp
            res_t = t

    print("best t : ",res_t)
    for x in range(size[0]):
        for y in range(size[1]):
            luminance = 0.299*Original[x][y][0]+0.587*Original[x][y][1]+0.114*Original[x][y][2]#輝度 := 0.299×R + 0.587×G + 0.114×B (≒ 0.3R+0.6G+0.1B)
            if luminance < res_t:
                Result[x][y]=black
            else:
                Result[x][y]=white
    drawPicture(Result,size,result_file_path,result_file_name,sigma)
                


if __name__ == "__main__":
    main()

元の画像
f:id:umashika5555:20170309210122p:plain
生成された画像
f:id:umashika5555:20170309210137p:plain

ABC051_C

背の順に並べるという問題

#include <bits/stdc++.h>
using namespace std;
static const int MAX_N = (int)1e5;
int main()
{
    int n,x;
    priority_queue<pair<int,int> > pq;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        pq.push(make_pair(x,i));
    }
    while(!pq.empty()){
        cout<<pq.top().second<<endl;
        pq.pop();
    }
    return 0;
}

pair型の配列をソートすればよいだけ.
priority_queueを用いる必要無かった.

ABC028_C

A < B < C < D < E
の入力に対して考えうる3つの和の中で3番目に大きい物を答えるという問題

#include <bits/stdc++.h>
using namespace std;
int main()
{
    priority_queue<int> pq;
    set<int> s;
    int a[5];
    for(int i=0;i<5;i++){
        cin>>a[i];
    }
    sort(a,a+5);
    do{
        int x = a[0]+a[1]+a[2];
        if(!s.count(x)){
            s.insert(x);
            pq.push(x);
        }
    }while(next_permutation(a,a+5));
    pq.pop();pq.pop();
    cout<<pq.top()<<endl;
    return 0;
    
}

と書いたが,より単純な方法があった.
最も大きいのはC+D+E
次に大きいのはB+D+E
3番目に大きいのはA+D+E or B+C+E

ABC054_C

階乗して並び変えたもののうち島1から始まるPATHを数える.
グラフを隣接リストから隣接行列に変形する.
はじめから島1が最初になるようにvector<> islandを作ったためnext_permutatino()しても時間的に問題ない.

#include <bits/stdc++.h>
using namespace std;
template <class ForwardIterator, class T>
  void iota (ForwardIterator first, ForwardIterator last, T val)
{
  while (first!=last) {
    *first = val;
    ++first;
    ++val;
  }
}
int g[11][11]={0};
int main()
{
    int n,m,x,y,res=0;
    cin>>n>>m;
    vector<int> island(n);
    iota(island.island(),island.end(),0);
    
    for(int i=0;i<m;i++){//隣接行列
        cin>>x>>y;
        g[x-1][y-1] = g[y-1][x-1] = 1;
    }
    do{
        bool flag = true;
        if(island[0])break;//始点が0の時のみ考える
        for(int i=1;i<n;i++){//始点からのつながりを見ていく
            if(!g[island[i-1]][island[i]])flag=false;//つながってない
        }
        if(flag)res++;
    }while(next_permutation(island.begin(),island.end()));
    cout<<res<<endl;
    return 0;
}


iota()を使う場合

template <class ForwardIterator, class T>
  void iota (ForwardIterator first, ForwardIterator last, T val)
{
  while (first!=last) {
    *first = val;
    ++first;
    ++val;
  }
}


vector<int> a(10);
iota(a.begin(),a.end(),0);
for(int i=0;i<10;i++)cout<<a<<" ";
//0 1 2 3 4 5 6 7 8 9