競プロ日記

TOP

主にAtCoderで解いた問題の感想とか詰まったところとかを記録します。
自分に対する解説的な一面はありますが、解説ブログを書いているつもりは一切ありません。

AtCoder マイページ
2019/12　現在緑

シンタックスハイライトが働かなくなってしまったので、適当な無料レンタルサーバー借りてWordPressに移行予定。

ABC150

問題

unrated

3完
新年初競プロ&新年初C++。
コンテスト前にABCのC問題までくらい1つ解いておこうと思ったが映画見てご飯食べてたら時間なくなった。

そして2連続unrated。
unratedに気づいた後色々あってやる気を失った。
unratedじゃなかったらたぶん4完。

色々書いたけどなんか記事消えたので適当。
保存する押して保存しましたのダイアログと共に消えるの頭おかしいだろ。
忍者ブログ本当に嫌。

A問題

かんたん。
チェック段階でkとxを2回間違えてチェックした。
焦りすぎ。

B問題

もしかしてcount関数ってStringに特殊化されて文字列も数えられる？？？と淡い期待を抱いて実行したら普通にコンパイルエラー。
素直にループ回した。

C問題

考察実装5分next_permutationの使い方調べるの5分。
なんとなくnext_permutationは順列を扱えるくらいしか知らなかったが、知ってるのは強いね。
初めて使ってみて勉強になった。

D問題

unratedの根源。
わざわざ問題文にa[i]は偶数と書いてあったのに奇数が紛れていたらしい。

「最小公倍数は整数をかける場合の最も小さい公倍数なので、整数+0.5をかける場合の最小の半公倍数は最小公倍数の半分。半公倍数の間隔は最小公倍数。」
という考察をコンテスト中にしたが、半分間違っていた。
「最小公倍数は整数をかける場合の最も小さい公倍数なので、整数+0.5をかける場合の最小の半公倍数になる可能性があるのは最小公倍数の半分。半公倍数が存在するなら間隔は最小公倍数。」
というのが正しい。

というのも、最小の公倍数をZとおくと、Z / a[i]が偶数になるa[i]が存在した場合、最小の半公倍数となる(Z / 2) / a[i]が整数となってしまい、X = a[i] * (p + 0.5)を満たせない。
間隔となる最小公倍数のn倍を足しても必ず満たさないので、半公倍数は存在しないことになる。

ということで、基本的には(Z / 2) + nZ {n:0以上の整数}が半公倍数の数で、答えとなるM以下のものの数は簡単に計算できるが、Z / a[i]が偶数となるa[i]が1つでも存在したら半公倍数は存在しない。

コンテスト中はTLE+WAで、色々改善してTLEはなくしたが、後半15個のWAがなくならなかった。
途中で間違えてEに提出してしまったり、そもそもunratedだったりと、WAは入力ミスが原因だろうと1時間くらいで解くのをやめた。
しかしコンテスト終了後に提出してもWAだった。
改めて考察し直してみると、Twitterで偶奇が云々という記述をいくつか見ていたのもあり、最後の偶奇のチェックが必要だとすぐに気付けた。
unratedで解くのをやめていなければ自力で気付けたと思うが、ちょっと時間かかってたかも。
それでも十分時間内に間に合ったとは思うが。

E問題

やる気はなかったが方針だけは途中まで立てた。
解説を見る限り基本的には合ってそう。
たぶんその先は時間内に思いつけない。

Σa[i] * b[j]を最小化するタイプの問題なので、昇順ソートと降順ソート同士でかけ合わせれば良い。
S[i]が異なっていると置くと、残りN-1個の選び方2^(N-1)の中でC[i]が何番目に大きいかが分かれば良い。

というのをぼーっと考えていたが、進まなかった。
部分問題まで辿り着けたのは成長だが、そろそろ先に進まないといけない頃合い。
後でしっかり解説読んで理解しよう。

F問題

やる気ない中でXORの文字を見つけたので読むのをやめた。

まとめ

1年がunratedで終わりunratedで始まるのはどうなんだAtCoder。
別に文句を言いたい気持ちは全然なくて、イメージ悪くない？大丈夫？という感じ。

明日明後日と3日連続でrated(予定)のコンテストがあるので参加したいのだが、いまいちモチベーションが上がらない。
ブログの移行が進んでいないのが大きい。
詰まった部分は大体解決していて、単純にやっていないからなので頑張ろう。

保存しましたで消えるの本当に頭おかしいから早く移行したい。
・・・本当に頑張ろう。

2019年→2020年

あけましておめでとうございます。

年明けてから年末のコンテスト参加記事をいくつか書いたけど改めて。
とりあえずAtCoderの記録を乗せる。
去年はyukicoderも張ったが、今年はAtCoderがメインで、AOJとyukicoderはライブラリの確認とかでしか解いていないのでAtCoderだけ。

～2020/1/10

やってる時期とやってない時期が激しすぎる。
2週間に1日だけとかが何回かあるのがあんまりやってないなーって感じする。
趣味は他にもいくつかあるからずっとやるのは難しいが、もうちょっと継続的にやりたいね。

今年の目標は黄か橙。
青は(やれば)いけると思うので、その先が大事。

この記事はまた更新するかも。

ABC149

問題

unrated

