ゆらのふなびと

競プロ, Python, C++

Educational Codeforces Round 4 に参加しました

(参加って言ってもvirtualなんですけどね!)

自分のメモ用に。

結果

f:id:pakapa104:20151227005459p:plain

(クリスマスだったせいか背景に雪が!)

時間内で解けたのはA,Bの2問。Aは一番簡単なはずだが格子点の問題だと気付くのに時間がかかり1:05。Bは15分で解けた。Cを考えている途中で時間切れ。

A. Text Splitting

codeforces.com

文字列s(長さn)を、長さp, qの文字列のみに分割できるかという問題。

思考回路

  1. 最初の案は「n%p==0ならpだけ繰り返す、余ればその余りをqで割って繰り返す。それでも余れば不可」というものだったが、これだと11 = 5+3+3のような例に対応できないと気付く。
  2. 次に浮かんだ言葉は「線形結合」。つまりこの問題は「n = kp+lq をみたすような 非負整数 k, l は存在するか?」という問題。
  3. このkとlが変化する……格子点だ! 直線px+qy=n上の格子点を求めればよいのだ。

提出コード

xを変化させながら、(n-px)%y==0となる点があればpx+qy=nと判断した。見つからなければ不可。 (本当はp>qならxを変化させながら、p<qならyを変化させながらの方が早い(範囲が狭まるので))

n, p, q = map(int, raw_input().split())
s = raw_input()

for x in xrange(n/p + 1):
    if (n-p*x)%q == 0:
        y = (n-p*x)/q
        print x+y
        for i in xrange(x):
            print s[p*i:p*(i+1)]
        for j in xrange(y):
            print s[p*x+q*j:p*x+q*(j+1)]
        break
else:
    print -1

B. HDD is outdated Technology

codeforces.com

HDDはデータを分割してディスクの各部分にしまう。このときHDDがデータを順番に読みだすのにかかる時間を求めよという問題。

以下の例ではデータは3個に分割されており、HDDの1番目のセクターにファイルの3番目の破片が格納されている。

HDDはデータを1->2->3の順に読み込むので↓の例では答えは3。

3
3 1 2

思考回路

  1. 本物のHDDのヘッドみたいに行ったり来たりで探していると時間が足りないんだろうなあ……
  2. 先にfをファイルの順番にソートしておくと楽そうだ

提出コード

  1. g = [fの各要素, インデックス(HDDのどこに保存されているか)] というリストをつくる
  2. gをfについて昇順にソートする
  3. gの隣り合う要素について、インデックスの差の絶対値を足していく 和を出力
n = input()
f = map(int, raw_input().split())
g = []
for i in xrange(n):
    g.append([f[i], i])
g.sort(key = lambda x: x[0])
s = 0
for i in xrange(n-1):
    s += abs(g[i][1]-g[i+1][1])
print s

C. Replace To Make Regular Bracket Sequence

codeforces.com

タイトルそのまんまの問題。4種類の括弧からなる文字列をRBSにするための最小置換回数を求める。できない場合は"Impossible"と表示。

一応類題があったので載せておく→http://codeforces.com/contest/26/problem/B

思考回路

  1. まず"Possible"か"Impossible"かだけを判断するコードを書いた。カウント用の変数cntを0で初期化し、open bracketなら+1, close bracketなら-1。cntがマイナスになったらbreak(Impossible)。breakしなかった場合は、最終的にcntが0ならpossible。そうでなければimpossible。
  2. 次にpossibleの置換回数を求めるコードを考える。cntが増加している間は括弧のインデックスを記録していく。cntが減少に移ったら、openとcloseのインデックスが同じかどうか判断する。違えば置換+=1。
  3. ↑のやり方がめんどくさそうだったけどスタック使えば楽そうだと気づく。

提出コード

↑でほとんど書いてしまったのであとはもうコードで。 スタックってこういうところで使うんだ……と思った問題でした。

string = raw_input()
ob = ['<', '{', '[', '(']    #open brackets
cb = ['>', '}', ']', ')']    #close brackets
stack = []
miss = 0
for s in string:
    if s in ob:
        stack.append(ob.index(s))
    elif len(stack) <= 0:
        print "Impossible"
        break
    elif stack.pop() != cb.index(s):
        miss += 1
else:
    if len(stack) != 0:
        print "Impossible"
    else:
        print miss