2019-07-13

CPSCO2019 Session2 F - Treasure Collector (700)

リンク
F - Treasure Collector
ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー
問題文は長いので割愛

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー
個人的に見た目は区間dp、ギリ4乗通る気がするので(通らないかも)
まあ違っていて。

結論を言うと"燃やす埋める"をします。

そもそもフローを知らない人はFord FulkersonかDinicのライブラリを作ろう。
これとかを解くと良さそう。
https://atcoder.jp/contests/abc010/tasks/abc010_4

”燃やす埋める”を知らない人はググろう。たくさん記事が出てくるので。

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー
以下、フローと燃やす埋めるは知識としてある前提で。

まず頂点の持ち方。
この問題で2状態のどちらかを選ぶようなものは何か？
そもそも2状態とは？

結論としては頂点は $N × N$ の全てのマス。
すべてのコインはx方向あるいはy方向のどちらかで回収される、これが2状態になる。

絵を描いてみると分かることだが、コイン目線でx方向あるいはy方向を決めると回収してくれるロボットは一意に決まる。
直感的には4通りありそうだけど制約的にそうならない。
言われるとまあ自明かも。

次に辺の張り方。

１．まず禁止するための辺を張る。
これは簡単。
例えばあるコインをx方向で回収してもらうとしたときに、ロボットのいるマスまでの間にy方向を選ぶコインがあってはならない。
なので
ある頂点を決めたときに、ロボットから遠い側の頂点が向かってくる方向に対して垂直に動くようなパターンは許されない。
これを満たすようにコストが無限大の辺を張っていく。

２．コストの辺について。
全マスにコスト $1$ の辺を張ると終わりになってしまう。
ここが難しい。
$i$ 行目におけるx方向のコストを愚直に考えると(ロボットとの距離) $/A_i$ となる。

$i$ 行目におけるx方向のコストは
.. 6 5 5 5 4 4 4 3 3 3 2 2 2 1 1 1 r 1 1 1 2 2 2 3 3 3 ...
$A_i = 3$ のときこんな感じ。rはロボットのいる点。

これに合わせて辺を張るとそれはそれでコスト過多。重複があるので。
ここで見方を変えると、同じコストの頂点について一度コストを払うとどこまでも進めると言い直すことができる。

$i$ 行目におけるx方向のコストは
.. 6 0 0 5 0 0 4 0 0 3 0 0 2 0 0 1 r 1 0 0 2 0 0 3 0 0 ...
$A_i = 3$ のときこんな感じ。rはロボットのいる点。

これでかなりマシになった。でもまだ重複がある。
よく考えると、例えばコスト $6$ の点を使うときロボットに対して同じ側のコスト $1$ の頂点は必ず使われているはずである。
またこれはグラフ上でも先に作った禁止辺によって達成されている。
なのでコストを累積する必要はなく全て $1$ でよい。その結果

$i$ 行目におけるx方向のコストは
.. 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 r 1 0 0 1 0 0 1 0 0 ...
$A_i = 3$ のときこんな感じ。rはロボットのいる点。

これに合わせて辺を張ると最小カット容量がそのまま答えとなる。
以下コード。

#include <bits/stdc++.h>
using namespace std;

template <class T> class Dinic {
public:
	struct info {
		int to, rev;
		T cap;
	};
	T ini, inf;
	vector<vector<info>> edge;
	vector<int> level, iter;

	Dinic(int N, T ini, T inf) : edge(N), level(N), iter(N), ini(ini), inf(inf) {
		// do nothing
	}

	void make_edge(int from, int to, T cap) {
		edge[from].push_back({ to, (int)edge[to].size(), cap });
		edge[to].push_back({ from, (int)edge[from].size() - 1, ini });
	}

	void bfs(int start) {
		for (int i = 0; i < level.size(); ++i) level[i] = -1;
		queue<int> q;
		level[start] = 0;
		q.push(start);
		while (q.size()) {
			int from = q.front();
			q.pop();
			for (auto& e : edge[from]) {
				if (e.cap > 0 && level[e.to] < 0) {
					level[e.to] = level[from] + 1;
					q.push(e.to);
				}
			}
		}
	}

	T dfs(int from, int goal, T flow) {
		if (from == goal) return flow;
		for (int& i = iter[from]; i < edge[from].size(); ++i) {
			auto& e = edge[from][i];
			if (e.cap <= 0 || level[from] >= level[e.to]) continue;
			T dflow = dfs(e.to, goal, min(flow, e.cap));
			if (dflow <= 0) continue;
			e.cap -= dflow;
			edge[e.to][e.rev].cap += dflow;
			return dflow;
		}
		return ini;
	}

	T maxflow(int start, int goal) {
		T maxflow = ini;
		while (1) {
			bfs(start);
			if (level[goal] < 0) return maxflow;
			for (int i = 0; i < iter.size(); ++i) iter[i] = 0;
			T flow;
			while ((flow = dfs(start, goal, inf))>0) maxflow += flow;
		}
	}
};

