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

A. Comparing Strings

implementation,strings

ざっくりと大意

・10⁵を超えない長さの異なる内容であることが保証された文字列が2行与えられる、長さは同じかもしれないしそうでないかもしれない
・1行目の文字列の任意の2箇所の文字を入れ替える操作で2行目の文字列が作れるか？

方針のようなもの

・両方の文字列を比較しながら先頭から舐めて1箇所目の違いがあったらメモ
・2箇所目の違いを続けて探して入れ替えで同じに出来れば以降は違いがないことを末尾まで確認する、入れ替え成功出来ないや3箇所目の違いがあったら中断でNO
・10⁵の長さで2秒制限なら間に合うはず

n=raw_input()
m=raw_input()
ans=chk=0


def dead():
    print 'NO'
    exit()

if len(n)-len(m):
    dead()

for i in range(len(n)):
    if n[i]!=m[i] and chk==0:
        chk+=1
        nw=n[i]
        mw=m[i]
    elif n[i]!=m[i] and chk==1:
        if n[i]==mw and m[i]==nw:
            chk+=1
        else:
            dead()
    elif n[i]!=m[i]:
        dead()
print 'YES' if chk==2 else 'NO'

B. Growing Mushrooms

greedy,sortings

ざっくりと大意

・マッシュルームを育てるコンテストがあって勝者は木製のサラダボウルを得る
・\(t_1\)秒と\(t_2\)秒の時が採点対象？？
・スタート後に秒速\(v_i\)メーターで育てる。\(t_1\)秒後には一時休憩でマッシュルーム育てを中断する
・そして休憩中にk%マッシュルームは小さくなる
・そして第2部が始まり秒速\(u_i\)メーターで育てて\(t_2\)の時に終了する
・a,bの成長速度は入れ替えて使ってもよくて、\(t_1\)秒後までの成長とk%の減少、そしてまた\(t_2\)秒後までの成長をさすのにより大きくなるa,bの使い方
・大きい順にソートして何行目だったかと、幾つになるのかを出力

方針のようなもの

・nが1000以下なら全員のa,b計算して成長結果と行数目をリストに入れてソートしても間に合いそうな気がする

n,t1,t2,k=map(int,raw_input().split())
l,ans=[],[]
for i in range(n):
    w=map(int, raw_input().split())
    l.append(w)

for i in range(n):
    a1=l[i][0]*t1
    ad=a1-(a1*k/100.0)+(l[i][1]*t2)
    b1=(l[i][1]*t1)
    bd=b1-(b1*k/100.0)+(l[i][0]*t2)
    ans.append((max(ad,bd),-(i+1)))
ans.sort()
for i in range(-1,-n-1,-1):
    print -(ans[i][1]), '%.2lf' % ans[i][0]

\(t_1\)までの成長を一度a1とかで保存してa1-(a1*減少割合)としたけど、そこまで速度に影響する要素ではなかったかも？？
あとはリストに保存する要素によっては昇順、降順取り出し方が逆になる場合に-1を書けるのがすごい便利で素晴らしい

C. Plant

ざっくりと大意

・毎年農場が分割されて増えていく？？
・問題文の図のように増えていきn年目の上向き？の△の個数は幾つかを10⁹+7の余りで表す

方針のようなもの

・紙に増え方の図を手書きしたら1年で2倍に段が増えて、1段毎に1つの単調な増加っぽいような？？
・なので1から段目の数までの総和でいけるのでは

#!/usr/bin/env python
# -*- coding: UTF-8 -*-
import sys
m=1000000007
k=int(sys.stdin.readline().rstrip())
if k==0:
    print 1; exit()
#n=2
#for i in xrange(k-1):
#    n=(n*2)%m
n=2<<(k%m)-1
n%=m
if n%2:
    w=((1+n)*(n/2)+(n+1)/2)%m
else:
    w=((1+n)*(n/2))%m
sys.stdout.write(str(w)+'\n')

%mにしながらループ回すとTLE、ビットシフトで済まそうとするとMLE。。メモリと時間を工夫しないと通らないか解き方自体が全く別なのか。。。