4完
初めて参加したコンテストがunratedになった。
出来はひどかったので助かった。

A問題

かんたん。

B問題

問題文読み間違えた。
問題文のGreedy Takahashiからして、高橋くんは自分も青木くんもクッキーを持ってる場合、青木くんのクッキーから食べにかかると思って実装してしまった。
普段BくらいまではACを見ずに次の問題に取り掛かるのだが、今回はCを提出した後に20/20の表示でまだジャッジ中だった。
遅くない？？？と思いつつもDに取り掛かり、途中でBがWAしてるのを確認。
問題の読み間違いに気づき、再度提出してDに取り掛かる。
しかしBだからと高をくくって詰めが甘くてまたWA。
今度はDを解いた後に気づいた。
最終的にACDBという珍しいAC順になった。
毎回毎回あほらしいミスを繰り返しているが、簡単なBで何度もやらかしてしまったのは反省点高い。

C問題

かんたん。
エラトステネスの篩張ったら終わった。

D問題

最近のDにしては複雑な問題だなーという感想。
K個前の値を保存してDPすれば良さそう・・・と思ったのだが、どう頑張ってもK個前の値だけじゃ遷移を進められない。
「K個前の値」じゃなくて「K個前までの全ての値」を保存しないといけないという考えから抜け出せなかった。
あるところでK個毎に独立してるのでは？と気付き、modKで分けてDPの方針が立った。
この時点で結構時間が立っており、これ以上ミスを重ねたくないとかなり安定志向の実装にしたつもりだが、modK毎のインデックスがすんなりいかずデバッグにかなり時間を取られた。

最初は出す手を数字と連想配列でうまく関連付けてシンプルな条件式にしようとしていたのだが、安定志向で条件式が長くなってしまった。
今回はミスしなかったが、長いとミスも増えるしどっちが良いのか悩みどころ。
うまく関連付ける内容は、詳しい部分は忘れてしまった。
もう去年の話だぞ。
記事書いてるのは徹夜明けの早朝6時過ぎだぞ。

最終的にACしたのが73分。
時間かかりすぎ。

聞くところによるとDPなんかしなくても貪欲で良いらしい。
ちょっと考えてみればすぐわかる話だ。
とりあえず勝てるなら勝てる手を出せば、他の順番と比べて同じ点数になることはあっても悪くなることはない。
最善が複数ある場合に貪欲で解けるっていうの慣れないとなと感じた。
これゲーム問題の分野かな。
ゲーム問題も解かないとなぁ。

E問題

去年の話なのでもうあまり覚えていない。

去年の話とかいう便利な言葉。

とりあえず覚えているのが、AGC 020 Cを思い出したこと。
解いていないのだが、解説をちらっと読んだ覚えがあった。
全ての組み合わせの中から、大きい方からM個を考える時、必ず満たす性質がないかというのをずっと考えていた。
しかしうまくいかずにタイムアップ。

解説PDFをちらっと見て理解した解法が、ある値を決め打つ二分探索を基本として、その二分探索の途中でさらに二分探索をする方法。
2回目の二分探索がPDFで言う「左手で握手する人を先に決めたとき、右手で握手できる人が何人いるかは累積和を用いることでO(1)で求まる」という部分で、最初この部分が理解できなかったので、方針だけ理解して二重に二分探索すればできそうだなと考えた。
制約的にはO(Nlog^2N)でも間に合いそうだが、部分問題として考えるとO(logN)からO(1)は結構大きいので、この累積和の部分を頑張って考えた。
理解はできたのだが、PDFはもうちょっと詳しく書いてほしいなー。

累積和といえば累積和だが、「V[i] = 数列中のi以上の数」と見れば良いだけで、インデックスとして考えるのではなくて値として考えるというちょっと変わった累積和だ。
だから数列中の値の最大値も重要になってくる。

こういう添字に意味を持たせるタイプの問題ずっと苦手だなぁ。
記事に書いた記憶があるが、BITの添字に意味を持たせるタイプの問題で、「こういうデータの持ち方するという発想に至るのきついなぁ。考えられるようになれるかなぁ。」といったことを書いた記憶があるのだが、やはりきつい。
次はこういう発想も道具として取り出せるようにしておきたい。

F問題

なんかむずかしそー。
完。
まぁunratedだし？という気持ちが溢れてた。

まとめ

2019年最後がunrated！
まぁ助かった。

このコンテストは自分の苦手ポイントを自覚させてくれて得られるものが大きかったように思う。
ミスをするなというのは言わずもがな。
・modKで考える発想。
・必ずしも最善は一択ではなく、そのうちの1つが分かれば良いという発想。
・累積和やBIT等、配列的なデータ構造のインデックスに意味を持たせる発想。
この3つが足りないと感じた。
modKは最近の問題でも理解に時間がかかったばかりだ。
値を決め撃って二分探索する発想はかなり浮かぶようになってきたので、この感覚を参考にこれらの発想も定着させていきたいね。

今日は2020年初のコンテスト。
参加するなら新年初C++コーディングになる。
年末年始全くやっていないので心配だなー。

AGC041

あけましておめでとうございます。
新年初記事。
年末に記事を書きたかったけど時間がなかったのでまずは2日連続のコンテスト参加記事から。

問題

順位: 1193

パフォーマンス: 1256

新レーティング: 1075