int main() {
	int N; cin >> N;
	vector<int> p(N),a(N);
	for(int i = 0; i < N; ++i) cin >> p[i];
	for(int i = 0; i < N; ++i) p[i]--;
	for(int i = 0; i < N; ++i) cin >> a[i];
	
	//コストを前計算
	vector<vector<int>> cx(N,vector<int>(N,0)),cy(N,vector<int>(N,0));
	for(int n = 0; n < N; ++n){
		int y = n, x = p[n], z = a[n];
		for(int i = 1; y + i < N ; ++i) cy[y+i][x] = !((i-1)%z);
		for(int i = 1; 0 <= y - i; ++i) cy[y-i][x] = !((i-1)%z);
		for(int j = 1; x + j < N ; ++j) cx[y][x+j] = !((j-1)%z);
		for(int j = 1; 0 <= x - j; ++j)	cx[y][x-j] = !((j-1)%z);
	}

	int inf = 12345;
	Dinic<int> dinic(N*N+2,0,inf);

	//コストの辺
	for(int i = 0; i < N; ++i) for(int j = 0; j < N; ++j){
		dinic.make_edge(N*N,i*N+j,cy[i][j]);
		dinic.make_edge(i*N+j,N*N+1,cx[i][j]);
	}

	//禁止辺
	for(int n = 0; n < N; ++n){
		int y = n, x = p[n], z = a[n];
		cy[y][x] = 1;
		cx[y][x] = 1;
		for(int i = 2; y + i < N ; ++i) dinic.make_edge((y+i-1)*N+x,(y+i)*N+x,inf);
		for(int i = 2; 0 <= y - i; ++i) dinic.make_edge((y-i+1)*N+x,(y-i)*N+x,inf);
		for(int j = 2; x + j < N ; ++j) dinic.make_edge(y*N+x+j,y*N+x+j-1,inf);
		for(int j = 2; 0 <= x - j; ++j)	dinic.make_edge(y*N+x-j,y*N+x-j+1,inf);
	}

	//最大流
	cout << dinic.maxflow(N*N,N*N+1) << endl;

    return 0;
}

2019-06-16

AtCoder偏差値くん開発記録。

AtCoder偏差値くんというwebアプリを作りました。
https://ningenme.net/hensachi/

･アプリの概要
AtCoderのidあるいはレートを入力すると偏差値が表示されるようなwebアプリケーション。

一年前ぐらいに一度似たようなものを作ったのですが運用を全く考えていなかったので無かったことになりました。
今回は一応色々調べながら(自分なりに)ちゃんと作ったのでその記録です。
(開発と呼べるほどではないかもですが)

ざっくりとした仕様
･週1でAtCoderのratingなどのユーザー情報を拾ってきてデータベースに追加
･標準偏差などの偏差値に必要なものを予め前計算
･クライアント側の入力に応じて偏差値を返す

シンプルだと思います。

[サーバー]　AWS
環境構築が苦手なので簡単らしいlightsailを選びました(それでも大変)
AWS何？って人はレンタルサーバーと認識すれば大丈夫だと思います。

※AWS悪いとこはあまりなくて、強いて言うならお金がネックになるのかなと思います。
ドメインで年間1500円ぐらいかかります、月々はアクセス多くなければ500円いかないと思います。
httpsのための保証書で月2000円ぐらいかかるのでそこが一番デカい。

[言語]　php, html, css, javascript.
lightsailのインスタンスとしてLAMPを選びました(環境構築しないでいいので楽)

[OS]　windows,linux
ローカルはwindows10、サーバーはubuntuです。

