SRM 714

Easy:Range Encoding

問題概要

単調増加の配列がarrが与えられる. 配列の中で連続した部分(arr[i] + 1 = arr[i + 1]) があるとき,その部分を [a, b]として置き換えることができる. 例えば,{3,4,5,6} であれば [3, 6] と置き換えることができる.

arr配列に対してこのような操作をしたときに最小で何個置き換えるとarr配列をすべて置き換えることができるか.

解法

arr[i] + 1 != arr[i + 1]であれば,カウントをしていけば良い ただし,一番最後のカウントし忘れに注意すること.

#include <iostream>
#include <algorithm>
#include <vector>

class RangeEncoding{
    public:
    int minRanges(std::vector<int> arr){
        std::sort(arr.begin(), arr.end());
        int ans = 0;
        for (int i = 0; i < arr.size() - 1; i++) {
            if (arr[i] + 1 != arr[i + 1]) {
                ans++;
            }
        }
        return ans + 1;
    }
};

Meddium:Removing Parenthesis

正しい括弧の対応が取れた文字列Sが与えられる. Sの一番左の括弧'(‘と右の括弧(場所はどこでも良い)を削除する. ただし,正しい括弧の対応が取れてない文字列となる場合はその右括弧の削除は無効とする. この操作を繰り返していき空文字列となるまで続ける.

この時,空文字列になるような括弧の削除の仕方は何通りあるか.

解法

文字列の長さが最長で20文字なので全探索をしても間に合うが,動的計画法を用いるとより早く計算を行うことができる.

#include <iostream>
#include <algorithm>
#include <string>
#include <map>

class RemovingParenthesis {
public:
    std::map<std::string, int> m;

    int rec(std::string s) {
        if(s[0] ==')'){
            return 0;
        }
        if (m[s] > 0) {
            return m[s];
        }
        std::cout << s << std::endl;
        int ret = 0;
        if(s[1] == ')') {
            ret = rec(s.substr(2));
        }else{
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == ')') {
                ret += rec(s.substr(1, i - 1) + s.substr(i + 1));
            }
        }
        }
        m[s] = ret;
        return ret;
    }

    int countWays(std::string s) {
        m[""] = 1;
        m["()"] = 1;
        m["(())"] = 2;
        m["((()))"] = 6;
        m["(((())))"] = 24;
        m["((((()))))"] = 120;
        m["(((((())))))"] = 720;
        m["((((((()))))))"] = 5040;
        m["(((((((())))))))"] = 40320;
        m["((((((((()))))))))"] = 362880;
        m["(((((((((())))))))))"] = 3628800;
        
        return rec(s);
    }
};

Codeforces Round #321 (Div. 2) A~C

A問題

連続した非減少数列の長さを求めれば良いので、前日の稼ぎ以上を今日稼いでいればカウント+1そうでなければカウント=1とする。

前日と今日の稼ぎしかみないので配列は使わず変数2つを使いコードを書いた。

#include <iostream>
#include <algorithm>

int main() {
    int n, pre_money, now_money, count = 0, max = 0;

    std::cin >> n;
    
    // 初日は前日の稼ぎがないので-1としておく
    pre_money = -1;
    for (int i = 0; i < n; i++) {
        std::cin >> now_money;
        if (pre_money > now_money) {
            max = std::max(max, count);
            count = 0;
        }
        count++;
        pre_money = now_money;
    }

    max = std::max(max, count);

    std::cout << max << std::endl;
    return 0;
}

B問題

お金の差を  d 以上にしないようにしながら友達を誘い友情度を最大化する問題。

この問題は最初にお金を基準にソートをしておく。

