競技プログラミングコンテストサイトAtCoderが、有料の検定を始める。
会社が社員や応募者に対して試験を受けさせるTOPSICに対して、AtCoderは今も問題を卸している。今回の検定は会社の採用に応募しようとする人が受けるのが主だろうか。それなら無料で毎週のコンテストに出てレートを獲得すれば、「AtCoderで黄色です」も「アルゴリズム実技検定エキスパートです」も同じ事だと思うのだけど、一度のコンテストで結果が出るのがウリらしい（AtCoderの普段のコンテストはある程度の回数をこなさないとレートが付かない）。
・「一日の受験でAtCoderの色と同等の評価が得られる」が最大のメリットです。既にレーティングを持っている人にはちょっとメリットが小さいです。
— chokudai(高橋 直大)🌸🍆🍡 (@chokudai) November 18, 2019
・とはいえ、レーティングだと良くわからないけど資格なら分かる、という環境はあるので、無駄にはならないと思います
仕事が忙しくて、お金はあるけれど時間が無いという人向けと。時間を掛けるかお金を払えというのはソシャゲーっぽい。
仕事でプログラムを書いているけれど普段のコンテストには出ない人が検定を受ける → 偉い人の目にとまる → 偉い人が採用や社員の自己研鑽に良いのではと考える → この資格やAtCoderのレートで選考が有利になったり会社から報奨金が出たりする
という流れに期待しているので、仕事でプログラムを書いているけれど競技プログラミングはやっていないという人向けに記事を書いてみる。
実務の役に立つのか
Twitterなどで定期的に燃えている話題である。ニコニコ大百科に端的にまとまっている。
- 主な批判
- 競技プログラミングをやると、可読性より速度を優先するため、汚いコードを書く癖がつく。
- 競技プログラミングをいくらやったところで、ライブラリの使い方や設計技術は身につかない。
- 競技プログラミングのランキングをあげても就職の役には立たない。
- 主な反論
- 競技プログラミングを極めた人のコードは美しい。汚いのは無能の証。美しさが分からないのも無能の証。
- 競技プログラミングを通じてアルゴリズムの考え方を身につければ、設計などもおのずと洗練されてくる。
- むしろ、計算量の見積もりもせずに設計してプロジェクトを破綻させるのは、非競プロerの方。
- お前らIT土方の就職には役立たないが、一流の人材を求めるところでは評価する会社もある。
私の考えだと、AtCoderの300点問題（サンプル問題のF）くらいまでは業務でプログラムを書けるかどうかと相関がある。300点くらいの問題が解けるならば業務のプログラムも書けるし、業務でプログラムが書けるなら300点くらいまでは解ける。それより先は、競技プログラミングのほうは業務で使わなそうなアルゴリズムとかの知識と技術が必要になるし、業務のほうもライブラリの使い方とか設計ができるのかという話になってくるのであまり関係が無い。野球選手がサッカーをすればその辺の人よりは上手いだろう、程度の繋がりはあると思う。
アルゴリズム実技検定の配点が興味深い。難しい問題ほど点数が低い。サンプル問題は過去のコンテストの問題から持ってきているので点数が書かれているけれど、この点数でもなお難しさには合っていないと思う。点数が100点から200点くらい増えると、解くのに掛かる時間が倍掛かるイメージ。AtCoderとしても、300点から400点くらいの問題が解けるかどうかを見分けられるようにしたいという意図があるのだろうか。
| 問題 | 元の点数 | 検定の点数 | 累積 | 先頭から解いたときの称号 |
|---|---|---|---|---|
| A | 100 | 9 | 9 | - |
| B | 200 | 8 | 17 | - |
| C | 200 | 8 | 25 | エントリー |
| D | 300 | 7 | 32 | エントリー |
| E | 300 | 7 | 39 | エントリー |
| F | 300 | 7 | 46 | 初級 |
| G | 400 | 6 | 52 | 初級 |
| H | 400 | 6 | 58 | 初級 |
| I | 400 | 6 | 64 | 中級 |
| J | 500 | 6 | 70 | 中級 |
| K | 500 | 6 | 76 | 中級 |
| L | 500 | 6 | 82 | 上級 |
| M | 600 | 6 | 88 | 上級 |
| N | 600 | 6 | 94 | エキスパート |
| O | 600 | 6 | 100 | エキスパート |
業務に関係のないところがむしろ楽しいという考えもある。保守性とか他人が読みやすいとかそういうことは一切気にせずにコードを書き殴れる。サーバー側でのチェックさえ通れば、もう読み返すこともない。業務ならテストは通ったが実可動で大丈夫だろうかと不安になることもあるけれど、競技プログラミングならばたとえバグっていてもチェックが通ったなら勝ちである。白黒はっきり。
Tips
普段プログラムを書いているけれど、AtCoderのコンテストに出たことがない人向け。
ググって良い
普段のコンテストで「2人以上で結託し、解答する行為」は禁止されているので、チャットで他人に相談したりするのはNG。でも、コンテスト中のインターネットの使用は禁止されていない。アルゴリズム実技検定でも多分同様でしょう。
オンライン整数列大辞典（OEIS）というサイトがあって、数列で検索ができる。数列の計算式も出てくる。たまにこれで検索するだけで解ける問題もある。まあ、作問者にしてみれば面白くないので、めったにないだろうけど。
良く使うアルゴリズムを事前に書いておいて、それをコピペして使っても良い。ある程度慣れた人はみんな自分用に用意していると思う。私のはこれ。
何度提出しても良い
AtCoderはコンテスト終了後にまとめて採点される形式ではない（他のコンテストではそういう形式もあるけれど）。提出したコードが間違えていると、普段のコンテストでは5分のペナルティ（同点ならば解答時間順に順位が付くところ、5分遅く提出したのと同じ扱い）。アルゴリズム検定では1分間再提出ができないだけ。
- 検定中に問題に正解すると点数を獲得できます。正解時間は不正解の回数は問いません。
- 検定中に何度でも同じ問題に提出することが出来ますが、同じ問題に1分以内に再提出することはできません。
「合っているとは思うのだけど、いまいち確信が持てないなぁ」くらいならば、さっさと出してしまったほうが良い。
標準入出力を扱えますか？
AtCoderのコンテストでは、標準入力から入力を読んで、答えを求めて標準出力に書き出す。
プログラミングと言ったら、まずはHello worldを標準出力に出力するところから始めると思っていたのだけど、ウェブアプリやスマホアプリをバリバリ書いていても、意外と標準入出力の扱い方を知らない人もいるらしい。
プログラマーに競技プログラミングを勧めたら「標準入出力って何？」みたいな事を言われて、「何言ってんだこの人……」となったけど、ウェブアプリとかから入るとマジで標準入出力は全く触らないままらしい。 https://t.co/NVGmhh60lP
— kusanoさん@がんばらない (@kusano_k) September 20, 2017
コンテスト前に自分の使う言語での標準入出力の使い方は確認しておいたほうが良い。ここに一通り載っている。
デバッグ
問題に書かれている入出力例と違う結果が出たり、セグフォしたりするならば、普通にがんばってデバッグ。printfデバッグが意外と有用。デバッガでループごとに変数の値を確認するくらいなら、全部出力してしまったほうが速いことが多い。
入出力例はあっているのに、提出してみると不正解になる場合がやっかい。1, 2個だけ不正解になる場合は境界条件の見落としが多い。0<=N<=1000みたいな問題のN=0の場合に特別な処理が必要で、それが抜けているとか。半分くらい抜けているときは、まずはオーバーフローを疑う。ある値が32ビットより大きくなりうるのに32ビット変数で扱っているとか。
どうしようもなければ、遅いけど確実なナイーブな解法を実装して、小さなテストケースをランダムに生成して出力を比較。間違える入力を探す。出力が間違えるのではなく解法が分からない場合も、ナイーブな解法を実装して色々な入力に対する出力を見ていると、解法が見えてくることもある。
計算量
「アルゴリズム」実技検定なので時間計算量は重要。AtCoderの場合、空間計算量の問題になることはあまりない。言語によって差が大きいかららしい。
普段プログラムを書いていて、「この処理のオーダー（$O(n \log n)$とか）は？」と気にすることがあっても、実時間で何秒かを気にすることはあまりないのではないかと思う。競技プログラミングをやったことがない人に「こんな問題を解いているのか。簡単じゃん？」と言われて、良く聞いてみたら、制限時間に全く間に合わない解法だったということもあった。
AtCoderのコンテストはだいたい2秒。問題によってはもうちょっと長い。雑な見積もりとして、C++ならば、オーダーの変数に制約の最大の値を入力してみて、1,000万くらいならだいたいOK。Pythonなら100万くらい。JavaやRubyはその間に入る感じ。
これを逆手に取ることもできる。作問者の心情としては想定解法よりも簡単だけど遅いプログラムで通されたくはないので、制約をなるべく大きくする。ということは、上記の100万から1,000万くらいになるような制約になる。想定解法のオーダーが推測できる。$n\leq 10^5$くらいなら$O(n)$か$O(n \log n)$、$n\leq 1,000$なら$O(n^2)$、$n \leq 100$なら$O(n^3)$、$n \leq 20$なら$O(n2^n)$、$n \leq 8$なら$O(nn!)$とか。
練習方法
サンプル問題が全てAtCoder Beginner Contestの問題なので、AtCoder Beginner Contestの過去問を解けば良いと思う。最初から解きたくなるところだけど、難易度や問題傾向が違うので、最近の問題から解いたほうが良いと思う。
本を買うなら、プログラミングコンテストチャレンジブック（通称「蟻本」）がオススメ。
サンプル問題の解説
一通り解いてみた。ちなみに、これらの問題は過去のAtCoderの問題そのままなので、問題名か問題のファイル名で検索すれば出題されたときのコンテストが出てきて、そこに公式の解説もある。
本番でこれらの問題（や過去のAtCoderの問題）が出ることはないだろうから、これらの問題の解法だけを覚えても役に立たないので、なるべく汎用的な考え方とかを書いてみる。私の解法の言語はPython3かC++。
A - T or T
素直に解くだけ。100点問題はループを使わなくても解けるようになっているらしい。
N, A, B = map(int, input().split())
print(min(N*A, B))
B - Roller Coaster
200点問題も特に難しいことはない。まだ計算量などを考える必要も無い。
N, K = map(int, input().split())
h = map(int, input().split())
print(len([x for x in h if x>=K]))
C - Time Limit Exceeded
tがT以下で、cが最小のものを出力。
N, T = map(int, input().split())
c = [0]*N
t = [0]*N
for i in range(N):
c[i], t[i] = map(int, input().split())
if min(t)<=T:
print(min(c[i] for i in range(N) if t[i]<=T))
else:
print("TLE")
D - Unification
ここから300点。検定の点数で7点。問題の通りに実装するだけでは解けなくなってくる。
$N\leq 10^5$なので、キューブの取り方を総当たりすると当然間に合わない。
このような「○○な部分を選んで××します。最大何回○○できますか？」というような問題は、「その選ぶことに意味はあるのか？」ということをまず考えると良い。この問題では意味が無い。赤と青のキューブが残っていればどこかが取り除けるのだから、赤か青の多いほうが残るだけである。選び方によって取り除けるキューブの個数が変わることはない。取り除けるキューブをどれでも良いので貪欲に取り除いていけば良い。
素直に取り除く処理を実装すると、実装方法によっては、$O(N^2)$になってしまって間に合わない。さらに考えてみると、もうキューブの並びとかどうでも良くて、個数だけ見れば良いことが分かる。min(赤の個数, 青の個数)回取り除ける。
S = input()
print(min(S.count("0"), S.count("1"))*2)
E - ID
こういう書式指定文字列が必要になる問題はAtCoderでは珍しい。検定ではこういう問題も出していくぞということだろうか。
各市ごとに、自分より早く誕生した市を数えていては間に合わない。まずは年順にソートして、ある県に市が何個あるのかを数えておけば良い。「処理する順番を変えられないか？」という発想が重要。入力の先頭から順番ではダメ。
N, M = map(int, input().split())
Y = [0]*M
P = [0]*M
for i in range(M):
P[i], Y[i] = map(int, input().split())
YP = list(zip(Y, P, range(M)))
YP.sort()
C = [0]*(N+1)
ans = [""]*M
for y, p, i in YP:
C[p] += 1
ans[i] = "%06d%06d" % (p, C[p])
for a in ans:
print(a)
F - Green Bin
アナグラムを全て試していては間に合わない。「Aに何か操作をしてBになるとき～」のような問題では、f(A)=f(B)となるような操作fが無いかを考える。アナグラムの場合、fは文字のソートである。
競技プログラミングの場合、平均的な計算量を小さくすることに意味は無く、最悪ケースの計算量を小さくする必要がある。この問題の最悪ケースは全ての文字列がアナグラムになっている場合。このとき答えはN*(N-1)/2。アナグラムになる組み合わせごとに+1するような解法では間に合わない。下の解法では自分よりも前に出現した自分のアナグラムを数え上げている。
N = int(input())
s = [input() for _ in range(N)]
ans = 0
M = {}
for x in s:
x = "".join(sorted(x))
if x not in M:
M[x] = 0
ans += M[x]
M[x] += 1
print(ans)
G - Enough Array
ある範囲がK以上という条件を満たすならば、その範囲を含む範囲は全て条件を満たす。ギリギリ条件を満たす範囲だけ探していって、それより広い範囲は何個あるかを足し合わせれば良い。「しゃくとり法」を使う。K以上ならば範囲の左端を右に動かして狭め、K以下ならば範囲の右端を右に動かして広める。各左端lに対して右端を探す感じにすると綺麗に書ける。
N, K = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
r = 0
s = 0 # sum(a[l:r])
for l in range(N):
while r<N and s<K:
s += a[r]
r += 1
if s>=K:
ans += N-r+1
s -= a[l]
print(ans)
H - Powerful Discount Tickets
合計金額を最小化しろという問題。各商品に割引券を1枚使うと合計金額をいくら安くできるかを考える。商品の現在の金額の半分なので、なるべく金額が高い商品に使ったほうが得。
値を追加と、最大の値の取り出しとが高速にできるデータ構造があれば良い。それがpriority queue。Pythonのheapqは最小の値が出てくるので、符号を反転させて入れている。
from heapq import *
N, M = map(int, input().split())
A = map(int, input().split())
H = [-a for a in A]
heapify(H)
for _ in range(M):
a = -heappop(H)
a //= 2
heappush(H, -a)
print(sum(-a for a in H))
I - Lamp
各マスについて、O(照らすマス)かかるアルゴリズムでは間に合わない。上下左右に分けて考える。一方向だけならば壁から数えていけばO(HW)で計算できる。後は各マスについて上下左右を足し合わせれば良い。
こういう問題は事前に周囲に壁を作っておくとプログラムを書くのが楽になることがある。
Pythonだと間に合わなかった。がんばればたいていの問題はPythonでも通せるらしいけれど、がんばるのが面倒なので私はC++を使います。
[AtCoder] 橙(2400+)になりました | maspyのHP
ちなみに、Time limit exceed（TLE、実行時間オーバー）のケースの実行時間は2秒ちょっとだけど、これは2秒を超えると実行が打ち切られるからであって、あと0.2秒高速化すれば間に合うわけではない。
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
using namespace std;
int main()
{
int H, W;
cin>>H>>W;
vector<string> S(H+2);
S[0] = string(W+2, '#');
for (int y=1; y<H+1; y++)
{
string s;
cin>>s;
S[y] = "#"+s+"#";
}
S[H+1] = string(W+2, '#');
vector<vector<vector<int>>> T(H+2, vector<vector<int>>(W+2, vector<int>(4)));
for (int y=0; y<H+2; y++)
for (int x=0; x<W+2; x++)
if (S[y][x]=='.')
{
T[y][x][0] = T[y][x-1][0]+1;
T[y][x][1] = T[y-1][x][1]+1;
}
for (int y=H+1; y>=0; y--)
for (int x=W+1; x>=0; x--)
if (S[y][x]=='.')
{
T[y][x][2] = T[y][x+1][2]+1;
T[y][x][3] = T[y+1][x][3]+1;
}
int ans = 0;
for (int y=0; y<H+2; y++)
for (int x=0; x<W+2; x++)
ans = max(ans, accumulate(T[y][x].begin(), T[y][x].end(), 0)-3);
cout<<ans<<endl;
}
J - Get Everything
500点。難しくなってくる。
Nの制約の小ささに気が付ければ勝ち。$N\leq 12$なので、$O(2^N)$が間に合う。
あとは動的計画法。動的計画法では、「後の計算が依存するものは何か」を考える。状態のうち依存しないものはまとめてしまい、状態の数が計算できる範囲に収まれば良し。この問題の場合は、鍵を先頭から順番に使っていくと考え、何番目までの鍵を考慮したかとどの宝箱を開けたか。これが同じならばどのような鍵の組み合わせて宝箱を開けていたとしても、後の計算には影響しない。何番目までの鍵を考慮したかはループ変数として持っているので、どの宝箱を開けたかごとに最小の金額をメモしておけば良い。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int N, M;
cin>>N>>M;
vector<int> a(M);
vector<int> c(M);
for (int i=0; i<M; i++)
{
int b;
cin>>a[i]>>b;
for (int j=0; j<b; j++)
{
int t;
cin>>t;
c[i] |= 1<<(t-1);
}
}
int oo = 100000000;
vector<int> T(1<<N, oo);
T[0] = 0;
for (int i=0; i<M; i++)
for (int j=0; j<1<<N; j++)
T[j|c[i]] = min(T[j|c[i]], T[j]+a[i]);
int ans = T[(1<<N)-1];
cout<<(ans<oo ? ans : -1)<<endl;
}
K - Strings of Impurity
$10^{100}$に面食らうけれど、これは無限大と思っておけば良い。無限大だと問題をきっちり定義するのが大変なのでしょう。
まずは遅くても良いから解ける方法を考え、それから速くする。tを先頭から見ていき、s'の中から探すという解法が思いつく。この解法は$O\left(\left|s\right|\left|t\right|\right)$。sの各場所ごとにある文字cが次に出てくるのはどこか？が高速に得られれば良い。これを事前に計算しておく。下のコードのT。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{
string s;
cin>>s;
string t;
cin>>t;
int n = (int)s.size();
// s[T[p][c]] == c
vector<vector<int>> T(n, vector<int>(26, -1));
for (int c=0; c<26; c++)
{
int p = 0;
while (p<n && s[p]!='a'+c)
p++;
if (p<n)
{
for (int i=n-1; i>=0; i--)
{
T[i][c] = p;
if (s[i]=='a'+c)
p = i;
}
}
}
long long ans = 0;
int p = n-1;
for (char c: t)
{
int np = T[p][c-'a'];
if (np==-1)
{
cout<<-1<<endl;
return 0;
}
ans += np-p + (np<=p ? n : 0);
p = np;
}
cout<<ans<<endl;
}
L - League
これもK問題と同様に、遅い解法をまず考えて高速化する。ある日、選手xが選手yと、選手yが選手xと試合をしたがっているとき、xとyが試合をしない理由はない。貪欲に試合をしたがっている選手の組み合わせを探すのに$O(N)$それを$O(N)$回で間に合うかと思いきや、試合の最大日数は$O(N)$ではなく$O(N^2)$になりうるので間に合わない。
最適な試合の日程で、ある日選手xと選手yが試合をするならば、その前日にxもしくはyの少なくともどちらか一方は試合をしているということに気が付けば解ける。なぜなら、どちらも試合をしていないならば、xとyの試合が前日にできるから。ということで、各日に試合をした選手を覚えておいて、その選手だけ次の日に試合をするかどうかを調べれば良い。
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
int main()
{
int N;
cin>>N;
vector<vector<int>> A(N, vector<int>(N-1));
for (int i=0; i<N; i++)
for (int &a: A[i])
{
cin>>a;
a--;
}
for (auto &a: A)
reverse(a.begin(), a.end());
int c = 0;
int ans = 0;
set<int> S;
while (true)
{
if (S.empty())
{
// first
for (int i=0; i<N; i++)
if (A[A[i].back()].back()==i)
S.insert(i);
}
else
{
set<int> P;
P.swap(S);
for (int a: P)
if (!A[a].empty() &&
!A[A[a].back()].empty() &&
A[A[a].back()].back()==a)
{
S.insert(a);
S.insert(A[a].back());
}
}
if (S.empty())
{
cout<<-1<<endl;
return 0;
}
for (int a: S)
{
A[a].pop_back();
if (A[a].empty())
c++;
}
ans++;
if (c==N)
break;
}
cout<<ans<<endl;
}
M - Absolute Minima
600点問題。普通に難しい。
$f(x)=\sum\left|x-a_i\right| + \sum b_i=\sum_{a_i\lt x}(x-a_i)-\sum_{a_i\gt x}(x-a_i)+\sum b_i$。微分すると、$f'(x)=\left|a_i\lt x\right|-\left|a_i\gt x\right|+\sum b_i$。これまでに出てきたaの中央値で$f(x)$が最小値を取ることが分かる。Priority queueを単に使うだけでは最小値か最大値かしか得られないので、priority queueを2個使って、小さいaと大きいaをそれぞれに格納しておく。
Priority queueにとても小さな数ととても大きな数を入れておくと、queueが空の場合の処理をはしょれる。
#include <iostream>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
int main()
{
int Q;
cin>>Q;
// Al.top() <= Ar.top()
// Al.size()==Ar.size() or Al.size()==Ar.size()+1
priority_queue<long long> Al;
priority_queue<long long, vector<long long>, greater<long long>> Ar;
// Alsum = sum(Al), Arsum = sum(Ar)
long long Alsum = 0, Arsum = 0;
long long Bsum = 0;
Al.push(-9999999999LL);
Ar.push(9999999999LL);
for (int i=0; i<Q; i++)
{
int q;
cin>>q;
if (q==1)
{
long long a, b;
cin>>a>>b;
if (a <= Al.top())
Al.push(a), Alsum += a;
else
Ar.push(a), Arsum += a;
if (Al.size() > Ar.size()+1)
{
long long t = Al.top();
Al.pop(), Alsum -= t;
Ar.push(t), Arsum += t;
}
if (Al.size() < Ar.size())
{
long long t = Ar.top();
Ar.pop(), Arsum -= t;
Al.push(t), Alsum += t;
}
Bsum += b;
}
else
{
long long x = Al.top();
long long f = - Alsum + Al.size()*x + Arsum - Ar.size()*x + Bsum;
cout<<x<<" "<<f<<endl;
}
}
}
N - Colorful Tree
「アルゴリズム」実技検定ではあるけれど、ダイクストラとか最長共通部分列を求めるとか、教科書に出てくるアルゴリズムをそのまま使うような問題はAtCoderではあまり出てこない。このくらいの難易度になると、良く知られたアルゴリズムを道具として一部で使うとか、一工夫を加えて使うとかする問題が出てくる。
問題を作る側も、良く知られた問題に一ひねりを加えて問題を作ることがあるので、解くほうはその一ひねりをどう対処するかを考えれば良いのだろうか。まあ、一ひねりによって全く違う問題になることもあるのだけど。
木が与えられて、頂点xと頂点yの距離を何度も聞かれる問題では、最小共通祖先を使う解法が知られている。頂点uと頂点vの最小共通祖先とは、頂点uと頂点vの共通の祖先で、根から最も遠いものである。前処理として、ある頂点を根にして、そこからの距離を求めておく。頂点vの根からの距離をD(v)とすると、頂点uと頂点vの距離はD(u)+D(v)-2*D(LCA(u, v))である。
この問題の一ひねりは、辺の長さが変わることである。各頂点で、各色について、その色の辺の個数と合計長を記録しておけば辺の長さの変化にも対応できる。ただし、色は最大でN-1なので、全ての色について記録しておくのは無理である。考えてみると、全ての頂点で全ての色が必要なわけではない。その頂点を対象とするクエリ、もしくはその頂点を最小共通祖先として参照するクエリの色だけを覚えておけば良い。
この手の問題では律儀に前処理を終えてからクエリを読む必要はないということが重要。最初にクエリを全部読んで、それからクエリに応じた前処理を行っても良い。
#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
#include <map>
using namespace std;
// last common ancestor
class LCA
{
int n;
vector<vector<int>> P;
vector<int> D;
public:
// a in E[b] <=> b in E[a]
LCA(vector<vector<int>> E, int root)
{
n = (int)E.size();
P = vector<vector<int>>(n);
D = vector<int>(n);
function<void (int, int, int)> f = [&](int c, int p, int d)
{
D[c] = d;
if (d>0)
P[c].push_back(p);
for (int i=1; 1<<i<=d; i++)
P[c].push_back(P[P[c][i-1]][i-1]);
for (int e: E[c])
if (e != p)
f(e, c, d+1);
};
f(root, -1, 0);
}
int query(int a, int b)
{
if (D[a]>D[b])
swap(a, b);
int d = D[b]-D[a];
for (int i=0; d>0; i++)
{
if (d&1)
b = P[b][i];
d >>= 1;
}
if (a==b)
return a;
int i = 0;
while (1<<(i+1)<=D[a])
i++;
for (; i>=0; i--)
if (1<<i<=D[a] && P[a][i]!=P[b][i])
{
a = P[a][i];
b = P[b][i];
}
if (D[a]>0)
a = P[a][0];
return a;
}
};
int main()
{
int N, Q;
cin>>N>>Q;
vector<vector<int>> E(N), C(N), D(N);
for (int i=0; i<N-1; i++)
{
int a, b, c, d;
cin>>a>>b>>c>>d;
a--;
b--;
c--;
E[a].push_back(b);
C[a].push_back(c);
D[a].push_back(d);
E[b].push_back(a);
C[b].push_back(c);
D[b].push_back(d);
}
vector<int> X(Q), Y(Q), U(Q), V(Q);
for (int i=0; i<Q; i++)
{
cin>>X[i]>>Y[i]>>U[i]>>V[i];
X[i]--;
U[i]--;
V[i]--;
}
LCA lca(E, 0);
vector<int> S(N); // sum(D)
vector<map<int, int>> CN(N); // CN[v][c]: count(color==c)
vector<map<int, int>> CD(N); // CD[v][c]: sum(d if color==c)
for (int i=0; i<Q; i++)
{
CN[U[i]][X[i]] = 0;
CN[V[i]][X[i]] = 0;
CN[lca.query(U[i], V[i])][X[i]] = 0;
}
int TS = 0;
vector<int> TN(N-1);
vector<int> TD(N-1);
function<void (int, int)> f = [&](int c, int p)
{
S[c] = TS;
for (auto it: CN[c])
{
int col = it.first;
CN[c][col] = TN[col];
CD[c][col] = TD[col];
}
for (int i=0; i<(int)E[c].size(); i++)
if (E[c][i]!=p)
{
int col = C[c][i];
TS += D[c][i];
TN[col]++;
TD[col] += D[c][i];
f(E[c][i], c);
TS -= D[c][i];
TN[col]--;
TD[col] -= D[c][i];
}
};
f(0, -1);
for (int i=0; i<Q; i++)
{
int a = lca.query(U[i], V[i]);
int s = S[U[i]] + S[V[i]] - 2*S[a];
int n = CN[U[i]][X[i]] + CN[V[i]][X[i]] - 2*CN[a][X[i]];
int d = CD[U[i]][X[i]] + CD[V[i]][X[i]] - 2*CD[a][X[i]];
cout<<s-d+n*Y[i]<<endl;
}
}
O - Enclosed Points
998244353で割った余りを出力してください
サンプル問題では初めて出てきたけれど、この割った余りを出力してくださいというのは競技プログラミングで良く出てくる。言語によっては多倍長整数が無く、64ビットより大きい整数を扱うのが大変なので、扱う整数を64ビット以下に収めたいらしい。
M=998244353として、足し算、掛け算は、計算するごとにそれぞれ(a+b)%M、a*b%Mとすれば良い。引き算は、C++の場合負の数の剰余が負になるので、(a-b+M)%Mとしなければならない。Pythonならば結果が0以上となるので、(a-b)%Mで良い。割り算は、逆数を掛ける。$a$の逆数とは$ab=1 \mod M$となるような$b$。フェルマーの小定理から、$a^{M-1}=1 \mod M$なので、$b=a^{M-2}$となる。冪乗はこんな感じで高速化できる。$x^{20}=x^{16}x^4$。$x^2=xx$、$x^4=x^2 x^2$、$x^8=x^4 x^4$、…。
サイズ$N$の集合$S$の空集合ではない部分集合は$2^N-1$個ある。$N\leq 2\times 10^5$の制約下で律儀に計算するのはどう考えても無理である。ひっくり返して、「各点について、その点を含むような部分集合は何個あるか？」を考える。これも大変なので、さらに補集合を考え、「各点について、その点を含まないような部分集合は何個あるか？」とする。これはその点について、全ての点がその点の上下左右いずれかだけにある部分集合である。ただし、左上、右上、左下、右下は2回数えているので、その分を引く。包除原理的な考え方。
で、各点について左上にあるような点の個数を数えるのは、座標圧縮とBinary Indexed Tree（BIT）を組み合わせるとできる。「アルゴリズム」実技検定っぽさが出てきた。
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <utility>
#include <algorithm>
using namespace std;
// 座標圧縮
vector<int> comp(vector<int> V)
{
set<int> S(V.begin(), V.end());
map<int, int> M;
int i = 0;
for (int v: S)
{
M[v] = i;
i++;
}
for (int &v: V)
v = M[v];
return V;
}
// Binary Indexed Tree
class BIT
{
int n;
vector<int> v;
public:
BIT(int n_) {
n = 1;
while (n < n_)
n <<= 1;
v = vector<int>(n);
}
// a[i] += x
void add(int i, int x) {
for (; i<n; i|=i+1)
v[i] += x;
}
// return a[0]+a[1]+…+a[i-1]
int sum(int i) {
int s = 0;
for (i--; i>=0; i=(i&(i+1))-1)
s += v[i];
return s;
}
};
int main()
{
int N;
cin>>N;
vector<int> x(N), y(N);
for (int i=0; i<N; i++)
cin>>x[i]>>y[i];
x = comp(x);
y = comp(y);
vector<pair<int, int>> T;
for (int i=0; i<N; i++)
T.push_back(make_pair(x[i], y[i]));
sort(T.begin(), T.end());
for (int i=0; i<N; i++)
x[i] = T[i].first,
y[i] = T[i].second;
vector<int> UL(N), UR(N), DL(N), DR(N);
BIT bit(N);
for (int i=0; i<N; i++)
{
int s = bit.sum(y[i]);
UL[i] = i-s;
DL[i] = s;
bit.add(y[i], 1);
}
bit = BIT(N);
for (int i=N-1; i>=0; i--)
{
int s = bit.sum(y[i]);
UR[i] = N-1-i-s;
DR[i] = s;
bit.add(y[i], 1);
}
long long M = 998244353;
vector<long long> P(N+1); // pow(2, i)
P[0] = 1;
for (int i=1; i<=N; i++)
P[i] = P[i-1]*2%M;
long long ans = 0;
for (int i=0; i<N; i++)
{
ans += (P[N]-1)
- (P[UL[i]+UR[i]]-1)
- (P[DL[i]+DR[i]]-1)
- (P[UL[i]+DL[i]]-1)
- (P[UR[i]+DR[i]]-1)
+ (P[UL[i]]-1)
+ (P[UR[i]]-1)
+ (P[DL[i]]-1)
+ (P[DR[i]]-1);
ans = (ans%M+M)%M;
}
cout<<ans<<endl;
}