[ネットワーク]
サーバーにドメイン当てたり、DNSやhttpsの設定とかを最初にします。僕も何言ってるのか未だに分かりません。

[sshクライアント]　mobaXterm
便利。拡張でgitもすぐ入る。ftpも同時にこなしてくれるので良いです。

[ソース管理]　git
bareとnon-bareの違いを理解してなかったのでリポジトリ立てる時点で苦労しました。
hooksで自動化を設定しておくことでローカルからpushしたと同時にサーバー側でpullしてくれて便利。

[gitクライアント]　Source tree
CUIが苦手なので。直感的に操作できて良いです。

[データベース]　mysql
phpmyadmin使ったので楽でした。

[スクレイピング]　phpQuery
phpのライブラリ。一瞬で準備終わるので楽です。

[フロントエンド]　bootstrap
cssは書けないので全てbootstrapです。

[定期実行]　cron
定期的なクロールをかけるためにcronを使いました。
パスとかが中で違うみたいで結構苦労した。

多分使ってる技術はこれぐらいで、後はphpをいい感じに書きます(完)
どれも当たり前の技術な感じがしますが、知らないと使うという選択肢すら出てこないのでそのへん難しいなと思いました。

余談ですが、これを作ったときはwebアプリにフレームワークなんてものがあるということを知らなかったので現状生phpだけで動いています(ゴミwebアプリでは……？)(MVC何それ？って感じでした)

さすがにまずいのとバージョンアップしにくいのでlaravelで作り直している途中。

AtCoderのレーティングの計算式もあまり目を通せていないのでよくない。

無知って怖いね。おしまい。

2019-05-06

CPSCO参加記

こういうのは時間経つと書かないがちなのでサッと書いていく。

大阪の競プロ合宿に参加しました。
今更ですがCPSCOって何の略ですか？わかりません。
でもとりあえず3日間楽しかった。

・合宿前
最初は全然知らないイベントだなという感じだったのですが知ってる人が割と参加するっぽいので僕も行こうかなーとなりました。

初心者イベントと聞いていたので、ABCぐらいのをやるならwriter側で参加してみたいなとか考えてました……が、しかし他のwriter陣を見て「えっこれガチなやつでは？？？？」みたいになって辞退しました。

まーでもこの判断は正しくて(AtCoderで作問はハードルが高すぎるし僕では能力不足)あとシンプルに参加者側で良かったと思いました。問題が本当に良かったので。面白かった。

・1日目
知っている人いるかなーと不安だったけど割といて安堵。snowくん居てくれると楽なので全てのイベントでいてほしいね。うんうん。

あときくちさんNキチくんnadareさんしいくん辺りがいたのでメンタル的には楽でした。ありがたい。

煎茶さんとまつかわさんが初対面なのに話しかけてくれた感じがありとても助かりました。感謝。

session1はjunさんとペイさんとチームになりました。
チーム戦は初めてだったんですが僕が一応レート一番高かったので解く担当とか決めました。これ難しいね。

12345を二人に任せて僕は678をすることに。
任せた1-3がたまにデバッグとか手伝ったりしつつも通って良かった。自分が書いてないのにACするのが結構新鮮でした。

自分の担当の7の部分点も見えたのでとりあえず書いて通しました。

任せてた4が分からないらしいので見てみると問題文に「行列累乗をしてください」って書いてたので書きました。
他は解けないまま終わるも一応役割を果たせたかなあと。
(8の部分点と6を通せてないのはまあ戦犯なのですが……)

帰り際おさしみさんと挨拶をした。
ずっとFFだったけど実在性を確認してないままだったので少し嬉しかった(twitterの人大半そんなところがある)

・2日目
session2はNキチくんとkanayaくんとチームでした。

567を担当して何も出来ませんでした。おしまい()
チーム戦自体は楽しかったです。

session3はかわらさんとsoundscopeくんとチームでした。
568を担当して何も出来ませんでした。おしまい。

かと思いきや、かわらさんがふんわり5のアイデアをくれました。それで僕があーそれで解けますねとなり解くことに。

かわらさんに実装お願いする方がいいのでは？と思うもののpythonだとTLEが苦しいかもということで僕がc++で実装することに。

ここで、僕が実装始めてから途中でかわらさんが問題を誤読していたことが発覚してちょっと笑った。