差分: -27

1完。
初めてAGCに参加したが、さすがに難しかった。
目覚めたらコンテスト開始してて、なんとか頑張って9:10過ぎから活動開始した。
結果論だが、Aは一瞬で解けて終わりなので最初から参加していればもっとパフォーマンス出てそう。
寝起きによる自身のパフォーマンスも含めて。

A問題

直近のABC148 Fとすごい似てるなーという第一印象。
偶奇があっていれば2人とも全て勝ち続ければ出会う。
偶奇を合わせるためにはどちらかが同じ場所に留まる必要があり、端でしか留まることができないので、端に近い人が端に行って1回留まれば良さそう。
普通にAC。
考察から実装まで5分ちょっと。
寝坊のせいで20分になってしまった。

B問題

この問題を2時間近く考えて結局解けなかった。
解析的に解け・・・ない。
二分探索でき・・・ない。(！)
二分探索に使うような関数で全問題に対して可能かどうか走査・・・いけそう？
というような流れで、計算量抑えつつなんとか実装できないか色々してたら解けなかった。
二分探索の発想に至るのにおそらく1時間以上かかったのはまだしも、そこからダメの判断を下したのは非常にbad。
単調増加であるという判断ができなかった。
PやVの値によって場合分けしていたのだが、場合分けしていることが問題を必要以上に複雑にしてしまった。

よく考えてみると、ある問題Xが可能であるとすると、問題Xよりスコアが大きい問題Yと問題Xの選び方を入れ替えると、Yを選ぶことが可能となる。
ただそれだけなのに、何点入れればある問題を選ぶことが可能で、残りの点数はどのように振り分ければ他の問題がある点数以内に収まるか、ある点数以内に収まるようにすると点数が余る場合はどのようにすれば良いか。
こんなことを考えていた。
ある問題を選ぶことが可能であるかどうか知りたいだけなので、M人全員が1点ずつ選ぶとして良い。
それに気付けなかったのが敗因。

C問題

ややこC。
問題文とドミノの配置を理解するのに相当時間がかかった。
偶数(偶数は色々便利そうと考えた)で一番小さい4×4について手作業で考えてみようと思ったが、それすらちょっと考えただけでは分からなかったので、その先は無理だろうということでBに専念。
ただ実際には、苦労してでも4×4を実装することが本筋だった。
マス目が小さい値でクオリティが同じものを構成すれば、後はそれらを組み合わせて対角線上に配置すれば、全ての行列でクオリティを保ったままになる・・・なるほど。
2の場合は不可能、3の場合はクオリティ1を作成でき、4, 5, 6, 7の場合はクオリティ1は作成できないが、クオリティ3のものを作成でき、4, 5, 6, 7があれば8以上は全て作成できるのでこれで考える必要のある構成は全て。

相当パズル要素強い。
競プロの大部分を占めるであろう数学系とかシミュレーション系しか解いたことがないので、こういった問題は面白いと感じるが、さすがに引き出しがなさすぎるからその方向に考えを移行できない。
もっと余裕持って問題解きたいね

D問題以降

見てまーーーーーせん。
ABCなら解けなくてもコンテスト終了後に解説見て云々あるのだが、解説すら見ていない。
ちょっとレベルが違いそうで解くのはいつになるやら。

まとめ

初めてのAGCだが、一応レートは上がったので変な苦手意識を持たずに済んだ。
B問題はdiff水色だし解けても良かったなー。

また原因を寝坊に求めることもできるが、そもそも最近まともに頭働いていない状態からコンテストに参加することが多くて反省している。
起きてから本稼働開始までに3,4時間かかる人間なので、本来ならもっと早く起きておくべきなのだが、年末だしねということでひとつ。

年内目標だったブログの移行はまだ少しかかりそう。
水色もブログの移行も年内無理だったかぁ。

ABC148 参加

問題

順位: 1671

パフォーマンス: 1053

新レーティング: 1048

差分: -2

5完
5完なのにレート下がるなんてそんな・・・。
全体的に簡単が過ぎる・・・。
E問題もうちょっと早く解けても良かったのと、F問題の考察進める速度が遅すぎた。
生活習慣ゴミだったので、ほぼ徹夜明け+テレビ見ながらと、コンディションはなかなかに悪かったのが言い訳になりそう。
M-1見たかったからね。

A問題

かんたん。
実装楽にするためにどうしようかちょっと考えた。
ハッシュ化すれば簡単そう、いやハッシュ化できるならそのままでも・・・、という流れで6-A-Bじゃんとなった。

B問題

かんたん。
B問題でこんなに簡単なの久しぶり？

C問題

かんたん。
C問題でこんなに簡単なの初めて？
前回のbit全探索見習って。
最小公倍数のライブラリ作ってて良かった。

D問題

貪欲でいけそうと比較的すぐ気付いたものの、実装で手間取った。
素直にforの中でif使えば良いものの、連続要素数える時と似てるな、ということでwhileなんて使うから1WA+タイムロスを生んでしまった。
15分かかってしまったが、5分で解けても良かった。

E問題

なんだこの数列は・・・。
制約すごいからLogかけられそうということで行列累乗を試してみる。
式は作れたものの、変数が出てきてしまってうまく繰り返し二乗が使える形に持っていけない。