あとはしゃくとり法を使ってお金の差が  d 以上にならないようにしながらやっていけば良い

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    int friends, d;

    std::cin >> friends >> d;

    // money, friendship factor
    std::vector<std::pair<int, int> > v(friends);
    for (int i = 0; i < friends; i++) {
        int m, s;
        std::cin >> m >> s;
        v[i] = std::make_pair(m, s);
    }

    // お金を基準にソート
    std::sort(v.begin(), v.end());

    // 尺取法でとく
    long long start = 0, end = 0, max = 0, total_friendship = v[0].second;
    while(true){
        while (end + 1 < friends && v[end + 1].first - v[start].first < d) {
            end++;
            total_friendship += v[end].second;
        }
        max = std::max(max, total_friendship);
        if (end + 1 == friends) break;
        end++;
        total_friendship += v[end].second;
        while (v[end].first - v[start].first >= d) {
            total_friendship -= v[start].second;
            start++;
        }
    }

    std::cout << max << std::endl;

    return 0;
}

C問題

猫が怖いkefaさんがレストランに行く問題。

kefaは連続して  m 回の猫のところに行くことは我慢できるが、連続して  m 回以上猫のいるところに行くとダメ。

連続して  m 回以上猫のいるところに行かないようにして行けるレストランは何件あるか。

この問題は幅優先探索、もしくは深さ優先探索を使えばよい。

私のコードでは幅優先探索で求めた。

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

int main() {
    int n_node, m, count = 0;

    std::cin >> n_node >> m;

    std::vector<int> is_in_cat(n_node);
    std::vector<std::vector<int> > node(n_node);
    for (int i = 0; i < n_node; i++) {
        std::cin >> is_in_cat[i];
    }

    for (int i = 0; i < n_node - 1; i++) {
        int from, to;
        std::cin >> from >> to;
        from--;
        to--;
        node[from].push_back(to);
        node[to].push_back(from);
    }

    // pos, cat;
    std::queue<std::pair<int, int> > pos;
    std::vector<bool> visited(n_node);
    pos.push({ 0, (is_in_cat[0] == 1 ? 1 : 0) });

    while (!pos.empty()) {
        int p = pos.front().first;
        int cat = pos.front().second;
        pos.pop();

        if (visited[p] || cat > m) continue;
        visited[p] = true;

        int push_count = 0;
        for (int i = 0; i < node[p].size(); i++) {
            if (!visited[node[p][i]]) {
                pos.push({ node[p][i], (is_in_cat[node[p][i]] == 1 ? cat + 1 : 0) });
                push_count++;
            }
        }
        // leaf
        if (push_count == 0) {
            count++;
        }
    }

    std::cout << count << std::endl;
    return 0;
}

KUPC2016 A~D問題

kupc2016.contest.atcoder.jp

A問題

問題概要

A時間目からB時間めの始まる直前まで授業は中止される。
N個の履修中の授業のうちいくつの授業をうけることができるか。

解法

各授業の時間に対して  [A - B) の範囲内でないものをカウントしていけば良い。

#include <iostream>

int main() {
	int n, a, b;
 
	std::cin >> n >> a >> b;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int num;
		std::cin >> num;
		if (num < a || b <= num) ans++;
	}
 
	std::cout << ans << std::endl;
	return 0;
}

B問題

N個の問題があるので以下の条件を満たす用にKUPCを開催する。
 1回のKUPCではK問の問題を出題する。
 各問題が出題される回数はたかだか1回である。
 1回のKUPCに出題するK問の問題の頭文字をすべて異なるように出題する。
最大で何回KUPCを開催することができるか

解法

制約に  P_i \ne P_j とは限らないと書いてあるのでsetを使い問題の重複をなくす。
また、頭文字にしか興味が無いので頭文字の出現回数のみをカウントする。
カウント数を降順にソートし、上から順番にK個使用していく。
ただし、使っていくたびにソートを行う必要がある。
そうしないと頭文字の出現回数が
A=4, B=4, C=2 で、1回のKUPCの出題問数が2のとき
最初だけソートした場合だと(A,B),(A,B),(A,B),(A,B) となりKUPCの開催回数は4回となる。
しかし、毎回ソートを行うと(A,B), (A,B), (A,B), (C, A), (C, B) の5回となる。

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
 
