2017-03-15

ABC033_C

C++ ABC

1+2*3+0+5*6+7
のように+か*で繋がった式が与えられる.
式の結果が0となるように,式のある値を0に入れ替える.
この時最小の入れ替え回数を求めるという問題.

足し算はそれぞれの値で0と入れ替えなければならない.
掛け算はひとつ0があればよい.
掛け算のほうが足し算より演算の順が先である.

これらを考えると'+'で分ければよいことがわかる.
上の式の場合,このように分けられる.
1
2*3
0
5*6
7
それぞれが0にしなければか？すでに0になっているのか？をカウントしていく.

#include <bits/stdc++.h>
using namespace std;

vector<string> split(const string &s, char delim)
{
    vector<string> elems;
    stringstream ss(s);
    string item;
    while(getline(ss,item,delim)){
        if(!item.empty()){
            elems.push_back(item);
        }
    }
    return elems;
}

bool contain_zero(string s){
    for(int i=0;i<(int)s.size();i+=2){
        if(s[i]=='0')return true;
    }
    return false;
}

int main()
{
    string s;
    vector<string> items;
    cin>>s;
    items = split(s,'+');
    int count = 0;
    for(int i=0;i<(int)items.size();i++){
        if(!contain_zero(items[i]))count++;
    }
    cout<<count<<endl;
    return 0;

}

文字列からある文字でスプリットしたいとき

vector<string> split(const string &s, char delim)
{
    vector<string> elems;
    stringstream ss(s);
    string item;
    while(getline(ss,item,delim)){
        if(!item.empty()){
            elems.push_back(item);
        }
    }
    return elems;
}

2017-03-15

ABC036_C

C++ ABC

連想配列mapを使う問題
map M;
M[key] = value;
とし, keyを与えられた数値にvalueをその数値が何番目に大きいのかを記録

TLE解法

#include <bits/stdc++.h>
using namespace std;
static const int MAX_N = 100000;
int main()
{
    int n,x;
    set<int>  s;
    int a[MAX_N],b[MAX_N];
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        s.insert(a[i]); 
    }
    //setは標準でソートされている
    int value = 0;
    for(set<int>::iterator itr = s.begin();itr!=s.end();itr++){
        int key = *itr;
        for(int i=0;i<n;i++){
            if(a[i]==key){
                b[i]=value;
            }
        }
        value++;
    }
    for(int i=0;i<n;i++){
        cout<<b[i]<<endl;
    }
    return 0;
}

AC解法

#include <bits/stdc++.h>
using namespace std;
static const int MAX_N = 100000;
int main()
{
    int a[MAX_N];
    set<int> S;
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        S.insert(a[i]);
    }
    map<int,int>M;
    int value = 0;
    for(set<int>::iterator itr=S.begin();itr!=S.end();itr++){
        M[*itr] = value++;
    }
    for(int i=0;i<n;i++){
        cout<<M[a[i]]<<endl;
    }
    return 0;
}

setについて
set の内部構造は配列ではなく、二分木になっているので、演算子（operator(size_t)）で、指定番目の要素を取り出すことは出来ない。
したがって、イテレータを使って各要素にアクセスする必要がある。
C++ 順序付集合 std::set 入門

for(set<int>::iterator itr=S.begin();itr!=S.end();itr++){
    cout<<*itr<<endl;
}

で値を参照する必要がある.

2017-03-14

ABC038_C

C++ ABC

二重ループの効率化の問題

TLEだったやつ

#include <bits/stdc++.h>
using namespace std;
static const int MAX_N = 100000;
int main()
{
    int n,a[MAX_N+1],l,r,ans = 0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<n;i++){
        l = i;
        for(int j=l+1;j<=n;j++){
            if(a[l++]<a[j]){
                ans++;
            }else{
                break;
            }
        }
    }
    cout<<ans+n<<endl;
    return 0;
}

しゃくとり法を用いた解法

#include <bits/stdc++.h>
using namespace std;
static const int MAX_N = 1000100;
int main()
{
    int n,l,r,a[MAX_N];
    long long int ans = 0;
    cin >> n;
    for(int i=0;i<n;i++)cin>>a[i];
    l = 0;
    r = 1;
    ans = 0;
    if(n>=2){
        while(l<n-1){
            if(r==l)r++;
            while(a[r-1]<a[r])r++;//(l,r)を満たす最大のrを見つける
            ans += (r-l-1);
            l++;
        }
    }
    ans += n;
    cout<<ans<<endl;
    return 0;
}

数列の和の計算を使った解法(本質的には上と同じ)
例えば1,2,3という数列に含まれる部分単調増加数列の個数は{1,12,123,2,23,3}の6つ
これは要素数1の数列が{1,2,3}の3個, 要素数2の数列が{12,23}の2個, 要素数3の数列が{123}の1個となるので1+2+3=6となる.
よって和の公式を使ってlength = 数列の長さ, length * (length+1)/2で部分単調増加数列の個数が出る.
あとはleftの位置を更新していけばよい.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
static const int MAX_N = 1000100;

