A
bを2で割ってaに等しければYes。
int main() {
int a,b;
if(b/2==a) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}
B
Nが小さいので普通に二重ループすればよいです。
int main() {
int n; string s;
cin >> n >> s;
for (int i = 1; i <= n - 1; i++) {
int ans = 0;
//等しくなってしまう場所を見つけるまでループ
for (int j = 0; j <= n - 1 - i; j++) {
if (s[j] == s[j + i]) {
break;
}
ans = j + 1;
}
cout << ans << endl;
}
return 0;
}
C
26進数的な処理をすればよいです。
int main() {
int len = s.length();
ll ans = 0;
for (int i = len - 1; i >= 0; i--) {
ll now = 1;
now *= (ll)(s[i] - 'A' + 1);
rep(j, len - 1 - i) { now *= 26; }
ans += now;
}
cout << ans << endl;
return 0;
}
D
$S_i$が相異なり、$T_i$も相異なるという条件から、「ユーザー名の変更を試みる時点ですでにユーザー名が使わている」状況が確定する条件は以下の通りになります。
- $S_i$から$T_i$とたどり、その$T_i$と等しい$S_j$があれば$S_j$から$T_j$とたどり...という操作を続け、{$S$}に存在しない${T}$の要素にたどりつく前にはじめの$S_i$に戻ってくる。
イメージ的には線形代数の巡回置換みたいなのが形成されていたら条件を満たす、というイメージです。
簡単な証明をすると、たどってきた要素のみでの$S$の集合と$T$の集合はまったく同じになるからです。
一度たどったものはもう調べなくていいので$O(N)$です。コードを今見ると変数1つ減らしてスッキリできそうですね。
const int max_n = 100005;
map<string, string> mp_st; //S_iとT_iの対応関係
map<string, int> mp_si; //S_iとiの対応関係
int isused[max_n]; //S_iが使われたかどうか
vector<string> vec_s;
vector<string> vec_t;
int main() {
//初期化、読み込み
int n; cin >> n;
rep(i, n) isused[i] = 0;
rep(i, n) {
string str_s, str_t;
cin >> str_s >> str_t;
vec_s.push_back(str_s); vec_t.push_back(str_t);
mp_st[str_s] = str_t;
mp_si[str_s] = i;
}
bool flag = true;
rep(i, n) {
if (!isused[i]) {
string str = vec_s[i];
//続くまでSからTへと辿る
while (mp_st.count(str)) {
isused[mp_si[str]] = 1;
str = mp_st[str];
if (str == vec_s[i]) { //巡回置換が存在する
flag = false; break;
}
}
}
}
if (flag) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}
E
一週間のうちで、「最初と最終日の次の日が休日で、あとは働く日が連続している部分列 : {$W$}」について考えてみます。そうすると、{$W$} は以下の2種類に分類できることが分かります。
- 長さが$2n+1$のとき : $0, A_1, A_2... A_{n-1}, A_n, A_n, A_{n-1}, ... , A_2, A_1$
- 長さが$2n$のとき : $0, A_1, A_2... A_{n-1}, A_n, A_{n-1}, ... , A_2, A_1$
つまり、 $A_1～A_i$ までの和を $aa_i$ とすると、長さ $i$ の {$W$} における生産量 $B_i$ は、
- 長さが奇数のとき : $B_i = 2×aa[i/2]$
- 長さが偶数のとき : $B_i = aa[i/2]+aa[i/2 - 1]$
と表すことができます。
さて、総生産量を最大にするための一週間の性質について考えてみます。
まず気になるのは、「休日が連続する状態は存在するのか」ということです。少し考えると分かりますが、$A_i>1$であることから、この状態は存在しません。休日が連続するということは、連続させていないときと比較して必ず$A_i$分損することになるからです。これにより、
- 休日の前後には、必ず働く日が来る
という性質が分かりました。さて、ここまで来たら問題を変化させることができます。具体的には、
- いろいろな長さの{$W$}を組み合わせていって、長さ$n$となるようにするときの、価値の最大値
を求めればよいです。{$W$}の初めに休日がくっついているのがミソかも知れません。
ここまでくればdpの典型問題です。制約的に$O(N^2)$でも充分間に合います。
const int max_n = 5005;
ll a[max_n];
ll aa[max_n]; //i番目までの要素の和
ll b[max_n]; //最初が休日で、i-1日連チャンで働く時の生産量の総和
ll dp[max_n];
int main() {
//1-indexで考える
//初期化
int n; cin >> n;
repa(i, n)(void)scanf("%lld", &a[i]);
repa(i, n) dp[i] = 0;
ll sum = 0;
repa(i, n) {
sum += a[i]; aa[i] = sum;
}
for (int i = 3; i <= n; i++) {
if (i % 2 == 0) {
b[i] = aa[i / 2] + aa[i / 2 - 1];
}
else {
b[i] = 2 * aa[i / 2];
}
}
b[2] = a[1];
//dp[i] := i日目までの価値の最大値
dp[0] = 0;
for (int i = 0; i <= n - 2; i++) {
for (int j = 2; j <= n; j++) {
if (i + j <= n) {
dp[i + j] = max(dp[i + j], dp[i] + b[j]);
}
}
}
cout << dp[n] << endl;
return 0;
}