最初のいくつかをシミュレートして数式辞典で調べてみるとそれ知ってるよーと教えてくれた！
二重階乗というらしい。
なんならn!!とか記号までついてる。
名前も記号も初めて見たんだが？
一般項もあったが、どう頑張っても誤差出ますよーって見た目してる。
それに多倍長でも無理だろって桁になりそう。

諦めて0が何個続くかに重点を置いて考察していくと、10作るなら2×5しかないと気づく。
・・・これどこかでやらなかった？？？
2は山程あるから5だけ数えれば良いってすごいどこかでやった考え方。
どこでやったのか全然思い出せなかったし、今も分かってない。
とりあえず方針は立ったが5の数え方はすぐに出てこなかったので、いくつか書いてみたら5^nごとに1回ずつ出てくるというのが分かった。

その通り実装するも、ここで恒例の凡ミス。
forの更新式でi*=5で5^nを計算していきたかったのだが、i*=iとしてしまって答えが合わない。
考察25分+凡ミス10分で35分くらいかかった。

F問題

ここまで57分。
時間は余裕というわけではないが、なんか解けそうな雰囲気。解けなかった。
考察が全然進まなかったが、コンテストの時間内では最終的に、「u, v間の最短経路を通って高橋くんが青木くんにギリギリまで近づき(近づいた後の頂点をaとする)、その近づいた際に通ったルートの各点から(各点をbとする)、青木くんのいない方にできるだけ頂点がある道に進み、その頂点数+aとbの距離が逃げられる最長距離。偶奇によって±1がありそう。」という考えになった。
考察にかなり時間がかかった上、実装も結構ややこしかったのでタイムアップ。
実装に取り掛かったのは30分後くらいだと思うが、考察も続けながらなので厳しかった。
さすがにまだDFS2回はスラスラ書けないねー。

方針はあってそうなんだけどなーと思っていたので、コンテスト終了後も自力で解き続けてみた。
実装を進めていくと、近づいた際の各点bからのルートは、近づいた最終の頂点aからのルートに含まれていることに気付いた。
つまり、「u, v間の最短経路を通って高橋くんが青木くんにギリギリまで近づき、近づいた後の頂点から青木くんのいない方にできるだけ頂点がある道に進み、その頂点数が最長距離。偶奇によって±1がありそう。」とかなり実装が簡単になった。
順調に実装を進めて提出するとWA。
よく考えると偶奇の処理が正確でなかったので直してAC。
コンテスト終了後の所要時間は15分くらい。
解説見ずにF通せたのは初めてかもしれない。
diff水色だけど。

まとめ

E問題diff茶色ってマジ？おかしくない？
バッドコンディションが脳死行列累乗に繋がって、それに時間かけたのはかなり悪手だった。
とは言え茶色に時間かかるのは苦手問題ってことなのかなぁ。
それよりは単純にFの考察をもっと短く正確にというのが本筋か。

-2とは言えレート下がってしまったので、年内水色難しそう。
しかもブログの移行関連で面白そうなものを見つけてしまい、そればかりで全く問題を説いていない。
今日はAGC明日はABCと一応出るが、今日の初AGCがどうなるかで決まる感じがある。
AGCは過去問すら1問も解いていないので不安しかない。
なんとか頑張っていきたいところ。

ブログのシンタックスハイライトは直ったみたい。
やっぱり悪いのは忍者ブログだった！
直ったからブログの移行はまぁいいやとしても良いのだが、前述の通り面白そうなのを見つけて結構時間をかけているから移行はする。
色々考えた結果デザインが1から自分でになったのがつらすぎる。
こっちも年内目標。

ABC147 F Sum Difference

問題

ACコード
ACコード(区間をsetで管理)　2019/12/17追記

通常

#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) begin(x), end(x)
#define debug(x) cout << #x " => " << (x) << endl
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
#endif
using lint = long long;
constexpr int MOD = (int)1e9 + 7;
constexpr double EPS = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

int main(void) {
  lint n, x, d;
  cin >> n >> x >> d;
  if (d == 0) {
    if (x == 0) {
      cout << 1 << endl;
    } else {
      cout << n + 1 << endl;
    }
    return 0;
  }
  // ?
  if (d < 0) {
    x = -x;
    d = -d;
  }
  unordered_map<int, vector<pair<lint, lint>>> now;
  for (lint A = 0; A <= n; ++A) {
    // S = Ax + Bd
    lint Bmin = (A - 1) * A / 2, Bmax = (2 * n - A - 1) * A / 2;
    lint Adiv = A * x / d, Smod = A * x % d;
    if (Smod < 0) {
      Smod += abs(d);
      // ?
      ++Adiv;
    }
    now[Smod].push_back({Adiv + Bmin, Adiv + Bmax});
  }
  lint cnt = 0;
  allrep (m, now) {
    sort(all(m.second));
    lint now = LLONG_MIN;
    allrep (p, m.second) {
      lint l = max(now, p.first), r = max(now, p.second + 1);
      cnt += r - l;
      now  = r;
    }
  }
  cout << cnt << endl;
  return 0;
}

区間をsetで管理

#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) begin(x), end(x)
#define debug(x) cout << #x " => " << (x) << endl
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
#endif
using lint = long long;
constexpr int MOD = (int)1e9 + 7;
constexpr double EPS = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

