VK Cup 2017 - Qualification 2 - 君はまるで砂漠に咲く、一輪の花。

A. New Password

ざっくりと大意

・パスワードを作る。長さn文字。
・全て小文字。
・文字種はk文字。
・同じ文字は隣り合わないようにする。

Python3

n,k=map(int,input().split())
x=ord("a")
ans=""
for i in range(n):
    ans+=chr(x+i%k)
print(ans)

aから使い始めたり、kで剰余を取ったりしてパスワードを作成する。

B. Maximize Sum of Digits

ざっくりと大意

・x以下の数で桁和が最も大きいもの、桁和が同じならより大きい数を出力する。

Python3

n=input()
l=[int(i) for i in n]
ans=[sum(l),n]
for i in range(len(n)-1):
    t0=0
    t1=""
    for j in range(len(n)-1):
        if i==j:
            t0+=l[j]-1
            t1+=str(l[j]-1)
            t0+=9*(len(n)-j-1)
            t1+="9"*(len(n)-j-1)
            break
        else:
            t0+=l[j]
            t1+=str(l[j])
    if t0>=ans[0]:
        ans[0]=t0
        ans[1]=t1
if ans[0]==sum(l):
    ans[1]=n
print(int(ans[1]))

元々の数か、どこかを1減らした以降が9埋めのような感じに。

C. Online Courses In BSU

ざっくりと大意

・n個ある講義のうちk個の講義を受ける必要がある。
・i番目の講義を受けるには関連のあるいくつかの講義を先に受ける必要がある場合がある。
・受講したものは時系列通りに出力する。

#include<bits/stdc++.h>
using namespace std;
// from https://codeforces.com/contest/770/submission/86484006

#define rep(i,n)  for(int i=0;i<n;++i)
#define sc1(a)  scanf("%d",&a)
#define sc2(a,b)  scanf("%d %d",&a,&b)

const int si=1e6+5;
vector <int> adj[si];
int vi[si];
int par=1;
vector <int> ans;
map<int, int> mm;
void dfs(int x) {
    vi[x]=1;
    mm[x]=1;
    for (long i=0;i<adj[x].size();i++) {
        if(mm[adj[x][i]]==1) { par=-1; return; }
        if (vi[adj[x][i]]==1) continue;
        dfs(adj[x][i]);
    }
    ans.push_back(x);
    mm[x]=0;
}

int main(){
    int n,k,u,v;
    sc2(n,k);
    vector <int> f(k);
    rep(i,k) sc1(f[i]);

    rep(i,n) {
        sc1(u);
        rep(j,u) {
            sc1(v);
            adj[i+1].push_back(v);
        }
    }
    rep(i,k) {
        if (vi[f[i]]==1) continue;
        dfs(f[i]);
        if(par==-1) {
            printf("-1\n");
            return 0;
        }
    }
    printf("%ld\n",ans.size());
    for (long i=0;i<ans.size();i++) printf("%d ",ans[i]);
    puts("");
    return 0;
}

写経しました。
サンプル3のように関連が循環するものは検知して-1を出力する必要があります。前提となるものが受講済かどうかを判定してansに入れたり、済でなければdfsでひたすら探索します、多分。