https://atcoder.jp/contests/abc207/tasks/abc207_a
https://atcoder.jp/contests/abc207/submissions/23802672
選んで手に取る組合せは3通りなのでそれをすべて列挙して最大値を求めてもいい。
自分の実装では、求めたい最大値は3つの数から大きい2つを取ってきて総和を取ったものであるため、
総和から最小値を引くことで、それを実現している。
int A, B, C; //--------------------------------------------------------------------------------------------------- void _main() { cin >> A >> B >> C; int ans = (A + B + C) - min({ A, B, C }); cout << ans << endl; }
https://atcoder.jp/contests/abc206/tasks/abc206_f
https://atcoder.jp/contests/abc206/submissions/23623437
今回の問題はgrundy数を知らないとまず解けない。
解説範囲がとても広くなってしまうので、grundy数についてはどこかで勉強してきてほしい。
だが、一応簡単に以下に説明する。
エッセンスだけ記載するが、理由も含めて他で学習してくるべきなので、調べて勉強してくるのがオススメ。
grundy数というのを各状態に対して計算を行う。
計算ルールとしては、
な感じ。最終的にgrundy数が0の状態が負け状態になり、それ以外は勝ち状態である。
今回は、この「状態」を適切に決定することでgrundy数の計算に持ち込むことができ、勝敗を判定できる。
端的には以下のようにする。
grundy(l,r) := 区間[l,r)がまだ選択可能な時のgrundy数
区間の範囲は[1,100)なので、grundy(1, 100)が0なら負け状態なのでBobの勝ち、それ以外ならAliceの勝ちとなる。
grundy数の計算では、遷移を意識する必要がある。
例えば、grundy(1,100)からの遷移を考えてみよう。
この場合は何も選択されてないということなので、N個の選択可能な区間がある。
例えば[4,6)を選択したとしよう。すると、選択後には区間は2つに分割される。
具体的には[1,4)と[6,100)に分割される。
この2つの区間は今後は独立に操作されることになる。
なので、grundy([1,4)∧[6,100))はgrundy([1,4)) xor grundy([6,100))として考えることができる。
ちょっと複雑な感じになったのでまとめると、
grundy(1,100)から区間[4,6)を選択した後のgrundy数はgrundy([1,4)) xor grundy([6,100))となる。
このようにあるgrundy(x,y)を計算するときは、さらに小さい区間のgrundy(x',y')の結果のみが必要となるので、
再帰的に、もしくは、区間DPのように計算を進めていくことでgrundy(1,100)を計算することができる。
後は0かそうでないかを判定するだけ。
int N, L[101], R[101]; //--------------------------------------------------------------------------------------------------- bool vis[101][101]; int memo[101][101]; int grundy(int l, int r) { if (vis[l][r]) return memo[l][r]; vis[l][r] = true; set<int> gs; rep(i, 0, N) if (l <= L[i] && R[i] <= r) gs.insert(grundy(l, L[i]) ^ grundy(R[i], r)); int g = 0; while (gs.count(g)) g++; return memo[l][r] = g; } //--------------------------------------------------------------------------------------------------- void solve() { cin >> N; rep(i, 0, N) cin >> L[i] >> R[i]; rep(l, 0, 101) rep(r, 0, 101) vis[l][r] = false; if (grundy(1, 100) == 0) cout << "Bob" << endl; else cout << "Alice" << endl; } //--------------------------------------------------------------------------------------------------- void _main() { int T; cin >> T; rep(t, 0, T) solve(); }
https://atcoder.jp/contests/abc206/tasks/abc206_e
https://atcoder.jp/contests/abc206/submissions/23623547
しょっぱなから発想の転換が必要な問題。
類題を多く解いているので、すぐ思いついたが、そうでないと難しい。
xとyを列挙して、条件を満たすかどうかを確認していくような流れでは今回は解けない。
そうではなく、最大公約数がgとなるようなx,yの組がどれだけあるかという目線で解いていく。
最大公約数gを全探索して、条件を満たす(x,y)の組がどれだけあるかを計算することで問題を考えていこう。
条件の少し緩くして考えてみよう。
条件を「g != 1」だけにした状態で問題が解けるかを考えてみる。
この問題が解ければ、大体解法は理解したようなもの。
数値の上限が106なので、同様にgの上限も106である。
これは全探索できそうである。
gを全探索して、最大公倍数がgとなる個数を数え上げよう。
最大公倍数がgとなるためには少なくとも、x,yはgの倍数である必要がある。
よって、[L,R]の中のgの倍数の個数、R/g-(L-1)/gがx,yの候補数であり、
(R/g-(L-1)/g)2が答えの組み合わせのように見える。
だが、これではgの倍数同士の組であることは言えるが、x=2g, y=2gのような最大公倍数がgの倍数となってしまう組も含まれる。
(R/g-(L-1)/g)2の中で適さないのは最大公倍数が2g, 3g, 4g, ...のものであり、これを取り除くいい方法がある。
約数系包除原理である。
エラトステネスの篩というか、調和級数的計算量というか、
g=1～Nの全てに対して2g, 3g, ...をN以下まで探索するようなループを書くと
全体の計算量はO(NlogN)になるというものがある。
何を言っているのか分からないという場合は、エラトステネスの篩のアルゴリズムを学ぶとどういうことか分かると思う。
コードベースで説明すると「rep(i,1,N) for(j=i;j<=N;j+=i) というループ構造はO(NlogN)で行える」ということ。
ここで言っていることは丁度、さっきやりたかったことである。
以下のような配列を用意して、適さない2g, 3g, 4g, ...を取り除くようなコードを書こう。
cnt[g] := 最大公倍数がgであるときの(x,y)の組合せ
実装の注意点としては、cnt[g]を計算するときにはcnt[2g], cnt[3g], ...を引く必要があるので、gは降順に計算していくこと。
これで、基本的にはcnt[g] = (R/g-(L-1)/g)2なのだが、これでは最大公倍数が2g, 3g, とかが混ざっているので、
gの倍数がR以下になるまでcnt[2g], cnt[3g], ...を引けば、ちょうど最大公倍数がgになるときの組み合わせが求められる。
後はcntの総和を取れば、少しだけ簡単にした問題は解ける。
元々の問題では、x != g, y != gという条件がついているので、別途、x=gまたはy=gのパターンを引いてやろう。
こうなるのは[L,R]にgが含まれているときだけで、
のように微調整してやることで元々の問題も解ける。
int L, R; ll cnt[1010101]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> L >> R; rrep(g, 1010100, 2) { cnt[g] = 1LL * (R / g - (L - 1) / g) * (R / g - (L - 1) / g); int x = 2 * g; while (x <= R) { cnt[g] -= cnt[x]; x += g; } } ll ans = 0; rep(g, 2, 1010101) { ans += cnt[g]; if (L <= g && g <= R) { ans -= R / g - (L - 1) / g; ans -= R / g - (L - 1) / g; ans++; } } cout << ans << endl; }
https://atcoder.jp/contests/abc206/tasks/abc206_d
https://atcoder.jp/contests/abc206/submissions/23624301
以下の解説は、この問題はUnionFindを知らないと理解は難しいので、どこかで学習してきてほしい。
UnionFindを知らなくても別の解法があるかも。
例えば、1 2 1 4という数列に対して、1を4にしたとすると、4 2 4 4となり、もともとの1と4がまとめられた操作のように見える。
（区別がなくなる）
ここからUnionFindを効果的に使う問題か？という所が自分は考察の始まりとなった。
1 2 3 4を考えてみると、1と4, 2と3が同一になる必要がある。
1-4
2-3
14と23の間については同じになる必要はない。
1 1 1 2 3 4を考えてみると、1と2, 1と3, 1と4が同一になる必要がある。
1-2
1-3
1-4
1と2が同じになるということは結果的に、123が同じになり、1234が同じになることになる。
よって、1234が1つになる、連結になるのに必要な最小回数は？ということになる。
例で見てみると、回文の対応する部分を見て、数字で同じになる関係に辺を貼ってみたときに、
連結関係にある所は最終的に1つの数になるし、連結関係間は操作に何も影響し合わないことが分かる。
なので、回文の対応する部分に辺を貼って連結成分を取り出したときに、連結成分ごとに1つの数にするのに必要な最小の操作回数を計算して総和を取れば答えになる。
最後の問題は各連結成分毎で1つの数にするために必要な最小回数はいくつかという部分である。
操作を思い返すと、毎回の操作で数が1つにまとまっている、つまり、数の種類が1つ減っていることに気が付く。
連結成分にk個の数字が含まれるとき、どんな操作をやっても種類が1つ減るのでk-1個になる。
なので、最小の操作回数を計算するのは、実質かかる操作回数を計算しているだけであり、k個から1個になるにはk-1回操作が必要なので、k-1回が答えとなる。
解法をまとめると、回文の対応する数字の組を辺として、UnionFindで連結成分を求める。
各連結成分について、含まれる数字の個数-1の総和を取れば答え。
int N, A[201010]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 0, N) cin >> A[i]; UnionFind uf(201010); rep(i, 0, N / 2) uf(A[i], A[N - 1 - i]); int ans = 0; rep(i, 0, 201010) if (uf[i] == i) ans += uf.getValues(i) - 1; cout << ans << endl; }
https://atcoder.jp/contests/abc206/tasks/abc206_c
https://atcoder.jp/contests/abc206/submissions/23625007
まず、i,jの組を全探索する方針があるが、これは9*1010通りとなるので間に合わない。
全探索系は107くらいが上限。
だが、片方だけ全探索するのは間に合う。
片方を全探索して、もう片方は効率よく求める方針で解いていこう。
iでもいいのだが、i＜jの場合はjを全探索する方針で自分は良く解いている。
逆を全探索しても本質は特に変わらない。
jを固定化したときに条件を満たすiの個数を高速に求めることができれば、その総和を取れば答えになる。
条件はA[i] != A[j]であるが、今回は余事象を使うことにしよう。
つまりA[i] == A[j]を使うということだが、以下のように考える。
(条件を満たすiの個数)
= (全体) - (条件を満たさないiの個数)
= j - (A[i] == A[j]となるiの個数)
i,jを0-indexedで考えているので、全体はjとなっている。
上記の式までをまずは理解しよう。
これを高速に求めるためにC++ではmapを使おう。
mapを使って以下の配列を用意しておく。
cnt[x] := A[i]=xとなるiの個数
これをjを0から探索していくときに同時に更新していくことで、
とあるjを計算するときには「0～j-1のA[j]について、cnt配列が構築されている」状態を維持することができる。
なので、jを評価する時点でのcntはj未満の結果、つまり、i＜jの条件を満たした状態の結果が入っていることになる。
よって、cnt[A[j]]がA[i] == A[j]となるiの個数として使えることになる。
後は、実装を頑張る。
mapが使えない場合は座標圧縮というテクを使って普通の配列に乗る様に頑張る必要があるが、座標圧縮を知らない場合はmapを勉強する方がたぶん早い。
あと、C++になじみがない人向けに書くと、mapは辞書配列のことである。
int N, A[301010]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 0, N) cin >> A[i]; map<int, int> cnt; ll ans = 0; rep(j, 0, N) { ans += j - cnt[A[j]]; cnt[A[j]]++; } cout << ans << endl; }
https://atcoder.jp/contests/abc206/tasks/abc206_b
https://atcoder.jp/contests/abc206/submissions/23625300
この問題は実は1日目から順番にシミュレートすれば間に合う。
200点問題ではあるが、ちょっと計算量について考え始めると心配になったりするかもしれない。
1+2+3+...+nという等差数列の総和は、公式を適用するとn(n+1)/2である。
Nの最大値は109であるが、n=105を入れてみると既に最大値を超えてしまう。
ちょっとだけ詳しく書くと総和をN以上にするためには、単純に足し合わせても約sqrt(N)日くらいでNを上回るので、
これはシミュレーションしても問題ない上限である。
1+2+3+...というのをシミュレーションしていき、N以上となったら、その時の日付を答える。
注意点は特にないが、個人的には上限をsqrt(N)とかにするよりかは適当に間に合う上限を入れておいた方が事故が少ない。
正直、上限をあまり厳密に評価してないが、余裕があるなら遊びを持たせておくぐらいの保険を自分はいつもいれている。
int N; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; int tot = 0; rep(day, 1, 1010101) { tot += day; if (N <= tot) { cout << day << endl; return; } } }
https://atcoder.jp/contests/abc206/tasks/abc206_a
https://atcoder.jp/contests/abc206/submissions/23625515
今回の問題で精度が要求されるかは分からないが、テクとして、小数計算は精度が心配だから、できるなら整数で計算するというものがある。
今回要求されている、1.08×Nの小数点以下切り捨ては、普通にやると1.08×Nで一旦小数表現がなされる。
この表現時に精度問題が発生する可能性があるので、「108×N/100の切り捨て」と言い換える。
こうすると108×Nは整数で計算ができ、100での切り捨てをすることで一度も小数を介することなく、元の計算が行える。
このように小数表現を排除する手法は床関数で答えを出すときに良く使えるので覚えておくと、役立つときがあるだろう。
後は独特な出力表現なので、typoしないように気を付けよう。
int N; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; int included = N * 108 / 100; if (included < 206) cout << "Yay!" << endl; else if (included == 206) cout << "so-so" << endl; else cout << ":(" << endl; }