でも実はそんなに間違えていなかったのと僕は解けそうなのを確認していたので影響は殆どなく終わりました。よかったね。

デバッグとか見てもらいつつ2人で解いたーって感じで楽しかったです。チーム戦良い。

この日は帰り際ドラグスコルさんとプリティーリズムの話ができて良かった。全人類プリティーリズムを見てほしい。

懇親会も楽しかった。
Arkくん黒ねえさんなおさんゴジラさんとあんまりtwitterを知らないながらも話す機会があって良かったなーと。

競プロの話とかしながらお酒飲めるの良いですね。
帰りの電車がかわらさんてんぷらさんと同じで、Twitterじゃしないような話とかできて良かった。

・3日目
session4は個人戦で、1234の4完で終わりました。まだまだだなあと痛感。

3日間通して色んな人と話せたりしてとても楽しかったです。空間の雰囲気も好きなのでオンサイトはとても良いなあと思いました(けんちょんさんとかこたまねぎくんとかが普通に同じ空間にいるの何か凄くないですか)(伝わって)

企画と運営してくれたはにーまさんに感謝です。色々準備が丁寧で凄いなと思いました。

作問陣も本当に感謝です。session全部楽しませていただきました。凄いしか出てこない……(小並感)

3日間とても楽しかったです。

僕も早く黄色ぐらいになって作問手伝えるようになりたいね。おしまい。

2019-01-28

AtCoder青になったメモ。

AtCoderで青色になった。嬉しい。

2019/1/27 全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019
Rank: 250(rated)
Perf: 2109
Rating: 1601(+74, highest!)
https://t.co/Z073F4eRzm

黄パフォ！国内176位で初オンサイト！そして念願の青レート！
めーっっっちゃ嬉しい！！！
— くる (@ningenMe) January 27, 2019

皆祝ってくれて界隈の優しさにビビる。ありがとうです。

青色に対してはかなり思い入れがあったので書きたいことを書いていく。
f:id:ningenMe:20190128203926p:plain

Rated参加41回。15ヶ月ぐらい。
水色入ってからかなり停滞した。
5ヵ月ぐらいレート上がらなくて、僕には青色無理かなとかなり悩んだ。

結構水色で止まる人って多いなと思っていたので、ここが1つの壁かなと。
まあ理由は明確でABCでレートが付かないから。
ARCでパフォ1200以上は取っていかないと全然レートが上がらないしむしろ下がる。
ABCで取れてた水パフォが取れない。厳しい。
(実際ARCになったからといってパフォが出にくいかは分からない。偏見。)

ここからレート上げるための方法がよく分からなかったので出来るだけ問題を解くことにした。

地頭足りてないと割り切って量をこなすのが一番マシかなと。

絶対に青になるぞ。 pic.twitter.com/kyIsKyDDXC
— くる (@ningenMe) August 24, 2018

AtCoder ProblemsでABCを全部埋めた(kenkooooさんに感謝)

f:id:ningenMe:20190128133037p:plain

f:id:ningenMe:20190128133100p:plain

あまりレートは上がらなかった。
悲しい。

まだ足りないみたいなのでAtCoder Scoresで下から埋めていった。(えびちゃんさんに感謝)
f:id:ningenMe:20190128133010p:plain
400、500埋めたぐらいでパフォが上がってきて、600埋めた状態で青色を迎えた。

パフォーマンス推移。
f:id:ningenMe:20190128132951p:plain
青パフォたまに黄パフォが出るようになって、やっと青になるという感じですね。大変。

精進グラフ。(えびちゃんさんに感謝)
f:id:ningenMe:20190128204307p:plain

停滞時も精進は続けてたので、どこがレートあがる要因だったかはわかっていない。
でも水色頭打ちしてたときより今の方が確実に強くなった気はする。

個人的には500埋めるで結構青になる気がする(僕は無理でしたが)

あと埋めるも大事だけどコンテスト中に解けないと意味ないのでムーブを結構考えるようになった。

自分にとって自明に感じるものを前から爆速で解く。
No sub.をしない(300点400点早解きは普通に実力差なので受け止めていく)
分からなかったらとりあえず飛ばして他を見る。
詰まったら順位表確認。多く解かれてるものから考察。

(それでも何も分からないとき)(ここからは最悪)