int main()
{
    int n,l,r,a[MAX_N];
    ll ans=0,length;
    cin >> n;
    for(int i=0;i<n;i++)cin>>a[i];
    ans = 0;
    length = 1;
    for(int i=0;i<n;i++){
        if(a[i]<a[i+1]){
            length++;
        }
        else{//今tmpは単調増加列の長さを示している.
            ans += length*(length+1)/2;
            length = 1;
        }
    }

    cout<<ans<<endl;
    return 0;
}

2017-03-14

ABC039_C

C++ ABC

文字列一致の問題
鍵盤の右20個の文字列が与えられるので今いる場所を当てるというやつ.

#include <bits/stdc++.h>
using namespace std;

string func(string str,int n){
    /*
        文字列strを整数n倍し文字列を返す関数
    */
    string tmp = str;
    for(int i=1;i<n;i++){
        str += tmp;
    }
    return str;
}

int main()
{
    string s;
    cin>>s;
    string keyboard = "WBWBWWBWBWBW";
    string tmp = func(keyboard,3);
    int res = -1;
    for(int i=0;i<12;i++){
        if(s == tmp.substr(i,20)){
            res = i;
            break;
        }
    }
    switch(res){
        case -1:cout<<"fuck";break;
        case 0:cout<<"Do";break;
        case 2:cout<<"Re";break;
        case 4:cout<<"Mi";break;
        case 5:cout<<"Fa";break;
        case 7:cout<<"So";break;
        case 9:cout<<"La";break;
        case 11:cout<<"Si";break;
    }
    cout<<endl;
    return 0;

}

Pythonの辞書的な使い方を学んだ.

map<string, string> res = {
		make_pair("WBWBWWBWBWBW", "Do"),//make_pair(その位置から右20個の文字列, その位置)
		make_pair("WBWWBWBWBWWB", "Re"),
		make_pair("WWBWBWBWWBWB", "Mi"),
		make_pair("WBWBWBWWBWBW", "Fa"),
		make_pair("WBWBWWBWBWWB", "So"),
		make_pair("WBWWBWBWWBWB", "La"),
		make_pair("WWBWBWWBWBWB", "Si"),
	};
cout << res[S.substr(0, 12)] << endl;//与えられた文字列がkeyになるmap<string,string>型resの要素

2017-03-14

ABC040_C

C++ ABC

典型的DP問題

#include <bits/stdc++.h>
using namespace std;
static const int MAX_N = 100000;
int main()
{
    int dp[MAX_N+1] = {0};//i本目の柱までにかかる最小コスト
    int n,x,height[MAX_N+1];
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>height[i];
    }
    dp[1]=0;
    dp[2]=abs(height[2]-height[1]);
    for(int i=3;i<=n;i++){
        int a = dp[i-2] + abs(height[i-2]-height[i]);//柱i-2から柱iへのルート
        int b = dp[i-1] + abs(height[i-1]-height[i]);//柱i-1から柱iへのルート
        dp[i] = min(a,b);
    }
    cout<<dp[n]<<endl;
    return 0;
}

2017-03-14

Iterator並列処理

Python

alphabet_list = ['a','c','e','b']
ascii_code_list = [0x61,0x63,0x65,0x62]

max_ascii_code = 0x00
for alphabet,ascii_code in zip(alphabet_list,ascii_code_list):
	if ascii_code>max_ascii_code:
		max_alphabet = alphabet
		max_ascii_code= ascii_code

print(max_alphabet,max_ascii_code)

list_A = []#len(list_A) == len(list_B)
list_B = []
for a,b in zip(list_A,list_B):
      pass

zip関数の問題点

python2ではジェネレータではないのでitertools.izipを使う.
リストの長さが異なると短い方のリストの処理までしか行わない.

2017-03-14

enumerate

Python

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から始められる.

2017-03-12

ABC035_C

C++ ABC

一列に並んだオセロ(最初は全て黒)を指定された左と右の位置で反転を繰り返すという問題.
普通にやっていたら配列サイズ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;
}

2017-03-11

分割統治法

C++

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

#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;
}

2017-03-11

lower_bound()

C++

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;
}

2017-03-11

二分探索

#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を返している.

2017-03-10

ABC037_C

C++ ABC

二重ループ中の計算

#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

2017-03-09

画像二値化

画像処理 Python

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 #クラス１の画素数
        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
生成された画像

2017-03-09

ABC051_C

C++ ABC

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

#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を用いる必要無かった.

2017-03-09

ABC028_C

C++ ABC

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