結果
1完でひどい。
Aが落ちてたり、他にもデバッグ出力を消し忘れてWAしたりTLE解を気づかずに出してたりと非常に頭が悪い。
大反省。。。
ただ、問題は面白かったです。
A. Infinite Sequence
問題
初項a, 公差cの等差数列にbが出現するかどうか判定せよ。
解法
-109 <= a, b, c <= 109と制約がでかいので、愚直にループを回すことはできません。よって場合分けを考えます。
以下のコードはすぎむさんの解法を参考に組み直したものです。これがとてもシンプルで頭がいいと思います。
本番の僕のコードではa == bを判定するタイミングが遅くて、c == 0とともに成り立つときしか通らないようになってしまっていました…。あと、負の剰余は危ないと思って避けたのですが、あまりが0かどうかを判定するだけなら大丈夫みたいです。
int a, b, c; bool solve() { if (c == 0) return a == b; return (b - a) % c == 0 && (b - a) / c >= 0; } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(0); cin >> a >> b >> c; cout << (solve() ? "YES" : "NO") << endl; }
B. Restoring Painting
問題
3 * 3のマス目がある。
- マスには1以上n以下の数字が入る。
- 角と真ん中以外の4マスの数字は既に決まっている。(a, b, c, d)
- 2*2の範囲4通りの和はどれも等しい。
これらの条件を満たす数字の埋め方は何通りあるか？
詳しくは問題文の図を参照。*1
解法
まず、真ん中の要素は1からnのなんでもよいことがわかります。なぜなら真ん中の要素がなんであっても、2*2の4通りの領域の和の関係(差)は変わらないからです。
また、左上の要素を決めると、左下、右上、右下の要素は自動的に決まります。なので左上の要素を全探索して4つの角の値が条件(1以上n以下)を満たすものの個数 * n(真ん中の数字はなんでもよいのでn通り) が答えになります。
ただ、本番ではちょっと難しく考えていて、O(1)解法で解きました。2*2の正方形領域の確定している値の和はa + b, a + c, b + d, c + dです。これらの最小値をA, 最大値をBとします。すると4つの角の値のうち、Aの正方形領域に含まれる角の値xとBの正方形領域に含まれる角の値yの差が、角の値どうしの差の中では最大になります。xを決めたとき、x + A = y + B より y = x + B - A です。1 <= y <= n より、1 + (B - A) <= x <= n + (B - A) (式1)となります。一方 1 <= x <= n (式2)です。よって条件を満たすxの区間はは式1と式2の共通部分です。式1, 2は真ん中の値によらないので、n * (共通部分の長さ) をO(1)で求めることができます。
signed main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int n, a, b, c, d; cin >> n >> a >> b >> c >> d; int A = min({a + b, a + c, b + d, c + d}); int B = max({a + b, a + c, b + d, c + d}); int lb = 1 + (B - A); int m = max(n - lb + 1, 0LL); cout << n * m << endl; }
C. Money Transfers
問題
円環上に頂点1, 2, ..., Nが並んでいる。各頂点に整数x_iが与えられている。隣り合う頂点についてi, jについてx_i += d, x_j -= d (d は任意の数) という操作が可能である。すべてのx_iを0にするための最小の操作回数を求めよ。(ただしすべてのx_iを0にできることが保証されている。すなわち、x_iの総和は0である。)
解法
円環は、いくつかの「総和が0になる区間」に分けることができます。このとき、作ることのできる区間の個数の最大数がkであったとすると、必要な操作回数はn - kになります(各区間では、長さをlとするとl - 1回の操作が必要になるので)。よってこの問題は、円環をできるだけ多くの総和が0になる区間に分割する問題に帰着されます。
では、kの値はどう求めればよいでしょうか？ 円環の問題と言えば切る位置を全通り試して直線として処理するという方法がありますが、この問題はn <= 105なのでO(n2)解法は効きません。
そこで累積和を用います。例えば左からの累積和が{3, 5, 7, 3, 0}となったとすると、1つ目の3のすぐ右から2つ目の3までの区間は総和が 0であることがわかります。総和が0だからこそ同じ値に戻ったわけです。この例では[1, 4]と[5, 1] (端をまたぐ区間)という2つの総和が0になる区間を作ることができます。
この考えを使うと、累積和において、登場する回数が最大の数の分だけ区間が作れます。よって答えは n - (累積和に最も多く出現する数の出現回数) です。
本番では累積和まではやっていたけど、最大の頻度を取るというところまで行き着かなかった。
signed main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int N; cin >> N; vector<int> a(N + 1, 0); rep(i, N) { cin >> a[i]; } rep(i, N) { a[i + 1] += a[i]; } map<int, int> cnt; int mx = -1; rep(i, N) { cnt[a[i]]++; mx = max(mx, cnt[a[i]]); } cout << N - mx << endl; }
D. Tree Construction
問題
二分探索木に値を挿入する順番が与えられるので、うまくやってください。(n <= 105)
解法
n <= 1000 くらいなら、もちろん木をたどって行きついたところに挿入していけばOKです。しかし n <= 105 なのでO(nlogn)程度の解法を考える必要があります。
ある値xを挿入するとき、xの親となるのは、既に木に存在する値の中でx以上の最小の要素 or x未満の最大の要素です。そこで、以下の方法が考えられます。
- 既に木に挿入した値をsetで管理する
- upper_boundによりx以上の最小の要素をsetから見つける
実は2ができれば、そのすぐ左がx未満の最大の要素なので、2つとも求まったことになります。まずx以上の最小の要素に繋ごうとしてみます。このとき、x以上の最小の要素が存在しないか、あるいは存在してもそいつが既に左側の子を持っている場合にはイテレータを1つ左にずらして、x未満の最大の要素に右側の子として繋ぎます。(この操作は4->6 に5を挿入するような場合に必要になります)
以下は想定解を写経しました。こういうイテレータゲーは苦手です。。。
signed main() { std::ios::sync_with_stdio(false); std::cin.tie(0); set<int> numbers; map<int, int> left; map<int, int> right; int n, v; cin >> n >> v; numbers.insert(v); rep(i, n - 1) { cin >> v; // vより大きい要素が現れる最初の位置 auto it = numbers.upper_bound(v); int result; // vより大きい要素が以前に存在し、そのうち最小の要素に左側の子がまだないならば if (it != numbers.end()&& left.count(*it) == 0) { // そいつを親とする left[*it] = v; result = *it; } // vより大きい要素が存在しない、 // あるいはvより大きい要素は存在するがそのうち最小の要素に // 既に左側の子があった場合、 else { // 左に1つずらして、そいつを親とする it--; right[*it] = v; result = *it; } numbers.insert(v); cout << result << (i == n - 2 ? '\n' : ' '); } }
次こそは4完するぞー。
*1:575