今まで解いた問題をまとめておき、似た問題を探す。https://ningenme.github.io/compro.html
解かないといけない問題かを把握する(落として良いことはないけどレートが下がるかどうかは判断できるので)
かなり多くの人が通してる400とか500だと貪欲とかシンプルな解法を疑う(最悪)
(Twitter前提だけど)知ってる人が通してたらその人が出来そうな解法を逆算する(最悪)
(Twitter前提だけど)知ってる人の得意の問題を把握してるとよい(要らないかもしれない)
めちゃめちゃ強い人が秒単位で通してたらライブラリゲーを疑う(最悪)

効率よく真面目にレートを上げるやり方は未だに分からない。
自分には量やるしかなさそう。

青になったとき本当にAtCoderやってて良かったと思った。
もうちょっとレート上げれそうなので頑張る。黄色を目指していく。

おしまい。

2019-01-05

2019目標メモ。

2019目標メモ。
･AtCoder青。
･黄パフォを出せるようにする。
･800点まで埋める。
･ARC-Eまで埋める。
･AGC-Dまで埋める。
･こどふぉ紫。
･オンサイトに出る。
･レートが上がらなくても精進をやめない。
･webアプリ何か一個ぐらいは作る。
･競プロ以外のプログラミングもそれなりに触る。
･会社をやめない/遅刻しない。

また年末に見返して出来たか確認。

2018-12-16

CODE THANKS FESTIVAL 2018 E - Union (400)

リンク：
beta.atcoder.jp
ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー
問題文
$1 \leq i \leq T$ の範囲の数字 $T$ 個をそれぞれについて $0$ 以上 $a_i$ 以下の好きな個数だけ黒板に書いたあと、次の操作を繰り返す。

・黒板に書かれている整数のうち、 $2$ つ以上ある整数 $X$ を $2$ つ消して、黒板に $X+1$ を1つ書く。

最終的に $1$ つの整数が黒板に書かれているようにできるような整数の書き方は何通りあるかを $mod(10^9 + 7)$ で求めよ。

制約
$1 \leq T \leq 300$
$0 \leq a_i \leq 300$

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

操作を繰り返しても数字を大きくするしか出来ないことが分かる。
よって黒板に書かれた一番小さい数xは1個or偶数個である。

1個のときはそれより大きい数字は書かれていてはいけない。
偶数個のときは愚直に全部の $x$ を $x+1$ に変換すると、一番小さい数が $x+1$ になるため、この数について再び同じように考える。

これを繰り返すと、ある決まった整数の書かれ方について条件を満たしているか判定ができる。
ただし $1 \leq i \leq T$ の各整数の書き方のパターンはおおよそ $a_1 × a_2 ×......× a_T$ なので膨大であり愚直な全探索はできない。

ただこのことから、 $x$ が $2N$ 個あると $x+1$ は $N$ 個増えるということが分かるのでこの遷移を使って $dp$ を書く。

$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}j\end{bmatrix}$ := 整数 $i$ が $j$ 個黒板に書かれているような場合の数。

$i$ の範囲は初期状態の $1$ から $T$ に加えて、整数 $T$ を操作したときのことも考慮して $T+\log_2{T}$ ぐらい必要。

また $j$ の範囲は初期状態の $0$ から $a_i$ に加えて、操作を行い1つ小さい数字の半分の個数が加わることを考慮して $2a_i$ ぐらい必要(雑に漸化式を立てると分かる)

よって $dp$ テーブルを $dp\begin{bmatrix}333\end{bmatrix}\begin{bmatrix}601\end{bmatrix}=0$ とする。

$1 \leq i \leq T$ の各整数は $0 \leq j \leq a_i$ の $j$ 個の範囲で好きに選べるため
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}0\end{bmatrix}=...=dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}a_i\end{bmatrix}=1 (1 \leq i \leq T)$

また各整数 $i$ が $0$ 個のパターンは常に $1$ 通りはあるため
$dp\begin{bmatrix}1\end{bmatrix}\begin{bmatrix}0\end{bmatrix}=...=dp\begin{bmatrix}332\end{bmatrix}\begin{bmatrix}0\end{bmatrix}=1$

