ARC 147 D - Sets Scores (700, 黄)
お気持ち
- 小さいケースを全探索してOEISに投げれば解を予想できます。
- 対称性をいい感じに使うと、数え上げの空間が簡単になります。
- (良い行列, 良い選び方) を数える問題にして選び方を固定するのはよくあるテクニックですが、良い選び方になるように狙って行列を作らなくても、適当な行列を作ってXORで帳尻を合わせるなり、適当な行列を作った場合に良い選び方になる確率を考えるなりすればいいというのが、面白いところですね。
考察
ソースコード
#include <iostream> #include <atcoder/modint> using namespace std; using namespace atcoder; using mint = modint998244353; int main() { int n, m; cin >> n >> m; mint ans = mint(m).pow(n - 1) * mint(n).pow(m); cout << ans.val() << endl; return 0; }
ARC 147 C. Min Diff Sum (600, 青)
考察
- 異なる二点間の距離の総和を最小化したいです。
- 答えが0になる条件が誘導になっています。
- 右端最小～左端最大に集められると気づくのは難しい気がします。
- 詳細は以下の通りです。公式解説と同じですね。
ソースコード
#include <iostream> #include <algorithm> #include <functional> #define rep(i, n) for(i = 0; i < n; i++) #define int long long using namespace std; int n; int l[300000], r[300000]; signed main() { int i; cin >> n; rep(i, n) cin >> l[i] >> r[i]; sort(l, l + n, greater<int>()); sort(r, r + n); int ans = 0; rep(i, n) { if (l[i] <= r[i]) break; ans += (n - 1 - 2 * i) * (l[i] - r[i]); } cout << ans << endl; return 0; }
ARC147 B - Swap to Sort (500, 緑)
お気持ち
- 本番に考えたこと
- 奇数に青丸、偶数に赤丸を書いて、青と赤が交互に並ぶように考えた。
- 操作Aで青赤青赤...を作ってから、操作Bをする方法が最適と思っていてWA。
- 反例:
P = (2, 4, 1, 3)最適解は1だが、上記では3回かかってしまう。
- 反例:
- 場所の偶奇が合っているかで青丸、赤丸の中に〇×を書いて頑張って考察した。
- 勘で解くならこうしたい
P_i <-- P_i mod 2として(0, 1, 0, 1, ...)を作ってもよさそう。偶数番Flipをして(0, 0, ...)を作る問題にできそう。- 操作Aは、
(0, 0) <-> (1, 1)、(0, 1) <-> (0, 1)、(1, 0) <-> (1, 0)、2個飛ばしのswapは(0, 0) <-> (0, 0), (1, 1) <-> (1, 1), (0, 1) <-> (1, 0)になるから、(1, 1) -> (0, 0)を使いたい。 - 操作Bで
1をできるだけ前に持ってきてから、1, 1を0, 0にしていって、最後に操作BでPをバブルソートしたら解けそう。 - 以下の考察により正しいことが分かる。
考察
- 初期地点が
のものを目的地
に移動したい。
- （操作Bでは）その差の偶奇が変化しないため、
% 2と置いてみたい。
- 任意の順列
に対して、
になるのが美しくて、感動した。
- 証明すると新しい知識が得られる問題は、楽しい👍
ソースコード
//Q_i = |P_i - i| % 2としたとき、任意の順列Pに対して(Q_0+Q_2+Q_4+...)=(Q_1+Q_3+Q_5+...)なの、美しい。 #include <iostream> #include <algorithm> #include <vector> #define rep(i, n) for(i = 0; i < n; i++) using namespace std; typedef pair<char, int> P; int n; int p[400], q[400]; int main() { int i, j; cin >> n; rep(i, n) { cin >> p[i]; p[i]--; q[i] = abs(p[i] - i) % 2; } vector<P> ans; rep(i, n) { for (j = i; j >= 2; j -= 2) { if (q[j - 2] < q[j]) { swap(q[j - 2], q[j]); swap(p[j - 2], p[j]); ans.push_back(P('B', j - 2)); } } } for (i = 0; i + 1 < n; i += 2) { if (q[i] == 1 && q[i + 1] == 1) { q[i] = 0; q[i + 1] = 0; swap(p[i], p[i + 1]); ans.push_back(P('A', i)); } } rep(i, n) { for (j = i; j >= 2; j -= 2) { if (p[j - 2] > p[j]) { swap(p[j - 2], p[j]); ans.push_back(P('B', j - 2)); } } } cout << ans.size() << endl; rep(i, ans.size()) { cout << ans[i].first << " " << ans[i].second + 1 << endl; } return 0; }
ARC146 C - Even XOR (600, 橙)
お気持ち
- 本番は、「奇数個OKの条件がなければ／0が必ずSに含まれる場合なら」簡単なのになぁと思いながら複雑に考えてしまい、頭が爆発しました。
- 最初に思いつきやすいのは、以下の性質かなと思います。そして、この辺の考えがグルグル回ってしまい、収集がつかなくなるのも日常茶飯事。
- (1) 集合Sが独立なら部分集合のXORは相異なる
- (2) 集合Sが独立という条件なら数え上げが簡単
- (3) 集合Sに必ず0を入れるパターンはS/{0}が独立ならOK
- あながち悪い方針ではないですが、(2)(3)は特殊ケースの性質になっていて、(1)や(1)の証明に使われる性質を上手く活かせていない気がします。もう少し基本的な性質を見ていきたいですね。
考察
基本的な操作に対して、いい性質を見つけていく感じで解けました。
2枚目のメモにWAと書いてありますが、解法は正しいです。
最初、サンプル1の答えが11になったので首をかしげていましたが、 の逆元を計算していなかっただけでした。
ソースコード
#include <iostream> #include <atcoder/modint> #define rep(i, n) for(i = 0; i < n; i++) using namespace std; using namespace atcoder; using mint = modint998244353; int n; mint dp[200002][2]; mint pw2[200002]; mint inv[200002], fact[200002], finv[200002]; //(n+1)!の逆数まで使うので注意 void init(int n) { int i; pw2[0] = 1; rep(i, n) pw2[i + 1] = pw2[i] * 2; inv[1] = fact[1] = fact[0] = finv[1] = finv[0] = 1; int mod = 998244353; for (i = 2; i <= n; i++) { fact[i] = i * fact[i - 1]; inv[i] = -inv[mod % i] * (mod / i); finv[i] = inv[i] * finv[i - 1]; } } int main() { int i, j; cin >> n; init(n + 1); dp[0][0] = 1; dp[0][1] = 0; dp[1][0] = pw2[n] - 1; dp[1][1] = 1; for (i = 1; i <= n; i++) { dp[i + 1][0] = dp[i][0] * (pw2[n] - pw2[i]); dp[i + 1][1] = dp[i][0] * pw2[i - 1] + dp[i][1] * (pw2[n] - pw2[i - 1]); } mint ans = 0; rep(i, n + 2) { ans += (dp[i][0] + dp[i][1]) * finv[i]; } cout << ans.val() << endl; return 0; }
引き返す遷移のある双六の期待回数
問題文など
昨日のくしらっちょさん*1のツイートで気になったので、時間計算量 で解いてみました。
怠惰人間なので余りを取っていないです。
今日の東海オンエアの動画で気になった。
— くしらっちょ (@kusirakusira) 2023年8月9日
3, 5の2種類の数字が等確率で出るサイコロを使ってNマスの双六をする。また、この双六ではあがるためにはピッタリゴールマスに着く必要があり、通り越したらその分だけ引き返す。
ゴールするためにサイコロを振る回数の期待値をmod998.... で求めよ。
解法
実装を簡単にするため、 が
以下の時は手計算で解き、
は
以上とします。
マス～
のいずれかに初めて到達すれば、マス
～
の双六に帰着できて、そこからは連立方程式で解けます。動的計画法の漸化式など、細かい部分を合わせるのが難しくて嵌ってしまいました。
詳細は画像の通りです。1枚目の冒頭にあるように期待値が収束しないゲームを構成することもできるので、について答えが収束することを本当は言わないといけないんですが、多分大丈夫でしょうということで（えぇ.....）
数学お強い方いらっしゃいましたら、収束性をご教示いただけますと（他力本願）
実装
import numpy as np def solve(n: int) -> float: if n == 1: return 1 if n == 2: return 4 if n == 3: A = np.array([[0, -1/2, 1], [-1/2, 1, -1/2], [1, -1, 0]]) A_inv = np.linalg.inv(A) b = np.array([1, 1, 1]).T return (A_inv @ b)[2] else: p = [0] * (n + 1) a = [0] * (n + 1) p[0] = 1 a[0] = 0 def fp(i: int) -> float: if 0 <= i and i <= n - 5: return p[i] return 0 for i in range(1, n + 1): p[i] = 1/2 * fp(i - 3) + 1/2 * fp(i - 5) if p[i] == 0: a[i] = 0 else: a[i] = (1/2 * fp(i - 3) * a[i - 3] + 1/2 * fp(i - 5) * a[i - 5]) / p[i] + 1 mat_A = np.array([[-1, 0, 0, 1], [0, -1/2, 1, 0], [-1/2, 1, -1/2, 0], [1, -1/2, 0, -1/2]]) A_inv = np.linalg.inv(mat_A) b = np.array([1, 1, 1, 1]).T E = [0] + list(A_inv @ b) A = [a[n], a[n - 1], a[n - 2], a[n - 3], a[n - 4]] P = [p[n], p[n - 1], p[n - 2], p[n - 3], p[n - 4]] ans = 0 for i in range(5): ans += P[i] * (A[i] + E[i]) return ans if __name__ == '__main__': n = int(input()) print(solve(n))
モンテカルロ法によるランダム試行
確率漸化式の問題は、とりあえずランダム試行をして当たりをつけると、デバッグなどがしやすいと思います。 回試行すると、大体
くらいの誤差に収束すると思います。（この辺あまり詳しくない）
#include <iostream> #include <random> #include <cstdio> #define rep(i, n) for(i = 0; i < n; i++) using namespace std; mt19937 mt(252521); int simurate(int n) { int pos = 0, cnt = 0; while (true) { cnt++; if (mt() % 2 == 0) pos += 3; else pos += 5; pos %= (2 * n); if (pos == n) break; else if (pos > n) { pos = 2 * n - pos; } } return cnt; } signed main() { int n, T = 1000000; cin >> n; double ans = 0; for (int t = 0; t < T; t++) { ans += simurate(n); } ans /= T; printf("%.14f\n", ans); return 0; }
感想
ABC-Fにありそう（主観）。
解いたことがなかったので、面白かったです。
（もっと計算量の小さい解法、あるのかなぁ？）
*1:し→ちに修正。ごめん。
JOI2010春合宿day2-A. a+b problem (Lv.8)
考察メモ
- 次のように手順を分解すると解きやすかったです。
- 入力を扱いやすい形式で受け取る
- 桁上がりなしの形式を作る
- 桁上がりを計算する
- 出力形式を作る
- 考えた具体例
- 桁上がりが発生する＆桁数が異なる基本ケース
- 1 + 9999のように最後まで繰り返し桁が上がるケース
- 3344+55566のように桁上がりがストップするケース
回答コード(C++)
#include <iostream> #include <algorithm> #include <vector> #include <cassert> #define int long long #define rep(i, n) for(i = 0; i < n; i++) using namespace std; vector<int> A, LA, rLA; vector<int> B, LB, rLB; vector<int> a, b; //桁上がり前の結果. Σ a[i] * (10^b[i] + ... + 10^(b[i + 1] - 1)) (0 <= a[i] <= 18, 0 <= i < a.size()), b.size() = a.size() + 1 vector<int> c; //桁上がり後の結果. Σ c[i] * (10^b[i] + ... + 10^(b[i + 1] - 1)) (0 <= c[i] <= 9) void input_number(vector<int> &digits, vector<int> &lengths, vector<int> &rui_lengths) { int n; cin >> n; digits.resize(n); lengths.resize(n); for (int i = n - 1; i >= 0; i--) { cin >> digits[i] >> lengths[i]; } rui_lengths.resize(n + 1); rui_lengths[0] = 0; for (int i = 1; i <= n; i++) rui_lengths[i] = rui_lengths[i - 1] + lengths[i - 1]; } void input() { input_number(A, LA, rLA); input_number(B, LB, rLB); } void add_number(vector<int> A, vector<int> rLA, vector<int> B, vector<int> rLB, vector<int> &a, vector<int> &b) { int i; rep(i, rLA.size()) { b.push_back(rLA[i]); b.push_back(rLA[i] + 1); } rep(i, rLB.size()) { b.push_back(rLB[i]); b.push_back(rLB[i] + 1); } sort(b.begin(), b.end()); b.erase(unique(b.begin(), b.end()), b.end()); int j1 = 0, j2 = 0; rep(i, (int)b.size() - 1) { while (j1 < rLA.size() && rLA[j1] <= b[i]) j1++; while (j2 < rLB.size() && rLB[j2] <= b[i]) j2++; int d1 = (j1 >= rLA.size()) ? 0 : A[j1 - 1]; int d2 = (j2 >= rLB.size()) ? 0 : B[j2 - 1]; a.push_back(d1 + d2); } } //convert: (a, b) -> (c, b) void carry(vector<int> &a, vector<int> &b, vector<int> &c) { int i; c.resize(b.size()); rep(i, a.size()) { c[i] += a[i]; c[i + 1] += c[i] / 10; c[i] %= 10; } } void create_output_format(vector<int> &c, vector<int> &b, vector<int> &digits, vector<int> &lens) { int n = c.size(), i; int len = 0; assert(b.size() == n); rep(i, n) { if (i > 0 && c[i - 1] != c[i]) { digits.push_back(c[i - 1]); lens.push_back(len); len = 0; } if (i + 1 < n) len += b[i + 1] - b[i]; else len++; } digits.push_back(c[n - 1]); lens.push_back(len); for (i = (int)digits.size() - 1; i > 0 && digits[i] == 0; i--); digits.resize(i + 1); lens.resize(i + 1); } void output(vector<int> &digits, vector<int> &lens) { cout << digits.size() << endl; assert((*digits.rbegin()) > 0); for (int i = (int)digits.size() - 1; i >= 0; i--) { cout << digits[i] << " " << lens[i] << endl; } } signed main() { input(); add_number(A, rLA, B, rLB, a, b); carry(a, b, c); vector<int> digits, lens; create_output_format(c, b, digits, lens); output(digits, lens); return 0; }
回答コード(Python)
from typing import List, Tuple class JOIsp2010Day2A: def __init__(self): # 下の桁からA[0]がLA[0]桁, A[1]がLA[1]桁, ...の形式. rLA[0]=0, rLA[i]=LA[0]+...+LA[i-1]. self.A: List[int] = [] self.LA: List[int] = [] self.rLA: List[int] = [] self.B: List[int] = [] self.LB: List[int] = [] self.rLB: List[int] = [] def input_number(self) -> Tuple[List[int], List[int], List[int]]: n = int(input()) digits: List[int] = [0] * n lengths: List[int] = [0] * n for i in reversed(range(n)): digits[i], lengths[i] = map(int, input().split()) rui_lengths: List[int] = [0] * (n + 1) for i in range(1, n + 1): rui_lengths[i] = rui_lengths[i - 1] + lengths[i - 1] return digits, lengths, rui_lengths def input(self) -> None: self.A, self.LA, self.rLA = self.input_number() self.B, self.LB, self.rLB = self.input_number() # return: 桁上がりを忘れて、A + B = Σ a[i] * (10^b[i] + ... + 10^(b[i + 1] - 1)) (i=0,...,len(a)-1), len(b) = len(a) + 1の形式にする。 def add_number(self, A: List[int], rLA: List[int], B: List[int], rLB: List[int]) -> Tuple[List[int], List[int]]: b: List[int] = [] b.extend(rLA) b.extend(rLB) b.extend([item + 1 for item in rLA]) b.extend([item + 1 for item in rLB]) b = sorted(list(set(b))) j1: int = 0 j2: int = 0 a: List[int] = [] for i in range(len(b) - 1): while j1 < len(rLA) and rLA[j1] <= b[i]: j1 += 1 while j2 < len(rLB) and rLB[j2] <= b[i]: j2 += 1 d1: int = 0 if j1 >= len(rLA) else A[j1 - 1] d2: int = 0 if j2 >= len(rLB) else B[j2 - 1] a.append(d1 + d2) return a, b # convert: (a, b) -> (c, b), return: c def carry(self, a: List[int], b: List[int]) -> List[int]: c: List[int] = [0] * len(b) for i in range(len(a)): c[i] += a[i] c[i + 1] += c[i] // 10 c[i] %= 10 return c def create_output_format(self, c: List[int], b: List[int]) -> Tuple[List[int], List[int]]: n: int = len(c) length: int = 0 assert len(b) == n digits: List[int] = [] lens: List[int] = [] for i in range(n): if i > 0 and c[i - 1] != c[i]: digits.append(c[i - 1]) lens.append(length) length = 0 if i + 1 < n: length += b[i + 1] - b[i] else: length += 1 digits.append(c[n - 1]) lens.append(length) i: int = len(digits) - 1 while True: if digits[i] > 0: break i -= 1 digits = digits[:i + 1] lens = lens[:i + 1] return digits, lens def output(self, digits: List[int], lens: List[int]) -> None: print(len(digits)) for i in reversed(range(len(digits))): print(f"{digits[i]} {lens[i]}") def solve(self) -> None: self.input() a, b = self.add_number(self.A, self.rLA, self.B, self.rLB) c = self.carry(a, b) digits, lens = self.create_output_format(c, b) self.output(digits, lens) if __name__ == '__main__': solver = JOIsp2010Day2A() solver.solve()