template <bool merge_adjacent>
class SectionUnion {
  struct comp { bool operator()(const pair<long long, long long> &a, const pair<long long, long long> &b) const { return a.second < b.second; } };

  public:
  set<pair<long long, long long>, comp> section_set;
  SectionUnion(void) {}
  bool insert(long long l, long long r) {
    auto litr = section_set.lower_bound({0, l - merge_adjacent}), ritr = section_set.lower_bound({0, r});
    if (ritr != section_set.end() && r + merge_adjacent >= ritr->first) ++ritr;
    const bool exist = litr != ritr;
    if (exist) {
      l = min(l, litr->first), r = max(r, prev(ritr)->second);
      section_set.erase(litr, ritr);
    }
    section_set.insert({l, r});
    return exist;
  }
  bool remove(long long l, long long r, bool involve = false) {
    auto litr = section_set.lower_bound({0, l}), ritr = section_set.lower_bound({0, r});
    if (ritr != section_set.end() && r >= ritr->first) ++ritr;
    const bool exist = litr != ritr;
    if (exist) {
      long long ledge = litr->first, redge = prev(ritr)->second;
      section_set.erase(litr, ritr);
      if (!involve) {
        if (ledge < l) section_set.insert({ledge, l - 1});
        if (r < redge) section_set.insert({r + 1, redge});
      }
    }
    return exist;
  }
  bool same(long long a, long long b) const {
    if (b < a) swap(a, b);
    auto itr = section_set.lower_bound({0, b});
    return itr != section_set.end() && itr->first <= a;
  }
  pair<bool, pair<long long, long long>> get(long long x) const {
    auto itr = section_set.lower_bound({0, x});
    return {!(itr == section_set.end() && x < itr->first), *itr};
  }
  void clear(void) { section_set.clear(); }
  bool empty(void) const { return section_set.empty(); }
  int  size(void) const { return section_set.size(); }
};

int main(void) {
  lint n, x, d;
  cin >> n >> x >> d;
  if (d == 0) {
    if (x == 0) {
      cout << 1 << endl;
    } else {
      cout << n + 1 << endl;
    }
    return 0;
  }
  if (d < 0) {
    x = -x;
    d = -d;
  }
  unordered_map<int, SectionUnion<true>> now;
  for (lint A = 0; A <= n; ++A) {
    // S = Ax + Bd
    lint Bmin = (A - 1) * A / 2, Bmax = (2 * n - A - 1) * A / 2;
    lint Adiv = A * x / d, Smod = A * x % d;
    if (Smod < 0) {
      Smod += abs(d);
      ++Adiv;
    }
    now[Smod].insert(Adiv + Bmin, Adiv + Bmax);
  }
  lint cnt = 0;
  allrep (m, now) {
    allrep (p, m.second.section_set) cnt += p.second - p.first + 1;
  }
  cout << cnt << endl;
  return 0;
}

練習で解く問題が4問の旧ABCばかりなので最近記事を書くほど詰まる問題がなかった。
久々に骨がある問題を解いた。
AtCoder Problemsでも黄上位くらいになっているし、青はかなり手の届く問題になってきたかな。

本番では取り組む時間がなかったので、まっさらな状態からスタート。
こういうシンプルな問題は解き慣れていないので何から手をつけて良いのか全く分からなかった。
解説を読んで方針だけなんとか把握できた。
基礎をしっかりしてないと解けない感じで、こういう問題をしっかり練習するのは大事っぽい。
イメージとしては、簡単なE問題レベルが4つか5つくらい重なった感じ。
自分の簡単なE問題の正解率を70~80%とすると、5つ重なったら正解率20%もないんだが！？となる。

考察

まず重要なのが、Tを考えずにSだけを考えれば良いという置き換え。
Sを決めればTも決まるのでなるほど当然だが、しっかり意識しないと両方考えちゃいそう。
両方考えても解けるのだろうが、やっぱり簡単な方が良いね。
実際Sだけ考えれば良いと分かった段階でかなり先が開けた気がする。

Sについて考えると決めれば、次に行き着くのは選ぶ個数Aを0~Nで固定してループする。
何度も見た解き方なのでこれは問題なく辿り着けるだろうと思う。
次の悩みどころが、個数を固定した上で何通りの選び方があって、他の個数との被りがないか。
これをチェックする必要がある。

まず、何通りの選び方があるかを考える。
ここで生きるのが、各iにおける値を数式で表現する書き方。
ただ単に等差数列という認識ではなく、「X, X+D, X+2D, ..., X+(N-1)D」と捉えることで、A個を選んだ際の合計がAX+BDという形で表現できる。
Bの最低値Bminは、0から1ずつ増やしたA個の合計なので、(0+A-1)*A/2。
Bの最大値Bmaxは、(N-1)から1ずつ減らしたA個の合計なので、{(N-1)+(N-1-A+1)}*A/2 = (2N-A-1)*A/2。
Dの係数は1刻みなので、Bmin~Bmaxまでの間を1刻みで(Bmax-Bmin+1)個の値を作れる(+1は開区間なので)。

AXについては、ループ内ではAを固定しているためAXの値も同じく固定となる。
このことから、Aを固定すると(Bmax-Bmin+1)個の値を作れることになる。

