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

A. Vitaly and Strings

ざっくりと大意

・sとtは同じ長さの英小文字のみの文字列であり、辞書順では必ずsのほうが早くtの方が遅い。
・辞書順でsより遅くtより早いものがありうるならその文字列を、あり得なければNo such stringを出力する。

方針のようなもの

・sを1つ遅くするか、tを1つ早くするかしてから、辞書順でsより遅くtより早くなっているかを確認する。

s=raw_input()
t=raw_input()[::-1]
ans=''
flag=1
for i in t:
    if flag:
        ans=chr(((ord(i)-98)%26)+97)+ans
        if i!='a':
            flag=0
    else:
        ans=i+ans
print ans if s<ans else 'No such string'

zを遅くする場合はaに戻って左隣りの文字を遅いものにする、同様にaを早くする場合はzに戻って左隣りの文字を早いものにする。繰り上げのようにすることを忘れさえしなければ、他には特に注意するポイントはないと思う。

B. Tanya and Postcard

ざっくりと大意

・文字列sから文字列tを作ろうとして、sから大文字小文字も一致で用意できたら"YAY!"、大文字小文字が違ってしまったら"WHOOPS"とする。
・YAY!の方をより優先して可能な限り最大化して、次点の優先でWHOOPSとなる文字も探して、それぞれの回数を出力する。

方針のようなもの

・先に大文字小文字を数えてしまってから、余った文字で一致しないものを数える。

python

s=raw_input()
t=raw_input()

def cnt(x):
    l=[[0]*26,[0]*26]
    for i in x:
        if i.isupper():
            l[0][ord(i)-65]+=1
        else:
            l[1][ord(i)-97]+=1
    return l

sl=cnt(s)
tl=cnt(t)

ans=[0,0]
for i in range(26):
    if sl[0][i]>=tl[0][i]:
        sl[0][i]-=tl[0][i]
        ans[0]+=tl[0][i]
        tl[0][i]=0
    elif sl[0][i]<tl[0][i]:
        tl[0][i]-=sl[0][i]
        ans[0]+=sl[0][i]
        sl[0][i]=0
    if sl[1][i]>=tl[1][i]:
        sl[1][i]-=tl[1][i]
        ans[0]+=tl[1][i]
        tl[1][i]=0
    elif sl[1][i]<tl[1][i]:
        tl[1][i]-=sl[1][i]
        ans[0]+=sl[1][i]
        sl[1][i]=0
    ans[1]+=min(sl[0][i]+sl[1][i],tl[0][i]+tl[1][i])

print ans[0],ans[1]

s,tそれぞれに大文字小文字を区別してどの文字が何個あるかがわかればいいので個数をリストにする。もしも文字列のままでtの先頭の文字から、sの文字列の中に探しに行くとTLEになります。

C. Anya and Smartphone

ざっくりと大意

・スマホのアプリをn個インストールしていて、1画面にはk個のアプリのアイコンが表示される。ページ内に入りきらないものは新たに次のページにアイコンが配置される。
・アプリ起動し終わると最初のページに戻り、使ったアプリは1つ前の順番のものと配置が入れ替わる(最近使ったアプリとして1つ早く表示されるようになる感じ)。既に先頭の場合は入れ替わりは起きない。
・アプリ起動を1手、1ページスクロールして探すのも1手とする。
・m個の各アプリを順々に起動すると何手になるか？？

方針のようなもの

・シミュレートするしか無いと思う。

python

n,m,k=map(int,raw_input().split())
a=map(int,raw_input().split())
b=map(int,raw_input().split())
l=[0]*(n+1)
for i,j in enumerate(a):
    l[j]=i

ans=chk=0
for i in b:
    ans+=1
    p=l[i]
    ans+=p/k
    if p!=0:
        a[p],a[p-1]=a[p-1],a[p]
        l[i],l[a[p]]=l[a[p]],l[i]
print ans

C++11

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;


int main(){
    int n,m,k;
    long long ans=0;
    scanf("%d %d %d",&n,&m,&k);
    vector<int> a(n);
    vector<int> b(m);
    for(auto&e:a){
        scanf("%d",&e);
    }
    for(auto&e:b){
        scanf("%d",&e);
    }

    int l[n+1];
    for(int i=0;i<n;i++){
        l[a[i]]=i;
    }

    for(int i=0;i<m;i++){
        ans+=1;
        int f=l[b[i]];
        ans+=f/k;
        if(f!=0){
            swap(a[f],a[f-1]);
            swap(l[b[i]],l[a[f]]);
        }
    }
    printf("%lld\n",ans);
    return 0;
}

アプリが何ページ目にあるかをindexで探すのがすごい時間がかるので、indexをメモする配列を別途で用意する。n,m共に最大が10⁵なので10⁵の配列の中から目的のアプリが何番目にあるかを10⁵回探すのは無理です。また、ページスクロール回数はindexをkで割ると求まるはずです。
配列メモなしでもC++なら無理やりTLE回避できないかなと淡い期待で書いてみたけど間に合うはずもなく。。。結局はメモして書きやすいpythonで書いて、わざわざ手を付けたならということでC++でも書いてみたのが今回の流れです。