Chokudai SpeedRun 001

はい。
https://atcoder.jp/contests/chokudai_S001

A - 最大値

PyPy3

n=int(input())
print(max([int(i) for i in input().split()]))

C++14

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    scanf("%d",&n);
    vector <int>a(n);
    for (auto&e:a) scanf("%d",&e);
    printf("%d\n",*max_element(a.begin(),a.end()));
    return 0;
}

最大値を出す。Pythonならリストでmax()、C++ならvectorで*max_element(a.begin(),a.end())で最大値を。あとこれ問題文からはそれとはっきりわかることは無いと思うのですが、数列aが1からNで構成されているようで print(input()) でもACします。

B - 和

PyPy3

n=int(input())
print(sum([int(i) for i in input().split()]))

C++14

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    scanf("%d",&n);
    vector <int>a(n);
    for (auto&e:a) scanf("%d",&e);
    printf("%d\n",accumulate(a.begin(),a.end(),0));
    return 0;
}

総和を取る。Pythonならリストでsum()、C++ならvectorでaccumulate(a.begin(),a.end(),0)を使う。ですがこの問題も数列が1からNになっているようで n=int(input());print(n*(n+1)//2) でACします。

C - カンマ区切り

PyPy3

input()
a=input().split()
print(*a,sep=",",end="\n")
#print(",".join(a))

C++14

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    scanf("%d",&n);
    vector <int>a(n);
    for (auto&e:a) scanf("%d",&e);
    for (int i=0;i<n;i++) printf("%d%c",a[i],i==n-1?'\n':',');
    return 0;
}

特に考える要素はなく指示通りに。 ",".join()は2からある書き方です。 print(*a,sep=",",end="\n") っていう書き方で出来るようになったのは3になってからですね、多分。C++でもprint1つで出来ないかなー、と探していたらこういう書き方見つかりました。その前はforで回して途中まで","付きでと最後だけ"\n"付きみたいにしていました。

D - ソート

PyPy3

input()
print(*sorted([int(i) for i in input().split()]))

C++14

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int n;
    scanf("%d",&n);
    vector<int> a(n);
    for (auto&e:a) scanf("%d",&e);
    sort(a.begin(),a.end());
    for (int i=0;i<n;i++) printf("%d%c",a[i],i<n-1?' ':'\n');
    return 0;
}

sortの使い方で工夫の余地があるようです。C++14で何も考えずにvector使っていますが、 int a[100]; を sort(a,a+n); とかでソートできるようです？

E - 1は何番目？

PyPy3

input()
print([int(i) for i in input().split()].index(1)+1)

C++14

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int n;
    scanf("%d",&n);
    vector<int> a(n);
    for (auto&e:a) scanf("%d",&e);
    for (int i=0;i<n;i++) if (a[i]==1) printf("%d\n",i+1);
    return 0;
}

Python3で書いた方はindexで、C++で書いた方は先頭から探しました。探したのですが find(a.begin(), a.end(), 1) - a.begin(); ということも出来るようです。

F - 見える数

PyPy3

input()
a=[int(i) for i in input().split()]
ans=chk=0
for i in a:
    ans+=i>chk
    chk=max(i,chk)
print(ans)

C++14

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int n,x,ans=1;
    scanf("%d",&n);
    int a[n];
    for (int i=0;i<n;i++) scanf("%d",&a[i]);
    x=a[0];
    for (int i=1;i<n;i++) if (a[i]>x) {
        x=a[i];
        ans++;
    }
    printf("%d\n",ans);
    return 0;
}

問題文が何を言っているのかを質問から確認する。数列を先頭から最大値を更新しつつ確認するだと思います。何か他の考え方とか、工夫して楽する要素はちょっと不明です。

G - あまり

PyPy3

mod=1000000007
input()
print(int("".join(input().split()))%mod)

C++14

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int n;
    scanf("%d",&n);
    char a[10];
    string s;
    for (int i=0;i<n;i++) {
        scanf("%s",a);
        s+=a;
    }
    long long ans=0ll;
    for (int i=0;i<s.size();i++) {
        ans=(ans*10+s[i]-'0')%1000000007;
    }
    printf("%lld\n",ans);
    return 0;
}

結合して余りを取る。Pythonなら桁とか何も気にせずにいけるのですが、C++はよく分かりません。空白区切りでcharで受け取って、stringに付け足していきます。全て結合したstringを先頭(大きい桁)の方から10倍にして1桁ずつずらしながらmodを取ってみていきます。割り算を筆算するときに大きい桁の方から割れるか試すようなことに近い操作だと思います。それを末尾までしていくと解になります。

H - LIS

PyPy3

from bisect import bisect_left
input()
a=[int(i) for i in input().split()]
d=[a[0]]
for i in a[1:]:
    if i>d[-1]: d.append(i)
    else: d[bisect_left(d,i)]=i
print(len(d))

C++14

#include<bits/stdc++.h>
using namespace std;

static const int inf =0x3f3f3f3f;

int lis(int a[], int n) {
    vector<int> l(n, inf);
    for (int i=0;i<n;i++)  *lower_bound(l.begin(),l.end(),a[i])=a[i];
    return find(l.begin(),l.end(),inf)-l.begin();
}