int main() {
	int n, k;
 
	std::cin >> n >> k;
 
	std::vector<int> p(26);
	std::set<std::string> se;
        // 問題の重複をなくす
	for (int i = 0; i < n; i++) {
		std::string s;
		std::cin >> s;
		se.insert(s);
	}
        // 頭文字のみを取り出し、カウントする。
	for (auto i : se) {
		p[i[0] - 'A']++;
	}
 
	int ans = 0;
	while(true){
		int count = 0;
		std::sort(p.begin(), p.end());
		std::reverse(p.begin(), p.end());
		for (int j = 0; j < 26; j++) {
			if (p[j] > 0) {
				p[j]--;
				count++;
			}
			if (count == k) {
				ans++;
				break;
			}
		}
		if (count < k) break;
	}
 
	std::cout << ans << std::endl;
 
	return 0;
}

C問題

kupc2016.contest.atcoder.jp

解法

各クッキーに対して美味しさ(x xor y)が127となるようにする。
この時美味しさyのクッキーは次の操作のときに127となるようにしていくだけ。


f:id:Matchald:20161002190419p:plain


#include <iostream>
#include <vector>
#include <algorithm>
 
void solve() {
	int n, d;
 
	std::cin >> n >> d;
 
	long long ans = 0;
	for (int i = 0; i < n - 1; i++) {
		ans += 127;
		d = 127 - d;
	}
 
	std::cout << ans + d << std::endl;
}
 
int main() {
	int test_case;
 
	std::cin >> test_case;
 
	for (int i = 0; i < test_case; i++) {
		solve();
	}
 
	return 0;
}

D問題

kupc2016.contest.atcoder.jp

解法

全探索を行うだけ。
黒板の状態はたかだか4種類である。黒板の長さは最高でも100なので 検索回数の上限以下でおさまる。
しかし、右方向に合っているか確かめたあとに、左方向に対してもクエリを出す必要がある。

#include <iostream>
#include <string>
#include <algorithm>
 
int main() {
    int n;
 
    std::cin >> n;
 
    std::string upper = "", lower = "";
 
    std::string uq = "..##", lq = ".#.#";
    bool back = false;
    while (true) {
	int before_length = upper.length();
	for (int i = 0; i < 4; i++) {
		std::string result;
 
		if (back) {
                        // ある点から左方向があっているか確かめる。
			std::cout << uq[i] << upper << std::endl;
			std::cout << lq[i] << lower << std::endl;
			std::cin >> result;
			if (result == "end") return 0;
			if (result == "T") {
				upper = uq[i] + upper;
				lower = lq[i] + lower;
				break;
			}
		} else {
                        // ある点から右側があっているか確かめる。
			std::cout << upper << uq[i] << std::endl;
			std::cout << lower << lq[i] << std::endl;
			std::cin >> result;

			if (result == "end") return 0;
			if (result == "T") {
				upper += uq[i];
				lower += lq[i];
				break;
			}
		}
	}
        // 右方向に確かめている間にすべてのパターンでミスした場合は
        // もう右方向に黒板はない。しかし、左方向にはあるかもしれないのでそちらを確かめる。
	if (before_length == upper.length()) {
		back = true;
	}
    }
 
	return 0;
}

CodeIQ 「トライアングル・メイズ」

問題

問題はこちらhttps://codeiq.jp/challenge/2833

コード

入力が  1 \le n \le 10^8 程度だったので埋め込みをしました。
 10^7 回程度のループなら1秒もかからず実行できるので10個埋め込みをすれば十分です。
あとは、入力 n にたいして f(n) = f(n -1) \times f(n - 1) + f(n - 1) を計算します。

#include<iostream>

