Codeforces Round #394 (Div. 2)
http://codeforces.com/contest/761
参加しました、どうやらUnratedになってしまったようです
ABだけ解けました
A. Dasha and Stairs
問題概要
正整数l, r(1 <= l <= r)を両端に含む区間[l, r]には奇数がいくつかあり、偶数がいくつかある。
aを区間に含まれる偶数の数、bを区間に含まれる奇数の数とする。
与えられたa, b(0 <= a, b <= 100)に対して、そのような区間[l, r]が存在するときYES, 存在しない場合はNOを出力せよ。
制約
- 0 <= a, b <= 100
例
a = 2, b = 3とすると、例えば区間を[1,5]とすると偶数が２つ{2,4}、奇数が３つ{1,3,5}含まれるのでYES
a = 3, b = 1とすると、偶数が３つ、奇数が１つとなるが、そのような区間は存在しないのでNO
感想
例えば[1,2,3,4]とすると偶数と奇数の数は一致するし、[1,2,3]とすると奇数の個数は偶数より１つ多い。
[2,3,4,5]とすると偶数と奇数の数は一致する、[2,3,4]とすると偶数の個数は奇数より１つ多い。
一般に[l, r](1 <= l <= r)に含まれる偶数の個数aと奇数の個数bは
- lが奇数、rが偶数 ⇒ a = b
- lが奇数、rが奇数 ⇒ a + 1 = b
- lが偶数、rが偶数 ⇒ a = b + 1
- lが偶数、rが奇数 ⇒ a = b
となっている。ここまでちゃんと言わなくても偶数と奇数の個数の差は１以下じゃないとだめだなーと分かる。
つまりabs(a - b) <= 1ならこれを満たす区間は存在するし、そうでないならこれを満たす区間は存在しない。
故に、与えられたa, bがabs(a - b) <= 1を満たすかどうかを確かめればよい。
ただし、例外があって、a = b = 0のときは偶数の個数も奇数の個数も0となる。
条件を見ると区間が空になるような場合は許されないので、a = b = 0の場合もNoとしなければならない。
実際に書いたコード
諸事情により、問題を解く関数を独立させて書くことにした
def solve(): a, b = map(int, input().split()) if (a + b) > 0 and abs(a - b) <= 1: ans = 'YES' else: ans = 'NO' print(ans) if __name__ == '__main__': solve()
B. Dasha and friends
問題概要
円周上をL等分し、各々に点がある。そのうちの相異なるn個の点上には障害物が置かれている。
そのような円がいくつもあるが、どの円も障害物の位置が相異なっているので互いに区別できる。
今ある円上のある点に置かれた人Aはその円を反時計回りに回って、障害物に当たるたびに最初の位置からその障害物までの距離を記録した。
ある円上のある点に置かれた人BもAと同様に障害物の位置を記録していった。
この２人の障害物の位置の記録が与えられるので、彼らが同じ円上に存在しているか否かを判断せよ。
制約
- 1 <= n <= 50: 円上の障害物の個数
- n <= L <= 100: 円上の点の個数
- ２人の記録は昇順に記録されており、それらの各要素は0以上L-1以下である
例
例えば図のようなケースではAが反時計回りに回って行ったときの障害物の位置の記録は[2,4,6]
Bが反時計回りに回って行ったときの記録は[1,5,7]となる
このケースではAとBは同じ円上に存在しているのでYESとなる
感想
最初例見たとき反時計回りなのに時計回りで数えてしまってなんで[1,5,7]なのかと無駄に悩んでしまった。
素朴にやるならAを基準にして、Bの位置を一つずつズラして障害物の位置を記録させていったときにAの記録と一致するものがあればYESだし、Bを一周させてもAと一致する記録が無ければNOということになる。
Bの位置を時計回りに一つずらしたとき、障害物の記録は各要素をそれぞれ+1することで求められる
ただし、L以上になることはないので常にmodLを取っておく必要がある。
さらに常に昇順にソートされている必要があるので、全要素に+1modLした後その配列をソートし直す必要がある。
これをL回繰り返す。計算量は１回ずらすごとにO(nlog(n))のソートが関わってくるので全体でO(Lnlog(n))となる。
n, L が小さいのでこれで間に合う。
実際に書いたコード
def solve(): n, L = map(int, input().split()) A = [int(i) for i in input().split()] B = [int(i) for i in input().split()] for i in range(L): B_r = sorted([(b + i) % L for b in B]) if A == B_r: print('YES') break else: print('NO') if __name__ == '__main__': solve()
しかし考え直すとソートしなおさなければならないのは末尾が+1modLで0になったときだけで
しかもそれも全体をソートするんじゃなくて末尾だけ先頭に持って来ればいいだけなので
ソートはO(nlog(n))じゃなくてO(n)で出来る……ということに気づいた。
だからもうちょっと効率良くするならこんな感じか、あんまり変わらないけど。
def solve(): n, L = map(int, input().split()) A = [int(i) for i in input().split()] B = [int(i) for i in input().split()] for i in range(L): B = [(b + 1) % L for b in B] if B[-1] == 0: B = [B[-1]] + B[:-1] if A == B: print('YES') return None else: print('NO') if __name__ == '__main__': solve()
やっぱりあんまり変わらなかった、というかむしろ微妙に遅くなった。
Pythonのデフォルトのソートが優秀なんだろうか。
C. Dasha and Password
問題概要
ｎ文字のパスワードを作りたい。パスワードは次の条件を全て満たしている必要がある
- 少なくとも１つ数字が含まれている
- 少なくとも１つアルファベット小文字が含まれている
- 少なくとも記号{*, #, &}のうちどれか１つが含まれている
今n個の長さmの文字列が与えられ、初期状態ではそれらの先頭文字をi番目の文字とした長さnの文字列を作る
例えば
1**2
a3*0
c4**
が与えられたら、初期状態では"1ac"という文字列が生成される
そして１回の操作では、ある行が指し示す文字を１つ右にずらすか、１つ左にずらすことができる
ただし、文字列は循環しているものとする
このとき、生成される文字列がパスワードとして有効な文字列にするために必要な操作の最小回数を求めよ
感想
題意は分かったが、しかし実際に解こうとすると難しい
ぱっと考えると各行について[一番近い数字までの距離、一番近い英文字までの距離、一番近い記号までの距離]（存在しない場合infにする）というデータを格納して各列の最小値を取ればいいんじゃないかみたいなことを考える。
しかし実際にはそれだけではダメで、考慮すべきいくつかの制約がある
- 一つの行から２つ以上の文字を取ることはできない
例えば
3 5
*a**1
**1**
**a**
みたいな例を考えると
[1,1,0]
[2,inf,0]
[inf,2,0]
みたいな感じになって最小値を取ると1+1+0 = 2かなーみたいな感じなんですけど
これは１行目から1とaを取るという不可能なことをやってしまっているのでダメです。
- ある行にしか存在しない文字の種類があるとき、その行からはそれを必ず取ってこなければならない
例えば
3 5
*a1**
**a**
**a**
みたいな例を考えると
[2,1,0]
[inf,2,0]
[inf,2,0]
ってなってて、aで一番小さいとこは１行目なんだけど、それを取っちゃうと数字がどこからも取れなくなっちゃうので
１行目からは1を取るしかないみたいなことです。
とか考えると意外と複雑だなあって思って、全然まとまらなかったですね。
結局何をやったかっていうと
ある列についてソート→一番小さいのを取る
→取った行を取り除いて他の列についてソート→一番小さいのを取る
→取った行を除いて残った列でソート→一番小さいのを取る→それらを全部足す
っていうのを列の取る順序を変えて全ての場合を試して、その結果一番小さくなったものを取るっていうやり方にしました
計算量はO(nm + nlog(n))って感じですかね、多分……
ごちゃごちゃしてますが以下ソースコードです
import sys from itertools import permutations from operator import itemgetter INF = 1000 def solve(): n, m = map(int, input().split()) str_l = [] for i in range(n): moji = [] line = input() for c in line: if c == '*' or c == '#' or c == '&': moji.append('*') elif ord('0') <= ord(c) <= ord('9'): moji.append('1') else: moji.append('a') str_l.append(moji) row_nums = [] for i in range(n): kyori = [get_kyori(str_l[i], '1'), get_kyori(str_l[i], 'a'), get_kyori(str_l[i], '*')] row_nums.append(kyori) ans = INF for i, j, k in permutations((0,1,2)): tmp = 0 kyori_c = row_nums.copy() kyori_c.sort(key=itemgetter(i)) tmp += kyori_c[0][i] kyori_c = kyori_c[1:] kyori_c.sort(key=itemgetter(j)) tmp += kyori_c[0][j] kyori_c = kyori_c[1:] kyori_c.sort(key=itemgetter(k)) tmp += kyori_c[0][k] ans = min(tmp, ans) print(ans) def get_kyori(str1, c): res = INF if c in str1: i1 = str1.index(c) if i1 > len(str1) // 2: i1 = len(str1) - i1 i2 = len(str1) - str1[::-1].index(c) if i2 > len(str1) // 2: i2 = len(str1) - i2 + 1 res = min(i1, i2) return res if __name__ == '__main__': solve()
