Codeforces Round #342 (Div.2) - 君はまるで砂漠に咲く、一輪の花。

A. Guest From the Past

ざっくりと大意

・最初はnルーブル持っていて最大で何回飲めるか？？
・aルーブル払う場合はプラスチックボトル使い捨てで飲む、bルーブル払うと飲んだ後にガラスボトルを返してcルーブルのキャッシュバックがある。

Python2

n=int(raw_input())
a=int(raw_input())
b=int(raw_input())
c=int(raw_input())
x=n/a
if ((n%a)-c)>0:
    x+=((n%a)-c)/(b-c)

y=(n-c)/(b-c)
if (n-c)/(b-c)>0:
    y+=(((n-c)%(b-c)+c)/a)
print max(x,y)

aを優先と、bを優先と両方を計算して大きい方を出力することにした。

B. War of the Corporations

ざっくりと大意

・aの文字列にbが含まれていたら最小の一部を#で置換してbを含まないようにする。最小の置換は何箇所か？？

Python2

a=raw_input()
b=raw_input()
print a.count(b)

含まないようにする最小の置換はbの末尾を置換することになると思う。置換をシミュレートするわけではないのでアレですが。例えば先頭を置換でa=aaa　b=aaをシミュレートすると、1箇所目置換はaに対してbを含むの検索が1-2文字目でhitして、先頭を#に置換でaが#aaになる。そしてもう一度2-3文字目でhitしてhit部分の先頭を置換して##aになるとbを含まないようになる。だがコレを末尾置換でシミュすると、1-2文字目がhitしてhit部分の末尾を置換するとa#aになって、一度の置換でbを含まないように出来る。
だが解を出力するにはシミュレートは必要なく、文字列aのウチに文字列bが何箇所あるかが解になる。

C. K-special Tables

ざっくりと大意

・n * n のマスで1からn²の数がそれぞれ1度だけ出現で並んでいる。
・各行は左の数 < 右の数になっている。
・k列の数が最大になるような並べ方にする。

Python2

ans=chk=0
n,k=map(int,raw_input().split())
#l=map(int,raw_input().split())
#l=[[0]*n for _ in range(n)]
l=[[] for _ in range(n)]
tmp=0
for i in range(n):
    for j in range(k-1):
        tmp+=1
        l[i].append(tmp)
for i in range(n):
    for j in range(n-k+1):
        tmp+=1
        l[i].append(tmp)
        if j==0:
            ans+=l[i][-1]
print ans
for i in l:
    print ' '.join(map(str,i))

サンプルを見るとなんとなく法則が見えるような。kが1かnならば1行目は1からnまで並んで(処理方法が違うけど最終形は同じ)、それ以外は1からk-1までn並べた後で続きを端まで。サンプル見ると法則がわかります。