int main() {
	long long umekomi[] = { 1, 962661, 542563, 812109, 276578, 851210, 574610, 185493, 203688, 638904, 342482};
	long long n;

	std::cin >> n;

	int pos = n / 10000000 ;
	n -= pos * 10000000;
	long long ans = umekomi[pos];
	if (pos == 0) n--; // スタート位置の調整
	for (int i = 0; i < n; i++) {
		ans = ans * ans + ans;
		ans %= 1000003;
	}

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

Codeforces 371 Div2 C

問題

codeforces.com



 n 個のクエリが与えられます。それぞれのクエリの内容は以下のとおり

 + a_i :  a_i をリストに加える
 - a_i :  a_i をリストから1つ削除する。 この a_i はリストの中に1つ以上存在する。
 ? s : リストの中に  s を満たす a_i の個数を求める。ただし、 s は0と1のみで構成され、0は偶数に、1は奇数に対応する。もし、sa_i の桁数が違うなら、一番左に0を追加することで調整しなければならない。

 s = 010, a_0 = 296
この時は  a_0 は 偶数、奇数、偶数なので  s の 010 と対応しているため個数に加える。

解法

クエリ ? は各桁が、偶数か奇数かしか気にしていないため、クエリ + a_i- a_i の時に  a_i の各桁の数字が奇数なら1に、偶数なら0に変換すると良い。
また、桁数が18桁に満たない場合は左に0を追加することで比較を簡単化することができる。
あとはマップに突っ込めば良い

f:id:Matchald:20160914133317p:plain

コード

#include<iostream>
#include<map>
#include<string>
#include<algorithm>

int main() {
	int query;

	std::cin >> query;

	std::map<std::string, int> m; // 数字 -> 回数
	for (int i = 0; i < query; i++) {
		char op;
		std::string num;

		std::cin >> op >> num;

		for (int j = 0; j < num.length(); j++) {
			if ((num[j] - '0') % 2 == 0) {
				num[j] = '0';
			} else {
				num[j] = '1';
			}
		}

		while (num.length() < 18) {
			num.insert(num.begin(), '0');
		}

		if (op == '+') {
			m[num]++;
		} else if (op == '-') {
			m[num]--;
		} else {
			std::cout << m[num] << std::endl;
		}
	}

	return 0;
}

python3でコードゴルフをするためのテクニック

':'の後ろに式を書くことができる。

for や if のあとにつく : の後ろに続けて式を書くことで余分なスペースを省くことができる。続けて式を書きたい時には ; で区切る。
しかし、2重for や for:if: のように : の後ろに更に : がつくような式は書くことができない。

# long
for i in range(10):
   print(i)
   print(i*i)

# short
for i in range(10):print(i);print(i*i)

# このような書き方はできない
for i in range(10):for j in range(10):print(i*j)

# 3項演算子ならOK
for i in range(10):a+=0 if i%3==0 else 1

n回処理をするときにはrangeを使わない

ただ単にn回処理を行いたい場合には [0]*n を使うと3文字短くすることができる。

# long
for i in range(10):print('Hello world!')

# short
for i in [0]*10:print('Hello world!')

複数回同じ関数を使うなら関数を代入する

3回以上input()を使うなら、inputを変数に代入することによってコードを短くすることができる。
input の他にも print や range などでも有効。

# long
a=input();b=input();c=input()

# short
i=input;a=i();b=i();c=i()

lambdaが使えるなら使う

通常の場合だと def と return が重いので lambda を使うと良い

from math import *

# long
def a(x,y):return x*y//gcd(x,y)

# short
a=lambda x,y:x*y//gcd(x,y)

rangeでループするときはiの初期化はいらない

forループ後もiは生きているので i = 0で初期化はいらない

for i in range(10):
  pass

print(i) # 9が表示される

リストを使って場合分けを行う

# グー = 0, チョキ = 1, パー = 2
print(["Drew","Lost","Won"][(a-b)%3])

# printされる値は以下のようになる
# 001 002 003
# 004 005 006
# 007 008 009
for i in range(1,10):print(("%03d"+"\n "[i%3!=0])%i,end="")

reversedではなく[::-1]を使う

リストや文字列を反転させたい時には reversed (reverse) ではなく [::-1]を使うと良い。

# long
print("".join(reversed(sorted(input()))))

# short
print("".join(sorted(input())[::-1]))

細々としたコード短縮法

数字と数字以外の文字の間のスペースや、記号以外の文字と記号の間のスペースは省略できる。

# long
for i in [0]*10:print('Hello world!')

# short
for i in[0]*10:print('Hello world!')

# long
a=0 if i<3 else i%3

# short
a=0if i<3 else i%3

おまけ

and, orを駆使する

and や or の挙動を知っておくと便利かもしれない

# 前が False の場合、前の値を返す
print(0 and 2) # 0
# 前が True の場合、後ろの値を返す
print(1 and 2) # 2

# True と判定した方を返す
# 両方とも False の場合は後ろの値を返す
print(0 or 2) # 2
print(1 or 2) # 1
print(None or []) # []

SRM696 div2 med

自分が参加した部屋(room19)がこの惨劇であったのでとりあえずどういう解法で解いたかを書いていきます。
ちなみに自分は見事に落ちました。

f:id:Matchald:20160812213810p:plain

問題概要

配列Aを配列Bと同じにするために、Aの値を配列Fの値で置き換える。しかし、置き換えられるのは1つの要素につき1回のみです。
Fの値は全て使わなければなりません。
最善の手を尽くした時にAとBの違いはどれだけあるかを数える。

例)
A = {2,2,2}
B = {2,2,2}
C = {1,2,3}