int main(){
    int n;
    scanf("%d",&n);
    vector<int> a(n);
    for (auto &e:a) scanf("%d",&e);
    int ans=lis(a.data(),n);
    printf("%d\n",ans);
    return 0;
}

はい。LISは最長増加部分列のことですね。C++は自分で書いたコードでも一旦はAC出たのですけども、 https://atcoder.jp/contests/chokudai_S001/submissions/6670427 は信用できないので、 https://atcoder.jp/contests/chokudai_S001/submissions/1457738 を見て写経して提出し直しました。
上のコードはLISの長さを調べるのにPythonとC++でちょっと違うことしてます。 Pythonの場合は初期は数列aの先頭の数から始めて大きい数は末尾に追加して、小さい数は置換します。 C++の場合は初期は全てinfで埋めている数列の中の置換を続けてinfの前までがLISの長さとなるようにしてます。多分。。

I - 和がNの区間

PyPy3

n=int(input())
a=[int(i) for i in input().split()]
chk=a[0]
ans=l=r=0
while 1:
    if chk==n: ans+=1
    if chk<=n and r<n-1:
        r+=1
        chk+=a[r]
    elif chk>n:
        chk-=a[l]
        l+=1
    else:
        break
print(ans)

C++14

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int n;
    scanf("%d",&n);
    vector<int> a(n);
    for (auto &e:a) scanf("%d",&e);
    int ans=0,l=0,r=0,chk=a[0];
    for(;;) {
        if (chk==n) ans++;
        if (chk<n && r<n-1) {
            r++;
            chk+=a[r];
        } else if (chk>=n) {
            chk-=a[l];
            l++;
        } else {
            break;
        }
    }
    printf("%d\n",ans);
    return 0;
}

尺取り。末尾は追い越さないように、先頭は配列外に行かないように。末尾は減算してから動かす、先頭は動かしてから加算する。計算がずれないように書く以外には特に工夫する要素は多分ないです。

J - 転倒数

C++14

#include<bits/stdc++.h>
using namespace std;

struct FenwickTree {
    vector<int> v;
    void init(int n) {v.assign(n,int()); }
    void add (int i, int x) { for (;i<(int)v.size();i|=i+1) v[i]+=x; }
    int sum(int i) const {
        int r =int();
        for (--i;i>=0;i=(i&(i+1))-1) r+=v[i];
        return r;
    }
    int sum (int left,int right) const{
        return sum(right)-sum(left);
    }
};

int main(){
    int n;
    scanf("%d",&n);
    vector<int> a(n);
    for (auto&e:a) scanf("%d",&e);
    FenwickTree ft;
    ft.init(n+1);
    long long ans=0ll;
    for (int i=0;i<n;i++) {
        ans+=i-ft.sum(a[i]);
        ft.add(a[i],1);
    }
    printf("%lld\n",ans);
    return 0;
}

転倒数難しいです。 https://atcoder.jp/contests/chokudai_S001/submissions/1457913 から写経しました。FenwickTreeの資料 http://hos.ac/slides/20140319_bit.pdf と 76Pは誤植のようです？ https://twitter.com/btk15049/status/703063581936324608 ｢n以下の最小の2べき｣→｢n以下の最大の2べき｣ 理解に至っていないのでこの記事で書くことはいまはありません。。

K - 辞書順で何番目？

C++14

#include<bits/stdc++.h>
using namespace std;
// https://atcoder.jp/contests/chokudai_S001/submissions/1458715
long long n, a[200000], b[200000], bit[262145], fact[200000], mod=1000000007;

void add (int i,int x) {
    while (i<=n) bit[i]+=x,i+=i&-i;
}
long long sum(int i){
    int ret=0;
    while(i>0) ret+=bit[i],i-=i&-i;
    return ret;
}
int main(){
    scanf("%lld",&n);
    for (int i=1;i<=n;i++) scanf("%lld",&a[i]);

    fact[0]=1; for(long long i=1;i<=n;i++) fact[i]=(fact[i-1]*i)%mod;
    long long ret=0;
    for(int i=1;i<=n;i++) add(i,1);
    for(int i=1;i<=n;i++) {
        add(a[i],-1);
        long long Z=sum(a[i]);
        ret+=(Z*fact[n-i])%mod;
        ret%=mod;
    }
    printf("%lld\n",ret+1);
    return 0;
}

難しいです。 https://atcoder.jp/contests/chokudai_S001/submissions/1458715 から写経しました。分からぬ。サンプルの 3 1 5 4 2 は先頭が3なので先頭に1,2のより後のもの〜を1桁ずつずらして考えたりする方針があるようです。今回の写経したものの内容見て方針とか確認するのはまた後からで。

L - N回スワップ

C++14

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int n;
    scanf("%d",&n);
    vector<int> a(n);
    vector<int> v(n);
    for (int i=0;i<n;i++) {
        scanf("%d",&a[i]);
        a[i]--;
    }
    int m=n;
    for (int i=0;i<n;i++) if (!v[i]) {
        int j=i;
        while (!v[j]) {
            v[j]=true;
            j=a[j];
        }
        m-=1;
    }
    bool ans = m<=n && (n-m)%2==0;
    printf("%s\n",ans?"YES":"NO");
    return 0;
}

難しいです。写経です。k回以内に昇順になるか、余り回数が偶数であるかで判定するはず。あとでもう一度見直し。