このままでは、他のAを選択した場合の値との被りを考慮していない。
これからがおそらくこの問題の本質なのかな。
解説PDFの、modD毎に考えれば良いという記述、雑ぅ・・・。
理解すれば確かにmodD毎に考えれば良いのだが。
modD毎に考えると、複数の区間を結合して、区間の合計を求めるような問題になる。
集合として考えると、まさしく和集合という感じ。
かなり典型チックな雰囲気を醸し出しているが、懇切丁寧に解説しているような記事はなかった。

modDを理解する部分で大事なのが、AX+BminD~AX+Bmaxを、Bが1刻みになっていると見るのではなく、式全体としてみるとD刻みになっていると捉えること。
つまり、AX+BminD~AX+Bmaxの間でmodDの値は変化せず、その値はAXのみで決まる。
これを式に表すと、AX+BD = (AX/D+B)D+AX%Dとなる(AX/Dは切り捨て)。
この式を見ると、AX%D毎に独立して(AX/D+B)を考えれば被りを防げることが分かるので、(AX/D+B)をBmin~Bmaxの区間を被らないように数える和集合の問題になった。

フレンズのアライグマさんの画像がすっごく分かりやすくて理解をかなり助けてくれた。
アライグマさんの解説

これでほぼ終わりなのだが、ここまで来てこの区間の和集合が難しい。
setで管理すれば簡単だけど計算量的にどうなのって話になる。
問題の設定から、必ず区間は正の方向に被るとか、区間を覆ってしまうような区間は存在しないとか、色々考えたが、そういう細かい部分まで考える必要はなかった。
区間を順に考えるのではなく、一度全ての区間を列挙した後で、区間の最小値(最大値でも良い)でソートする。
そうすれば、問題の設定に関係なく、区間の最小値は必ず逆行することがないという保証が得られる。
後は、現在どこまで区間を選んでいるかを保存しながら走査していけば被りなく区間を数えられる。
やったー解けた！
d=0の場合と、d=0かつx=0の場合は、全然話が変わってくるから注意しよね。

実装

まずmodDに騙された話。
modって巨大な数を扱えないからmod取ったよー＾＾とする場合が多いので、疑いなく二次元配列の要素数としてDの絶対値を取ったのだが、Dの制約が10^8。
僕は学んでいる、二次元配列でその要素数はダメだと。
全体でN+1回しかpush_backされないので、vectorを連想配列に入れれば解決。

modの話はもう1つあって、負の数のmodがなかなか曲者。
C++ではa%b=cとすると、a負ならbに関係なくcは負の数か0になる。たぶん。
正の数にしたかったら、cが負ならbを足せば良いだけなのだが、同時にa/b=dも使う場合は、±1しないと(bの正負によって符号が変わる)、b*d+c=aを満たせなくなってしまう。
符号変わるしcが負でも0だと±1しなくて良いしで面倒臭い。
これを考慮して、dを正に固定してdにプラス1するような実装にしてみたのだが(?コメントの部分)、この+1の部分がなくてもACしてしまう。

なぜ通るかいまいち分かっていなかったのだが、記事を書きながら気付いた。
Xが負ならAX%Dも全て負の数か0になるので、modDが0以外の場合は全てにおいて-1されている状態であり、何通りかという問題に対しては影響を与えず正しい答えが出ているっぽい。
本当は違うんだけどこれでも良いよみたいなのはなぜ通るのか理解しないとすごくもやもやするので、自分なりに解き明かせてよかった。

次はそんなに悩んでないが、やっぱり半開区間便利だねの話。
数列Zi(0<=i<N)のうち今Znowまで見ていて、次の区間(Zmin, Zmax)が得られた時に区間の合計を更新しながらZnowを更新してねとなった時、開区間だと結構ややこしい。
Znow=Z0でZ3~Z9が得られた時、区間の合計に+(9-3)+1する。
しかし、Znow=Z5でZ3~Z9が得られた時は、区間の合計に+(9-5)となり、Z5は既に合計に入っているので+1してはいけない。
Znowの更新はZnow=max(Znow, Z9)で良いのだが、区間の合計は単純なmax関数では計算できず、場合分けが増えるのでミスしやすくなってしまう。

ここで半開区間を使う。
Znow=Z0でZ3~Z9が得られた時、区間の合計は+(9+1)-3。
Znow=Z5でZ3~Z9が得られた時、区間の合計は+(9+1)-5。
Znowの値に関わらず同じ計算式なので、+(max(Znow, Zmin)+1)-max(Znow, Zmin)で良い。
Znowの計算式もZnow=max(Znow, Zmax)で簡単。
半開区間すげー。

最後によくやるミスだが、intの範囲外になる部分をrepのint型の変数のまま計算してしまい、値が大きいケースにWAが連なってた。
最後に直したのがこの部分なのだが、ここまでWA出るとなると考察から間違ってるのかと不安になる。
気付けば、あーここかーという感じ。
long longとして扱いたい部分はしっかりlong longにしていたのだが、計算式の途中でオーバーフローする部分をいつも忘れてしまう。
気をつけよう。

2019/12/17追記
区間をsetで管理するテクなるものがあるようで、典型チックと思った区間の管理部分をまさにやってくれてすごい。
一番悩んだ部分がとっても簡単に書けた。
satanicさんの実装を参考にしたつもりが、ほとんど別物になってしまった。

