#結果
Bの1完で, レート変化は722→704(-18)
#A問題 ( Two Choices )
###概要
N 人が M 個の二択問題に回答している.
どのような解答であっても得点が一致することの無い組み合わせは何組できるか求める.
###方針
「任意の2人組の得点が異なる組み合わせは何通りあるか」という問題だと誤読し, 2^m 通りの全ての解答をbit全探索する問題だと思い, 1時間くらい無駄にしてしまった. そもそも, 得点は m 通りしかないので, N > m のときは, 0通りになってしまう.
その後, ちゃんと題意を把握して, 回答が異なる問題の個数が奇数になる組み合わせを求める問題だと分かったが, i, j の全ての組み合わせを試すと, TLEになってしまった. (計算量が 0 ( N^2 * M)になる. )
「回答が異なる問題の個数が奇数である」をもっとよく考えると, A さんと B さんの回答の中の1の総数の差が奇数であることと同値であることが分かる. したがって, 回答の中の1の総数が偶数になっている人の数と奇数になっている人の数の積が求める答えになる.
「A さんと B さんの回答が異なる問題の個数が奇数である」ことと, 「A さんの回答中の1の総数と B さんの回答中の1の総数の差が奇数である」ことが同値であることは次のように示せる.
まず, A さんと B さんは 回答の中にそれぞれ1を X個, Y個持っているとする.
そして, A さんと B さんの回答の中には, (0, 0) (2人とも0と回答している) という回答が a 個, (0, 1) という回答が b 個 ... という風に仮定すると,
| a | b | c | d | |
|---|---|---|---|---|
| A | 0 | 0 | 1 | 1 |
| B | 0 | 1 | 0 | 1 |
A さんの回答の中に1は X 個あるはずなので,
X = c + d ・・・① が成立する. 同様に B さんに関しても,
Y = b + d ・・・②が成立する.
ここで, 求めたいものを思い出すと, b + c の偶奇である.
したがって, ① + ② をすると,
X + Y = b + c + 2*d ・・・③ となる.
よって, A さんの回答の中に含まれる1の総数と, B さんの回答の中に含まれる1の総数を合計して, 奇数になれば, b + c も奇数になり, 題意を満たす組み合わせとなる.
また, 「A さんの回答の中に含まれる1の総数と, B さんの回答の中に含まれる1の総数を合計すると奇数になる」ということは,前者と後者の偶奇が異なるということなので, 回答の中に含まれる1の個数が偶数個の人の数と奇数の人の数の積が求める答えとなる.
C++ での実装例は以下のようになる.
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (long long i = 0; i < (n); i++)
using ll = long long;
int main() {
ll N, M; cin >> N >> M;
vector<string> S(N);
rep(i, N) cin >> S[i];
ll cnt = 0;
// 回答の中の1の個数が偶数の人数をカウントする
for (ll i = 0; i < N; i++) {
ll one = 0;
for (auto c : S[i]) {
if (c == '1') one++;
}
if (one % 2 == 0) cnt++;
}
// (1の個数が偶数の人数) × (1の個数が奇数の人数) が答えになる
cout << cnt * (N - cnt) << endl;
}
#B問題 ( Plus Matrix )
###概要
N 行 N 列の行列 C の任意の成分 C [ i ] [ j ] が, C [ i ] [ j ] = A [ i ] + B [ j ] と表すことができる A, B は存在するか判定し, 存在する場合は出力する.
方針
A の要素を1つ確定させると, B は全て決まり, A も全て決まる. そして, 決まった A, B が条件を満たすか判定する. 最初に確定させる要素は, C の中で最小の値が含まれる行にする. そして, その値はその最小値にする. そうすることで, A, B が負の値になることは無くなる.
以下のようなイメージになる.
C++ での実装例は以下のようになる.
int main() {
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (long long i = 0; i < (n); i++)
using ll = long long;
using P = pair<ll, ll>;
const ll INF = 1001001001;
int main() {
ll N; cin >> N;
vector<vector<ll>> C(N, vector<ll>(N));
vector<ll> A(N), B(N);
// (最小値, 最小値が含まれる行数) を表す Pair
P min_val(INF, 0);
rep(i, N) rep(j, N) {
ll val;
cin >> val;
if (min_val.first > val) {
min_val = make_pair(val, i);
}
C[i][j] = val;
}
bool ok = true;
// A の要素を1つ確定させる
A[min_val.second] = min_val.first;
// 確定した行を使って, Bを全て確定させる
for (ll i = 0; i < N; i++) {
B[i] = C[min_val.second][i] - A[min_val.second];
}
// 0列目を使って, Aを全て確定させる
for (ll i = 0; i < N; i++) {
A[i] = C[i][0] - B[0];
}
// 条件を確認
rep(i, N) rep(j, N) {
if (C[i][j] != A[i] + B[j]) ok = false;
}
if (ok) {
cout << "Yes" << endl;
rep(i, N) cout << A[i] << endl;
rep(i, N) cout << B[i] << endl;
}
else cout << "No" << endl;
return 0;
}
#C問題 ( ℕ Coloring )
###概要
要素が N 個の配列のうち, i が j の約数であれば, i 番目の要素と j 番目の要素の数字は異なる, という配列を考えるとき, 配列の要素の最大値が最も小さくなる配列を求める.
方針
とりあえず1は全ての数の約数になるので, A [ 1 ] を1とすると, A [ i ] ( i >= 2 ) は, 2以上の数字になる. A [ 2 ] を考えてみると, 2以上の数なので, とりあえず2として次に行く. A [ 3 ] を考えると, 1でなければ良いので, 2とする. A [ 4 ] を考えると, 4 の約数は, 1, 2, 4 なので, A [ 1 ] = 1 と A [ 2 ] = 2 以外の数字であればいいので3とする.
このように考えて行くと, A [ i ] は i の約数にすればいいのでは？ と思った.
しかし, A [ 6 ] を考えてみると, 6 の約数は, 1, 2, 3, 6 だが, A [ 2 ] と A [ 3 ] は同じ数でも問題ないので, 最小になるようにすると, A [ 1 ] = 1, A [ 2 ] = 2, A [ 3 ] = 2, A [ 6 ] = 3 とできるので, 約数の個数ではうまくいかないことに気づく.
A [ x ] を考えるときに, x の約数である i, j が A [ i ] = A [ j ] はダブルカウントしないようにsetで管理をすればうまく行きそうであることに気づいた. 方針としては, x の約数を列挙して, その約数を y とすると, setに A [ y ] をどんどん入れていくという感じである. こうすることで, A [ x ] = setのサイズ という風にできる.
C++ での実装例は以下のようになる.
int main() {
#include <bits/stdc++.h>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ll n; cin >> n;
vector<ll> a(n+1);
for (ll i = 1; i <= n; i++) {
set<ll> ans;
// i の約数を列挙していく
for (ll j = 1; j * j <= i; j++) {
if (i % j == 0) {
ans.insert(a[j]);
ans.insert(a[i/j]);
}
}
a[i] = ans.size();
}
for (ll i = 1; i <= n; i++) {
cout << a[i] << endl;
}
return 0;
}