遷移に関して。
整数 $i-1$ が $2j$ 個あるとき、 $i$ は $j$ 個増えるので、整数 $i$ が $k$ 個のときを考えると $dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}k\end{bmatrix}=dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}k\end{bmatrix}+dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}k-j\end{bmatrix}×dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}2j\end{bmatrix}$

こうして遷移を終えた後の $dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}$ の和が答えとなる。

以下実装。
遷移の際、更新した値を他の遷移に影響させないために一時的な配列を用いている。
その他は愚直。

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const ll MOD = (ll)1e9 + 7;
 
int main() {
  int T; cin >> T;
  vector<ll> a(T+1,0);
  for(int i = 1;i <= T; ++i) {
    cin >> a[i];
  }
  //dpテーブル
  vector<vector<ll>> dp(333, vector<ll>(601, 0));
  
  //各iがa[i]個以下である書き方が1通りずつ
  for(int i = 1; i <= T; ++i) {
    for(int j = 1; j <= a[i]; ++j) {
      dp[i][j] = 1;
    }
  }
  
  //各iが0個である書き方が1通りずつ
  for(int i = 1; i <= 332; ++i) {
    dp[i][0] = 1;
  }
  
  //小さい方から見る
  for(int i = 1; i <= 332; ++i){
    //一時的な配列
    vector<ll> tmp(601, 0);
    
    //遷移
    for(int j = 1; j <= 300; ++j) {
      for (int k = j; k <= 600; ++k) {
        (tmp[k] += (dp[i][k-j]*dp[i - 1][2*j])%MOD)%=MOD;
      }
    }
    
    //更新
    for(int j = 1; j <= 600; ++j) {
      (dp[i][j] += tmp[j]) %= MOD;
    }
  }
  //iが1個になる場合の数を計算
  ll ans = 0;
  for(int i = 1; i <= 332; ++i) {
  	(ans += dp[i][1])%=MOD;
  }
  cout << ans << endl;
  return 0;
}

2018-09-12

ARC 066 D - Xor Sum (600)

皆大好きXor Sum。解き直したので。
リンク：D - Xor Sum

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

問題文

正の整数 $N$ が与えられます。
2 つの整数 $u,v (0 \leq u, v \leq N)$ であって、ある非負整数 $a,b$ が存在して、 $a\ xor\ b = u, a + b = v$ となるようなものが何通りあるかを求めてください。ここで、 $xor$ はビットごとの排他的論理和を表します。なお、答えは非常に大きくなることがあるので、 $10^{9}+7$ で割った余りを求めてください。

制約

$1 \leq N \leq 10^{18}$

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

難しい。 $N$ が大きすぎて何もできない。
最終的には $O(\log{N})$ になるんだけどその解説も天才すぎる。
https://atcoder.jp/img/arc066/editorial.pdf

桁dpということを強く意識して解いてみる(結局やることは解説まんま)

解説前半部分の $a + b \leq N$ だけ考えれば十分って部分は典型なのかな。

基本情報技術者の勉強で半加算器とか見てると分かりそうな気もする。

結局問題としては $a + b \leq N$ を満たす $a,b$ の組み合わせの数の桁dp(正確にはbit桁dpかな)

まず $N$ を2進に直す(bitsetとかvector < bool > とか)

$10^{3} \leq 2^{10}$ なので $10^{18} \leq 2^{60}$ 、60桁あれば十分。
　

桁dpなので上の桁から決めていく。解説通りにdpをとる。

「 $dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}j\end{bmatrix}=a$ と $b$ の $i$ ビット目以上が決定していて、その段階で $(v >> i) = (N >> i) - j$ となる通り数。」

最初何言ってるか分からなかった。天才過ぎて辛い。
具体的にやることは $N$ のビットを上から見て、それ以下になるような数を数え上げる。
(普通の桁dpと同じで、上位の桁がある程度決まると下位の桁をどうとっても $N$ 以下になるという性質を利用する)

dpテーブルは $dp\begin{bmatrix}61\end{bmatrix}\begin{bmatrix}3\end{bmatrix}$ ととり(0-indexed)、初期化は $dp\begin{bmatrix}60\end{bmatrix}\begin{bmatrix}0\end{bmatrix}=1$ それ以外は $0$ 。
(この $dp\begin{bmatrix}60\end{bmatrix}\begin{bmatrix}0\end{bmatrix}=1$ というのは $N$ の60桁目のビット(0-indexed,また制約より必ず0)に対して $a,b$ の60桁目のビット(0-indexed)をともに $0$ ととることで必ず題意を満たすことができるので)(簡単に言うと $0+0=0$ )(それはそう)