競プロで基底クラスのポインタに入れるなんて頭のおかしいことはしないはずなので、本当はsetをpublic継承したかった。
しかし書いているうちに区間の左端より右端で比較した方が良くないかという流れになり、pair(左端, 右端)を保ったまま格納するなら通常のsetだといけないということで、比較関数を色々弄っていくうちにスマートに書けないと判断してこの形に。
正直mapの方が理にかなっているのだが、map[右端] = 左端の形は扱いづらすぎる。
クラス内部のprivateなデータならともかく、map自体も外で使う可能性が十分ある中これはちょっと・・・となる。
ま、まぁSTLをpublic継承なんて邪道だし？これで良いよね？

まとめ

自分用メモだしなんでも良いかと見出しとかつけずに改行だけで乗り切る姿勢でいたのだが、あまりに見づらい・・・。
考察と実装とまとめくらいなら頑張れる気がするので、しばらくこのスタイルで行こうかな。
最近ブログレイアウトも変えた(元々横に広いのが良かったが見つけられなかった)のだが、コードのシンタックスハイライトの表示が崩れているっぽい。なぜ。
改行も自動で消えるの毎回意味分かんないし忍者ブログが悪い気がしてならない。
コード部分くらいは直したい。

pairをハッシュ化してunordered_map等に入れる

ABC146 D Coloring Edges on Treeより

2つの値をkeyにして値を取り出したいことは割と多い。

mapで計算量が間に合うならそれでも良いが、想定解法とは違うがC++パワーでunordered_mapを使えば間に合うなんてことがあるかもしれない。

そのためにpairのハッシュ関数を作成した。

namespace std {
template  struct hash<pair<A, B>> {
  size_t operator()(const pair<A, B> &p) const {
    const static size_t rand_seed = random_device()() + 0x9e3779b9;
    size_t seed = rand_seed;
    seed ^= hash()(p.first) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    seed ^= hash()(p.second) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    return seed;
  }
};
}

64bit環境ならsize_tも64bitのはずなので、int型2つ並べるだけで衝突は起きないはずだが、より汎用的にするためにboost::hash_combineを真似た。

テンプレートの特殊化の本来の目的に沿うとpair<int, int>を別に指定するべきなのだろうが、普通に面倒である。

このハッシュ関数をテンプレート入りさせようかなと考えているし、32bit環境のオンラインジャッジもあるかもしれないので、汎用性 is 正義である。

速度的にもintを2つ並べる場合とほとんど変わらない。

数回程度の試行だが、5ms程度しか違いがなく、ハッシュが衝突したのかジャッジシステムの誤差なのか分からないレベルなので問題なく動作しているだろう。(ABC146 D Coloring Edges on Treeで測定)

一応動くようにはなったのだが、方向性を参考にした記事と見比べてみると乱数の使い方が違う。

参考にした記事では、初期seedを0とし、pair要素のhash値と同様にseedをシフトしたものと足し合わせている。

pairの値によって定まる部分を定数とおくと、こちらはseedをシフトして足し合わせる回数が少ないのと、足し合わせる順番が最初になっただけなので、記事の方法でランダム性が確保されるなら初期値を乱数にするだけでも良さそうな気がするのだが、正直全く分からない。

偉い人に教えてもらいたい。

メモリによる配列の最大要素数の制限

ABC146 D Coloring Edges on Treeより

配列の最大要素数は気をつけよう。

int型は4byte。

AtCoderのメモリ制限は多くの場合1024MB。

配列に入れられるint型の数は1024*10^6 / 4 = 256*10^6 ≒ 2*10^8個。

int[N][N]を取りたい場合、N=10^4はOKだけどN=10^5だったらだめ！

long longでもN=10^4までいけるが、他の配列などでこれ以上大きなメモリ確保が難しそう。

単純計算だとこうなるが、vectorは余分にメモリ取るので、最大でこれの半分以下の要素数しか取れない。

通常配列は知らないが、vectorより大きくなることはないのでvector基準で考えておけば良い。

vector<int> v[N][N]

N=10^4まで。

vector<long long> v[N][N]

N=10^3まで。

ABC147　参加

ABC147

順位: 785

パフォーマンス: 1446

新レーティング: 1050

差分: +73

4完
ご飯を食べながらちょっとゆっくり参加。
Cが難しいというかややこしかった。
Eは途中で頭おかしくならなかったらかなりワンチャンあった。

A問題

かんたん。
bustってブラックジャックで普通に使うのかな？

B問題

反転した文字列用意したら分かりやすくなるというテクニック。
別にいらなかったね・・・。

C問題

ややこC。
制約がbit全探索だけど貪欲的にも解けそう・・・？
でもbit全探索の方が確実だからそっちで。
C問題でbit全探索なんか使うか？とかなり訝しんだが、bit全探索なら解けるという絶対的な自信があった。
Cにしては相当に実装が重かったのも訝しみポイント。
直近で解いたABC112 C Pyramidを思い出した。

正直者を決めた場合、正直者が正直者と示した人のみを確認すれば良いと思ったのだが、サンプルが合わない。
そうじゃなくて、正直者が正直者と示した人がさらに正直者を示して、と繰り返す必要があった。
それを実装しようとしてキューに正直者入れるかと考えたところでbit全探索じゃなくなった。
bitが指し示す正直者を使おうということでbit全探索に戻ってきた。危ない危ない。

