読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

Codeforces Round #342 (Div. 2) に参加しました

競プロ 参戦記

結果

f:id:pakapa104:20160207212222p:plain

A問題 無限に落ちて 悲しいな (575)

3完が目標だったので残念。というか今回A問題が一番難しかった!(手をつけた問題の中では) Bも無駄にimos法使ってpretest通ったと思いきやsystem testで落とされたのでご愁傷さま。

f:id:pakapa104:20160207212308p:plain

レーティングは1469 -> 1431(-38)。もっとガクッと減ると思ってたので少しホッとしている。前回のAIM Techでspecialist(色で言うと緑?(黄緑ではなく))に戻れたので、なんとか維持していきたいところ。2完が最低ラインだろうな。できれば3完を目指したい。

f:id:pakapa104:20160207213031p:plain

今回正答者数がこんな感じなんですよね……A < B = C。Aは難しくてCは簡単だったということでしょう。

A. Guest From the Past

Problem - A - Codeforces

買えるジュースの最大本数を答える問題。所持金はn円*1で、買い方には次の2通りある。

  1. a円で1本買う
  2. b円で1本買い、直後c円返ってくる

制約が<=10^18と大きいので全部試すのは無理。考察の結果、以下の買い方が最適(なはず)

r = b - a, '//'は整数除算として、

  1. r < a かつ b <= n のときはまずx = (n - b) // r + 1個のbを買い、所持金n -= r*x。他のときはスルー
  2. x += n // a (aを買える分だけ買う) してxが答え

要は、「bを買った方が得なら先に買えるだけ買っておいて、それでもお金が余ればaを買えるだけ買う。bを買うと損になるならひたすらaを買う」ということですね。

n = int(input())
a = int(input())
b = int(input())
c = int(input())

r = b - c

x = 0
if r < a and b <= n:
    x += (n - b) // r + 1
    n -= r * x
x += n // a
print(x)

B. War of the Corporations

Problem - B - Codeforces

文字列s, tが与えられる。tがsに含まれないようにするためにsのうちいくつかの文字を'#'に変更する。このとき、変更しなければならない最小の文字数を答えよ、という問題。

s = 'sirisiri', t = 'sir'のようなケースはs内のtの個数を数えるだけでいいが、s = 'xxxxx', t = 'xx'のようなケースはちょっと考える必要がある。後者にも対応できるようにするには、「sの先頭からtと一致する部分列を探していき、あればその最後尾を'#'にする」のが最適になる。

Pythonだとこんだけです。

s = input()
t = input()
print(s.count(t))

C. K-special Tables

Problem - C - Codeforces

n, kが与えられるので、以下の条件を満たすn*n行列の第k列の総和と行列そのもの(のうちの1つ)を出力せよ、という問題。

  • 1 から n^2 までの整数がどれも1個ずつ含まれる
  • 各行は単調増加
  • 第k列の総和が、上の2条件を満たす者の中で可能な限り最大

n = 4くらいまで手書きで試すと、数の並べ方に規則が見えてくる。以下のように並べればよい。

  • k-1列までは左の列から下向きに1, 2, 3, ...の順で数を埋めていく
  • 第k列からは上の行から右向きに続きの数を埋めていく

総和は下のコードでは等差数列の公式を使っているが、どうせ行列を作るので、行列から計算してもよい。

n, k = map(int, input().split())
a = n * (k - 1) + 1
sm = n * (2 * a + (n - 1) * (n - k + 1)) // 2
t = [ [0] * n for i in range(n) ]
x = 1
for j in range(k-1):
    for i in range(n):
        t[i][j] = x
        x += 1
for i in range(n):
    for j in range(k-1, n):
        t[i][j] = x
        x += 1
print(sm)
for row in t:
    print(" ".join(map(str, row)))

今回はここまで。

次こそは3完頑張るぞ~

*1:面倒なので慣れた単位をつけます