初の、NoSub。戦術的なやつではなく、手元でサンプルを通すことも叶わずでした。
最初、2倍3倍5倍の全探索（過不足を最後に調整）かと思ったんですけど、これだと途中で+1が挟まるパターンに対応できず。
次にメモ化再帰とBFSを考えましたが、これだと数字が大きくなると到底間に合いません。枝狩りとか、キューをpriority_queueにするとか無駄な抵抗をしてみましたがだめでした。
後ろから？ともちょっとは考えましたが、それで事態が好転するようなこともなく・・・。
見ました。見ただけ。
NoSubは残念ですが、今回大虐殺回だったっぽいのでいかんともしがたいですね。
https://codeforces.com/contest/1352/problem/G
整数nが与えられる。隣り合う項の差の絶対値が2以上4以下となるような、長さnの順列を作れ。無理な場合は-1を出力せよ。
これは気づいてしまえばおしまいという問題で、以下の手順でできてしまいます。
... 9 7 5 3 1）4 2と並べる（... 9 7 5 3 1 4 2）... 9 7 5 3 1 4 2 6 8 10 ...）なお、nが3以下の場合は無理です。n=2は1 2または2 1の二通りしかないので無理ですし、n=3でも2が1か3のどちらかには必ず隣接するので無理です。
#include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while (t--) { int n; cin >> n; if (n < 4) { cout << -1 << endl; continue; } int m = n + (n % 2 - 1); for (int i = m; i > 0; i -= 2) cout << i << " "; cout << "4 2" << (n < 6 ? '\n' : ' '); for (int i = 6; i <= n; i += 2) cout << i << (i >= n - 1 ? '\n' : ' '); } }
初のDiv. 4は、個人的には思ったより考察難易度が高かったことに驚いたのですが、難易度の傾斜はゆるくてたしかにたくさんの問題に挑戦できるようにという意図は満たしているように思いました。
今後もDiv. 4の記事は優先的に書いていきたいですね。
って、実はまだCの解説を書いてないんですけどね。なぜなら通せてないから。on_
https://codeforces.com/contest/1352/problem/F
'0'と'1'で構成された文字列を考える。その文字列の隣接した2文字を数値として足して和が0, 1, 2になる区間の合計数がそれぞれ与えられる。
例えば文字列1110011110の場合、11, 11, 10, 00, 01, 11, 11, 11, 10に分けることができて、0となる区間は1つ、1となる区間は3つ、2となる区間は5つであり、この3つの数が与えられる。
与えられた条件を満たす文字列を復元せよ。ただし復元できることは保証される。
場合分けをしてみます。簡単な方から考えてみましょう。
0を並べるだけです。与えられた数+1の0を並べると条件を満たせます。
0と1を交互に並べるだけです。これも文字列の長さが与えられた数+1になるように並べればよいです。
1を並べるだけです。与えられた数+1の1を並べます。
最初のサンプルの`(1, 3, 5)'で考えてみましょう。
0となる場合が1なので、1 + 1 = 2つの1を並べて00とします。
また、2となる場合が5なので、同様に1を並べて111111とします。
これを繋げてみます。0の場合と2の場合はすべて消費した状態で00111111となります。
ここで、連結部分が'01'であるため1の場合が一つ消費されて残りは2つです。あとはその2つを消費できるように末尾に0と1を交互に並べます。
0011111101となります。これで完成です。すべて0ではない場合は、与えられた数字がなんであれこの考え方で復元することができます。
`(0, 3, 5)'で先ほどと同じように考えてみます。
0はないので最初の手順は不要です。次に2となる場合が5なので111111とできます。
最後に1となる場合ですが、先程と違ってまだ0と1の連結がないので、末尾には3つの1ができるよう交互に連結します。
111111010となり、これで完成です。
このケースはありえません。0を作るためには2つの0が、2と作るためには2つの1が必要で、これを繋げるとどうしても01または10の区間ができてしまうためです。
`(5, 3, 0)'で考えてみます。
0となる場合が5なので000000とします。2となる場合はないので作成不要です。最後に、1を作るために交互に並べます。
000000101です。実装上は、このケースでは末尾が0の状態で最後の手順になるので、そこで1から交互に並べないといけないことに気をつけます。
このケースは制約がn0 + n1 + n2 > 0なのでありえません。
とここまでをコードにすると完成です。
#include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while (t--) { int n0, n1, n2; cin >> n0 >> n1 >> n2; string ans = ""; if (n0 > 0) ans += string(n0 + 1, '0'); if (n2 > 0) ans += string(n2 + 1, '1'); if (n1 > 0) { if (n0 > 0 and n2 > 0) { for (int i = 0; i < n1 - 1; i++) ans += (i % 2 == 0 ? '0' : '1'); } else if (n0 > 0) { for (int i = 0; i < n1; i++) ans += (i % 2 == 0 ? '1' : '0'); } else if (n2 > 0) { for (int i = 0; i < n1; i++) ans += (i % 2 == 0 ? '0' : '1'); } else { for (int i = 0; i < n1 + 1; i++) ans += (i % 2 == 0 ? '0' : '1'); } } cout << ans << endl; } }
まさかの1日2回幾何ｗｗｗ（えでゅふぉとABC）
しかもsin, cos, tan全部出てきました。
10で剰余を取って、後はif文で頑張りましょう。"hon"の時をelseにするのが一番効率がいいということにあとで気づきましたが、まあ誤差の範囲です。
問題文をそのままコードに落とす系。基本的な文字列操作ができればできる問題です。
幾何！
時計の中心を(0, 0)とした平面座標と考えて、指定した時刻にそれぞれの針の先端が平面座標のどの点に来るかを三角比で求め、後は二点間の距離です。
（追記）余弦定理？知らない子ですね。（←本当に気づかなかった人です・・・
ABCのDは全探索のD!
幅優先探索します。置くべき道標は、直前にいた部屋の番号です。
ACならず。
A = B = 0の場合はどれと組んでも0になるので、それに関わる組み合わせすべてがだめA = 0とB = 0の組み合わせはだめAi * Bi > 0とAj * Bj < 0でAi / Bi = Bj / Ajとなる組み合わせはだめかと思ったんですけど、どうなんでしょうか？
あと、あってるとしてその場合の数を出す方法もわからずじまいでした。（だめやん
みてません。
幾何でまごついたおかげで突き抜けたパフォーマンスにはならず。でも水色復帰にまた一歩前進です。
いやーでも数え上げのEはなんとかしたかったという気持ちもありつつ。
制約について考えさせられる問題でした。
https://codeforces.com/contest/1352/problem/E
長さnの数列が与えられる。各項は1以上n以下の整数である。
各項の値について、その数列の連続する2つ以上の項の和で表すことができる場合、その項は「特別」であるとする。
与えられた数列に「特別」な項がいくつあるかを答えよ。
TLが1秒でMLが64MBと、制約がきついです。
私はきっちりTLEもMLEも取りました。とほほ。
まず、累積和を取って一つ一つしゃくとり法で確かめていくという実装をしたところ、TLEでした。（しゃくとり法はO(n)で全体でO(n2)だから間に合うと思ったのですが・・・。最悪ケースで左右のポインタが一つずつ交互に動くケースが思ったより遅いということのようです。落ちたテストケースを参照してください。）
https://codeforces.com/contest/1352/submission/79522413
和の探索に時間がかかるなら前もってすべて列挙してしまえばいいのでは？と思って実行に移してはいけません。この問題はMLが64MBです。
https://codeforces.com/contest/1352/submission/79529811
はい、見事にMLEで落ちます。
最初の方針でしゃくとり法を二分探索に変えると、割とギリギリですがなんとか通ります。
#include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while (t--) { int n; cin >> n; vector<int> a(n); vector<int> sum(n + 1); for (int i = 0; i < n; i++) { cin >> a[i]; sum[i + 1] = sum[i] + a[i]; } int ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n - 1; j++) { auto itr = lower_bound(sum.begin() + j + 2, sum.end(), a[i] + sum[j]); if (itr != sum.end() and *itr == a[i] + sum[j]) { ans++; break; } } } cout << ans << endl; } }
Editorialによれば
ということだそうです。
#include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while (t--) { int n; cin >> n; vector<int> a(n); vector<int> cnt(n + 1); for (int i = 0; i < n; i++) { cin >> a[i]; cnt[a[i]]++; } int ans = 0; for (int i = 0; i < n - 1; i++) { int sum = 0; for (int j = i; j < n; j++) { sum += a[j]; // i == j のときはまだ一つしか足していないので続行 if (i == j) continue; if (sum <= n) { ans += cnt[sum]; // 同じ値を二度以上足さないように cnt[sum] = 0; } } } cout << ans << endl; } }
私が通した回答より10倍以上速いです。（白目
https://codeforces.com/contest/1352/problem/D
非負整数で構成された長さnの数列が与えられる。アリスは右からボブは左から以下の規則のとおりに数列の数字を取っていく。
二人が最後まで取りきった時のターン数とそれぞれが取った数字の合計を答えよ。
単純にシミュレーションしても線形時間で終わりますし制約は2*10^5なので、与えられた条件に沿って素直に実装するだけです。
#include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while (t--) { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; int prev = 0; int turn = 0; int alice = 0; int bob = 0; int l = 0; int r = n - 1; while (l <= r) { int cur = 0; if (turn % 2 == 0) { while (cur <= prev and l <= r) { cur += a[l]; l++; } alice += cur; } else { while (cur <= prev and l <= r) { cur += a[r]; r--; } bob += cur; } turn++; prev = cur; } cout << turn << " " << alice << " " << bob << endl; } }
Div. 4、こういうシンプルな問題がもっと出るのかと思ってました。
4完1WA1RE。
こどふぉDiv. 2のAとか、ABCのBに強烈な苦手意識があるのをなんとかしたい今日この頃。
SとTの|S|文字までを比較して、すべて一致すればYes、しなければNoです。
A >= Kなら1をK枚引けるのでK、A + B >= Kなら1をA枚と0をK - A枚引けるのでA、それ以外ならマイナスを引かざるを得ずA - (K - (A + B))が答えとなります。
なんとA >= KならAとやって、1WAもらいました。アホですか・・・。
で、実は最初愚直なシミュレーションを書いていて、いやこれ2 * 10^9だとさすがにTLEするやろと思って止めたんですよね。
通るんかい・・・。
ABCのCは全探索のCです！
今回はbit全探索でした。
まずシミュレーションして、閉路を探します。次に閉路の入り口までのステップ数と、閉路の中のステップ数と、テレポート順を確認します。あとは簡単な算数で終わりです。
私は閉路の入り口までたどり着く前に終わるパターンを失念していて1REもらいました。とほほ・・・。
普段なら、Eの500に数え上げが出たらそこで勝負ですが、今回はファーストインプレッションでダメっぽかったので捨ててFに行きました。
最終的な実装は、まずはじめから括弧列になっているところは消去して、)(型で残った分をまず繋げて、(と)を)(型にくっつけて、最後に(と)をくっつけて、とやったのですが半分近くWAでした。
何か大きな考察ミスか漏れがあるのでしょう。
まあCとDはすんなりいって、水パフォで今日の最低目標であったレート1100台復帰をぴったり達成できたのでまあよかったのかな、と。
いやでも本当にBあたりでハマるのをなんとかしたくはあります。