まず先にコードを書くとこんな感じ。

#include <iostream>
#include <vector>
#include <bitset>

using namespace std;
using ll = long long;
const ll MOD = (ll)1e9 + 7; 

int main() {
	ll N; cin >> N;
	bitset<60> bs(N);	//2進に直す
	vector<vector<long long>> dp(61, vector<long long>(3, 0));//dpテーブル
	dp[60][0] = 1;//初期化
		
	//上の桁から見ていく
	for (int i = 59; i >= 0; --i) {
		//i桁目のbitが立ってるとき
		if (bs[i]) {
			dp[i][0] = dp[i + 1][0];
			dp[i][1] = dp[i + 1][0] + dp[i + 1][1];
			dp[i][2] = 2 * dp[i + 1][1] + 3 * dp[i + 1][2];
		}
		//i桁目のbitが立ってないとき
		else {
			dp[i][0] = dp[i + 1][0] + dp[i + 1][1];
			dp[i][1] = dp[i + 1][1];
			dp[i][2] = dp[i + 1][1] + 3 * dp[i + 1][2];
		}
		dp[i][0] %= MOD;
		dp[i][1] %= MOD;
		dp[i][2] %= MOD;
	}
	cout << (((dp[0][0] + dp[0][1]) % MOD) + dp[0][2]) % MOD << endl;
	return 0;
}

$N$ のビットを上から見ていく(for int i = 59; 0 <= i; --i)

イメージとしてはこんな感じ。
f:id:ningenMe:20180911183219p:plain
(今この $N$ は適当な $N$ )

このとき $dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}j\end{bmatrix}(j=0,1,2)$ が何を表しているかというと
「 $dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}j\end{bmatrix}=a$ と $b$ の $i$ ビット目以上が決定していて、その段階で $(v >> i) = (N >> i) - j$ となる通り数。」である。ここが一番分かりにくい気がする。

$N$ の $59$ 桁目から $i$ 桁目までの2進数を一つの数 $M_i$ 、
$a$ の $59$ 桁目から $i$ 桁目までの2進数を一つの数 $\alpha_i$ 、
$b$ の $59$ 桁目から $i$ 桁目までの2進数を一つの数 $\beta_i$ として見たとき

$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}0\end{bmatrix}$ は $\alpha_i+\beta_i=M_i$ となる通り数。
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}$ は $\alpha_i+\beta_i=M_i - 1$ となる通り数。
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}2\end{bmatrix}$ は $\alpha_i+\beta_i \leq M_i - 2$ となる通り数。である(これでも分かりにくいけど)

f:id:ningenMe:20180911185005p:plain

ここで次のビットである $i-1$ 桁目を考えると
$N$ の $i-1$ 桁目が $1$ のとき $M_{i-1}=2M_i + 1$ 、
$N$ の $i-1$ 桁目が $0$ のとき $M_{i-1}=2M_i$
となる(2進数の定義より)

場合分けして丁寧に遷移を考える。

(1) $N$ の $i-1$ 桁目が $1$ のとき

$M_{i-1}=2M_i + 1$ より $dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}j\end{bmatrix}(j=0,1,2)$ について以下のようになる。
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}0\end{bmatrix}$ は $\alpha_{i-1}+\beta_{i-1}=M_{i-1}=2M_i + 1$ となる通り数。
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}1\end{bmatrix}$ は $\alpha_{i-1}+\beta_{i-1}=M_{i-1} - 1=2M_i$ となる通り数。
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}2\end{bmatrix}$ は $\alpha_{i-1}+\beta_{i-1} \leq M_{i-1} - 2 = 2M_i - 1$ となる通り数。

ここで
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}0\end{bmatrix}$ は $\alpha_i+\beta_i=M_i$ となる通り数。
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}$ は $\alpha_i+\beta_i=M_i - 1$ となる通り数。
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}2\end{bmatrix}$ は $\alpha_i+\beta_i \leq M_i - 2$ となる通り数、だったので
$\alpha_i+\beta_i$ の遷移を考えると2倍して0 or 1 or 2を足すという操作ができる。
( $a,b$ の $i-1$ 桁目のビットについて、共に1、どちらか一方が1、共に0の高々3種類なので)