この時は以下のように値を変えたときがAとBとの差が一番小さくなります。
f:id:Matchald:20160812214848p:plain

解法

とりあえずA[i] != B[i]でA[i]をF[j]で置き換えた時にA[i] == B[i] となるようなF[j]があればその値にしてあげるとAとBとの違いが少なくなるのでこれを行います。
ただし、Fの値は一回しか使えないこととに注意する必要があります。

これが終わったらA[i] == B[i] == F[j] を A[i] = F[j] とします。この操作ではA[i]の値は変わりませんが、使わなければならないFの値を少なくするのが目標です。

ここまででFで使っていない値というのはAのどの要素に対してもF[i]の値で置き換えるとA[i] != B[i] となってしまう値の集合です。

あとは残っているFの要素数と,A[i] != B[i] の数の大きい方を答えとして出力するだけです。

C++のコード

#include<iostream>
#include<vector>
#include<algorithm>

class Arrfix {
public:
	int mindiff(std::vector<int> A, std::vector<int> B, std::vector<int> F) {
		std::vector<int> diff_pos, same_pos;

		for (int i = 0; i < A.size(); i++) {
			if (A[i] != B[i])
				diff_pos.push_back(i);
			else
				same_pos.push_back(i);
		}

		std::sort(F.begin(), F.end());

		// ラベルを貼り直してBと同じにできるならラベルを貼る
		for (int i = 0; i < diff_pos.size(); i++) {
			if (F.empty()) break;
			auto f = std::find(F.begin(), F.end(), B[diff_pos[i]]);
			if (f != F.end()) {
				F.erase(f); // 使ったラベルは削除
				diff_pos[i] = -1;
			}
		}

		// 余ったラベルで合ってる奴に貼っつけても大丈夫なら貼る
		for (int i = 0; i < same_pos.size(); i++) {
			if (F.empty()) break;
			auto f = std::find(F.begin(), F.end(), B[same_pos[i]]);
			if (f != F.end()) {
				F.erase(f); // このラベルは使ったので削除
			}
		}

		// A[i] = B[i] にしたところはdiff_posから削除
		std::sort(diff_pos.begin(), diff_pos.end());
		while (true) {
			auto a = std::find(diff_pos.begin(), diff_pos.end(), -1);
			if (a != diff_pos.end()) {
				diff_pos.erase(a);
			} else {
				break;
			}
		}

		return std::max(diff_pos.size(), F.size());
	}
};