kmjp's blog

競技プログラミング参加記です

AtCoder ABC #009 : Python練習編

ARC

ABC009に参加。Aを1s差でFAを逃してしまった。
Dに若干苦戦したが何とか正答。
すいません、DだけPythonでTLEしたためC++です。
http://abc009.contest.atcoder.jp/assignments

A - 引越し作業

段ボールがN個ある。１回で２個ずつ運べるとき、全段ボールを運ぶのに何回かかるか。
(N+1)/2で良い。

import sys

N=input()
M={}

print (N+1)/2

B - 心配性な富豪、ファミリーレストランに行く。

N個のメニューの価格が与えられる。
２番目に高い価格を答えよ。

一旦全部setに放り込んで重複をなくした上、ソートして後ろから２つ目を答えればよい。

import sys

N=input()
S=set()
for i in range(0,N):
	S.add(input())

L=list(S)
L.sort()

print L[-2]

C - 辞書式順序ふたたび

文字列Sが与えられる。
このうち最大K文字まで位置を入れ替えて作れる文字のうち、辞書順最小のものを求めよ。

ヒントに従い答えの文字列の先頭から決めていく。
候補として'a'～'z'まで入れてみて、「その値を入れても残りの文字が(K-1)文字の入れ替えで済む」ならその文字を採用していく。

うーん、これ系の問題(一発で最適解を求める必要はなく、条件をはみ出ない範囲で解を絞り込んでいく)は苦手だ…。ヒントなしだと解けてないなこれ。

import sys

N,K=map(int,raw_input().strip().split(" "))
S=raw_input().strip()
C={}

def okok(ind,num):
	C2 = C.copy()
	for i in range(ind,N):
		if C2[S[i]] > 0:
			C2[S[i]] -= 1
		else:
			num -= 1
	return num >= 0

for c in range(ord('a'),ord('z')+1):
	C[chr(c)] = 0

for c in S:
	C[c] += 1

T=''
for i in range(0,N):
	for j in range(ord('a'),ord('z')+1):
		c=chr(j)
		if C[c] > 0:
			C[c] -= 1
			if S[i]!=c:
				K -= 1
			if okok(i+1,K):
				T += c
				break
			if S[i]!=c:
				K += 1
			C[c] += 1

print T

D - 漸化式

数列A,Cのうち先頭K個が与えられる。
K+1要素目以降は、A[N+K] = (C[1]&A[N+K-1]) ^ (C[2]&A[N+K-2]) ^ ... ^ (C[K]&A[N+K-K])で生成される。
A[M]を求めよ。

最初周期性があるかと考えて、周期性が出るまで試したが、最長で2^Kの周期になるため失敗した。
ここではK+1項間漸化式を行列で表現し、その行列のM乗を求めることで対応した。
なお、行列のM乗において、+と*の代わりにxorとandを使う必要がある。
また、単位行列の代わりに2^32-1を用いる必要がある。

以下の解法は、O(K^3*logM)である。PythonだとTLEしてしまったので、C++の回答のみ掲載。

const int MAT=101;
ll G[MAT][MAT],G2[MAT][MAT];
void powmat(ll p,ll n,ll a[MAT][MAT],ll r[MAT][MAT]) {
	ll i,x,y,z;
	ll a2[MAT][MAT];
	FOR(x,n) FOR(y,n) a2[x][y]=a[x][y];
	FOR(x,n) FOR(y,n) r[x][y]=0;
	FOR(i,n) r[i][i]=(1LL<<32)-1;
	while(p) {
		ll h[MAT][MAT];
		if(p%2) {
			FOR(x,n) FOR(y,n) {
				h[x][y]=0;
				FOR(z,n) h[x][y] ^= r[x][z]&a2[z][y];
			}
			FOR(x,n) FOR(y,n) r[x][y]=h[x][y];
		}
		FOR(x,n) FOR(y,n) {
			h[x][y]=0;
			FOR(z,n) h[x][y] ^= a2[x][z]&a2[z][y];
		}
		FOR(x,n) FOR(y,n) a2[x][y]=h[x][y];
		p>>=1;
	}
}

ll A[101],C[101];
ll K,M;
int loop[32];

void solve() {
	int f,i,j,k,l,x,y;
	cin>>K>>M;
	M--;
	FOR(i,K) cin>>A[i];
	FOR(i,K) cin>>C[i];
	
	//if(M<K) return _P("%lld\n",A[M]);
	ll ret=0;
	ZERO(G);
	FOR(j,K-1) G[j+1][j]=(1LL<<32)-1;
	FOR(j,K) G[0][j]=C[j];
	powmat(M,K,G,G2);
	FOR(j,K) ret^=A[j] & G2[K-1][K-1-j];
	
	cout << ret << endl;
}

まとめ

DはPythonでライブラリ無しでTLEせず解けるの…？