この実装でミスしてしまったのが、bitが立っているかどうかと正直者かどうかの一致判定。
普段bitのi桁目のビットが立っているかどうかを調べる際、if(bit & (1 << i桁目))と書くのだが、これはifの条件式が0以外をtrue(=1)にキャストすることを踏まえており、i桁目のビットが立っていた場合に取り出される値は(1 << i桁目)である。
これをそのままif(0or1 == (bit & (1 << i桁目)))としてしまったため、1桁目のビットが立っていても(1 == 2)の比較が行われてfalseになってしまう。
1にキャストされるから普段の書き方で良いというのは間違いなく頭に入っていたのだが、ふとしたところでミスる。
これからはif((bit >> i桁目) & 1)の書き方に統一します・・・。

もう1つ書きたいことが、ビットの数え方のお話。
実は競プロをやってみようかなと思い立ったきっかけがビット関連の演算。
ビットを立てたり消したりMSBとか立っているビットの数え方とかすごい鮮やかだなぁと。
別に競プロでしかビット使わないわけではないが、意識するのは組み込み系か競プロだろう。
立っているビットを数える関数は2年くらい前に作っていて、たぶんそれ以来初めて使った。
分割統治でO(log64)なのでほぼO(1)の実装。
他のビットを数える系も大体分割統治でO(log64)でできるのだが、LSBはde bruijn sequenceとかいう闇の数字を使って真にO(1)で計算できることを最近知った。
O(N)のRMQに使っている。
立っているビットを数えるのも真にO(1)でできたら良いなぁ。

D問題

ここまで50分。
相当きついと思いながらのD。
C解いてる途中に質問タブが(1)となっているのに気づき、見てみると「Xor Sum 4」の文字が。
EかFかなーうわー・・・、と思っていたのにD問題開いたらまさかの。

見た感じ桁毎に分けられそうだしXor Sumだし、ということで桁ごとに分けて考える。
どのAiも使われるのはN-1個なので、Aiを固定した際の合計を計算できれば良し。
Aiのd桁目が1なら他のAi以外のd桁目が0のときにその桁が1、逆も然りと、普通にカウントしたら良いのでは？
Xor Sumにしては簡単だけどなぁと思いながら実装するも普通にサンプル通ってAC。
Cの遅れを少し取り戻せた。

E問題

ここまで63分。
単純そうで難しそうだという第一印象。
色々考察して、80×80のサイズと、ABも80までなのでその差も80までというのが鍵っぽい。
差が80以内を使うということは、差の合計を0にするように足していく場合、差の合計の最大値は80×2くらいまでに収まることが保証できたりする？
とりあえずDP使って解けそうだなぁ。

ここまでかなり良い感じの考察だったのに、ここで頭がおかしくなる。
こういう右か上かしか行けないABC145 D Knightでやったなぁ。
確か全通りは、と思い出すより早いと解説PDFを見に行く。
[右と上を選ぶ回数の合計]C[右を選ぶ回数]の簡単な組み合わせだ！
つまり160C80 = 160*159/2 = 12720だ！

？
ちょっと頭に思い浮かべたのが3×3のマスで4C2 = 4*3/(1*2)となり、なぜかそのノリのまま計算してしまった。
そこから全通り調べて最小値調べれば良いかなぁと。
この時点で頭おかしくなってるので次もおかしい。
最大80だし(?)、通った|Ai-Bi|を大きい順にソートして、合計が正ならマイナス、負ならプラスで合計して行けば必ず最小値になるのでは！？
そんなわけない、貴様ナップサック問題知らずか。
で実装して間に合わなくて、コンテスト終了20分後くらいにそのままの方針でTLE出して終わり。
5,5,4,3,3とかの場合、5+5-4-4-3=0にできるが、上から順にプラスマイナスの方針だと5-5+4-3-3=-2になってしまう。
ということで色々だめ。

良さそうな解法は、最初の考察を進めて、差は80以内になるなら全部プラスで計算しても80*160=12800になるので、DP[x座標][y座標][現在までで作れる合計値]でDPしていく。
80*80*12800=81920000 < 10^8でたぶん間に合う。
あんまり解説読んでないけどたぶんこれで行けると思うので、後で改めて解いてみる。
実際全部プラスなんてことはないので、間に合わなければ少し節約できそうか？

F問題

Eと一緒に問題を眺めて、シンプルな問題で解けそうな解け無さそうなわからなかったので、順位表見たら圧倒的に難しそうだったのでパス。
シンプルな問題は簡単かやべーか二択だな。

まとめ

Cで時間溶かしたのは反省だが、間違いなく今回のCは難しかった。
Eは解けても良かった。
今までの解けても良かったよりかなり強めの解けても良かった。
全通り調べても良いなんて意味分からないことを考えなければ、次に進めるのは最初の考察の続きなので、80*160しても制限に収まると気づく可能性は十分あっただろう。

レートは順調に伸びてるものの、次も4完なら水色は厳しそう。
年内はAGCが1回予定としてあるが、ABCはもうないのかな。
AGCも参加する予定だが、できれば後1回ABCで余裕持たせてほしい。