Sdust ACM Weekly #5

今度の周試合のテーマはかなりいいと思います.
HDU 4371
合法的な数字が書けないのは2つのケースを含み、1は書くことができる数字SiがSi-2より大きいがnを超え、2はSiがnを超えていないがSi-2以下である.
これは、勝者の最後のステップが必ず最小の数字を使用していることを示しています(そうでなければ、彼が最小ではなく合法的であれば、相手は最小の数字を使用して合法的な数字を書くことができます).その後、どの数字を使用してもnを超えます.だから相手は必ず負けます.
では、最初にこの状態に達したのが勝者です.では、この状態に達する最後の一歩も、必ず最小の数字を使ったに違いない.
同じ理屈を繰り返す.最後に、誰が最後に最小の数字を使ったのか、パリティによって判断すればいい.
 
CodeForces 354C
最小の数をminnとし,minnがk+1以下であればminnが答えである.すべてのaiは、残りの結果がk以下であるためです.
minnがk+1より大きい場合、minnからk+1までdを列挙することができ、大きいから小さいまで、初めてすべてのai%d<=kを満たすdが答えである.
ai%d>kの場合、dをai%d=kに直接減算することができ、すべてが終了するまで自己減算する必要はない.
時間的複雑度はO(n+k)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define MAXN 300005
#define INF 2139062143
#define inf -2139062144
#define ll long long
using namespace std;
int arr[MAXN];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=0; i<n; ++i)
        scanf("%d",&arr[i]);
    sort(arr,arr+n);
    if(arr[0]<=k+1)
        printf("%d
",arr[0]);
    else
    {

        int d=arr[0];
        while(1)
        {
            bool update=false;
            for(int i=0; i<n; ++i)
            {
                while((arr[i]%d)>k)
                {
                    d--;
                    update=true;
                }
            }
            if(!update) break;
        }
        printf("%d
",d);
    }
    return 0;
}

 
 
CodeForces 353D
理解がまだ十分ではないので、CFにある大神の考えを貼ってみましょう.
1. The answer is the number of seconds needed to move the last girl to the finish place. 2. The number of seconds needed for girl i is at least the number of seconds needed for girl i - 1 + 1. 3. The number of seconds needed for girl i is at least the distance between the initial position and the finish position. 4. Each girl i will move as soon as she can, so she will be right at the back of the girl i - 1 or take at most dist(i) seconds to follow the girl i - 1 . so we can calculate the T(i) = max(T(i-1) + 1, dist(i)) and the answer is just T(lastGirl) .
これに基づいて書かれたコード.

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define MAXN 1000005
#define INF 2139062143
#define inf -2139062144
#define ll long long
using namespace std;
char str[MAXN];
int main()
{
    scanf("%s",str);
    int t=0,pos=0;
    while(str[pos]=='F') pos++;
    for(int i=pos,n=pos;str[i];++i)
    {
        if(str[i]=='F')
        {
             t=max(t+1,i-n) ;
             n++;
        }
    }
    printf("%d
",t);
    return 0;
}