よって以下のような遷移を考えればよい。

f:id:ningenMe:20180912022255p:plain

従って
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}0\end{bmatrix}(=2M_i+1)$ は
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}0\end{bmatrix}(=2M_i)$ に対して $+1$ の1通りのみで
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}0\end{bmatrix}=dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}0\end{bmatrix}$

$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}1\end{bmatrix}(=2M_i)$ は
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}0\end{bmatrix}(=2M_i)$ に対して $+0$ の1通り、
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}(=2M_i-2)$ に対して $+2$ の1通り、計2通りで
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}1\end{bmatrix}=dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}0\end{bmatrix}+dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}$

$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}2\end{bmatrix}(\leq 2M_i-1)$ は
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}(=2M_i-2)$ に対して $+0,+1$ の2通り、
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}2\end{bmatrix}(\leq 2M_i-4)$ に対して $+0,+1,+2$ の3通り、計5通りで
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}2\end{bmatrix}=2dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}+3dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}2\end{bmatrix}$

(2) $N$ の $i-1$ 桁目が $0$ のとき

$M_{i-1}=2M_i$ より $dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}j\end{bmatrix}(j=0,1,2)$ について以下のようになる。
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}0\end{bmatrix}$ は $\alpha_{i-1}+\beta_{i-1}=M_{i-1}=2M_i$ となる通り数。
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}1\end{bmatrix}$ は $\alpha_{i-1}+\beta_{i-1}=M_{i-1} - 1=2M_i - 1$ となる通り数。
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}2\end{bmatrix}$ は $\alpha_{i-1}+\beta_{i-1} \leq M_{i-1} - 2 = 2M_i - 2$ となる通り数。

(1)と同様に以下のような遷移を考えればよい。

f:id:ningenMe:20180912022052p:plain

従って
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}0\end{bmatrix}(=2M_i)$ は
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}0\end{bmatrix}(=2M_i)$ に対して $+0$ の1通り、
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}(=2M_i-2)$ に対して $+2$ の1通り、計2通りで
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}0\end{bmatrix}=dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}0\end{bmatrix}+dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}$

$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}1\end{bmatrix}(=2M_i - 1)$ は
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}(=2M_i - 2)$ に対して $+1$ の1通りのみで
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}1\end{bmatrix}=dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}$

$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}2\end{bmatrix}(\leq 2M_i-2)$ は
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}(=2M_i-2)$ に対して $+0$ の1通り、
$dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}2\end{bmatrix}(\leq 2M_i-4)$ に対して $+0,+1,+2$ の3通り、計4通りで
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}2\end{bmatrix}=dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}+3dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}2\end{bmatrix}$

以上をまとめて
(1) $N$ の $i-1$ 桁目が $1$ のとき
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}0\end{bmatrix}=dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}0\end{bmatrix}$
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}1\end{bmatrix}=dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}0\end{bmatrix}+dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}$
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}2\end{bmatrix}=2dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}+3dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}2\end{bmatrix}$

(2) $N$ の $i-1$ 桁目が $0$ のとき
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}0\end{bmatrix}=dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}0\end{bmatrix}+dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}$
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}1\end{bmatrix}=dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}$
$dp\begin{bmatrix}i-1\end{bmatrix}\begin{bmatrix}2\end{bmatrix}=dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}1\end{bmatrix}+3dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}2\end{bmatrix}$

以上の遷移を行うことで $dp\begin{bmatrix}0\end{bmatrix}\begin{bmatrix}0\end{bmatrix}+dp\begin{bmatrix}0\end{bmatrix}\begin{bmatrix}1\end{bmatrix}+dp\begin{bmatrix}0\end{bmatrix}\begin{bmatrix}2\end{bmatrix}$ が答えとなる。

難しすぎる。700点でしょ(800点でもいい)
ビットの遷移が $+0,+1,+2$ しかないので $dp\begin{bmatrix}i\end{bmatrix}\begin{bmatrix}2\end{bmatrix}(\leq M_i-2)$ の状態をまとめられるってのが凄い、ある意味桁dpらしいような気もするし強い人は気づくのかな。天才になりたいものです。

くるのプログラミング記録

プログラミングの感想とか解説とか。