ACLがVS2019で動かない
遂にACLデビュー！と思いきや、動かなかった、そんなあなたに
_umul128が見つからなかった場合
エラーメッセージ
・C3861 '_umul128': 識別子が見つかりませんでした
解決法
ビルド→構成マネージャー を開きます。
ここで、アクティブソリューションプラットフォームをx86からx64に変更します。
備考
_umul128は64bit環境にしか存在しないっぽいです。
式が定数に評価されなかった場合
エラーメッセージ
・C2131 式は定数に評価されませんでした
解決法
プロジェクト→(プロジェクト名)のプロパティ→C/C++→全般 を開きます。
SDLチェックをいいえに変えます。
備考
VSでscanfを使いたいときに同じことをしないと動かない場合があります。
終わりに
公式の強い系ツール、動かないがち
機械的に列を木に拡張するテク
はじめに
多分どっかで既出です。
お気持ちの説明
列上で行える累積和的な操作( f(x~y)=f(x~z)+f(z~y) みたいになっているもの)で構成される操作を、木上のパスで行うテクです。こういう操作でなくても物によっては出来ることもあります。
「根が関係ないような問題でも、根を適当に決めるとそこからの相対値でクエリを求める事が出来る」という風に思っておくと分かりやすいかもしれません。
具体的に説明するのは難しいので、例をいくつか出します。
X-Yパスの長さを求める
列上問題であれば、累積和配列を持って B[Y]-B[X] (X < Y) という風にすると求める事ができます。
木上クエリに拡張した場合、頂点0を根とすると
0-Xパスの長さ + 0-Yパスの長さ - 2*(0-LCA(X,Y)パスの長さ)
とできます。（これはただのダブリングでもできるので嬉しさはありません）
（このようにして木上のパスの長さを求める問題に、JOIの道路整備などがあります。）
モンスターショー
列上のクエリの場合だと、集める頂点をTとしたとき、
(スライム全ての座標の値の総和) - ( T*(Tよりも前の列にいるスライムの数) - Tよりも前のスライム全ての座標の値の総和) ) - ( T*(Tよりも後ろの列にいるスライムの数) )
とすることによって求める事ができます。
これを木上に拡張した場合はこの問題の解説を読んでください。
まとめ
「列上で、累積和みたいな操作と一点更新・一点取得で出来る操作をする問題」があったときに、この列を木上の1-tパスとみなすことによって機械的に木に拡張することができます。
累積和のところはHLDなどを使うことで行えることが多いと思います。
適当な列上の操作を思いつけるだけで難しい問題になるので、作問時に役立ちます。
また、木上の変なことをする問題を見た時に、「とりあえず根を固定してそこからの相対パスで考えよう」という発想を持っておくと、問題が解きやすくなります。
最後に、こういう風に機械的に作られた問題は面白くないものが多いので、真面目に作問をしたほうが良いと思います。
また、LinkCutTreeなどで殴られて悲しい思いをする事もあります。
ただ、300点問題に出来そうな列上のクエリ問が生えたときにこの記事の存在を思い出してもらえると、作問ストックに高難度が仲間入りするかもしれません。
yukicoder No.1170 Never Want to Walk
はじめに
問題が全体的に実装軽めで面白かったです。
想定解を思いつきはしたんですが、「区間のマージやりたくない…」と思って捨ててしまいました。 imosとか使えば普通に出来るんですけどね…
考察
区間に辺を張ることが出来ればよいことが分かります。
ここで、熨斗袋さんの区間に辺を張るテクのツイートを思い出すと解けます。
参考
セグ木の形にして区間に辺を張るテク
— 熨斗袋 (@noshi91) 2019年11月9日
頂点 +N 個
辺 +N+ElogN 個 pic.twitter.com/Xrw5y9bq2Z
セグ木っぽくしたほうが早いんですが、実装が面倒だったので平方分割で書きました。
想定のほうが実装も計算量も軽いです。
実装の軽い説明をすると、[0,n)は頂点の頂点、[n,n+sqrt(n))を区間の頂点にしてunionfindをしています。 最後に集合に含まれる区間の数を答えから引いてやる必要があります。
実装
yukicoder No.253 ロウソクの長さ
インタラクティブ練習に。 二分探索はすぐわかるんですが、そこからが面白かったです。
writerの想定解とは違ったので書きました。（当初の想定解かな？）
考察
二分探索をとりあえずすると、小さい値の時、質問をしているうちに燃え尽きてしまうので詰みます。 これを回避する方法を考えることになります。
まず最初に二分探索のクエリを投げることを考えます。
そうすると、次はクエリに1を投げる必要があります。ここで聞かないと二度と1，2の判別ができなくなるからです。 その次には二分探索のクエリを奈が得ることができます。なぜなら、その次に1をクエリに投げることで、3，4の判別をする事が出来るからです。
ここからわかることは、1をクエリに投げることによって(その時の回数)と(その時の回数+1)を探索することができ、詰むまでに1回分の猶予が生まれるので、この間に二分探索のクエリをすればよいということです。
これを繰り返すと詰むことなく二分探索をする事が出来ます。
コード
int judge(int k) { cout << "? " << k << endl; return read(); } void solve() { int ok = 1, ng = 1e9 + 1, mid; int times = 0; while (ng - ok > 1) { mid = (ok + ng) / 2; int num; if (mid - times >= 0) { num = judge(mid - times); if (num == 1) ok = mid; else if (num == 0) { ok = mid; break; } else ng = mid; times++; } num = judge(1); if (num == 0) { cout << "! " << times + 1 << endl; return; } else if (num == -1) { cout << "! " << times << endl; return; } times++; } cout << "! " << ok << endl; } signed main() { solve(); }
JOI2013sp Day1 Bus Tour＜怪＞
はじめに
これはクソ解法…ということもないかもしれません。
本番でこれを書いてもいいかも？
考察
ぱっとみめっちゃ辛くて、何が辛いって乗換が多いのが辛いです。
ただ、N<=1000であることから、バス運行路の組(i,j)についてそれぞれ見る必要のある乗換場所を考えます。
縦と縦or横と横で被っている場合はその被っている区間の端2か所だけ見ればよく、縦と横で被っている場合はその点だけ見ればよいです。
結論として、乗り換えが必要な組はそれぞれの(i,j)で最大4つなので、O(N2)で抑えられることが分かります。
本当はそれぞれの頂点に乗り換えの組をメモしたほうがいいんですが、面倒くさいのでさぼっても多分ばれません。頂点にメモするのは乗換の組のそれぞれのバスにすることにします。
これでダイクストラをする頂点が構成できたので、あとは適当にダイクストラすればよいです。
具体的に説明すると、a[x][y]=頂点(x,y)でバスに乗れる状態になった最初の時としてダイクストラをします。
境界判定が結構大変なので頑張る必要があります。
ソースコード
JOI2018ho-C Dango Maker 裏解法
はじめに
これはクソ解法です。
本番でこんなの書いてたら春合宿に落ちちゃうので、ちゃんとした解き方をしましょう。
考察
まず、図を書いてみると、どれか1つで団子を作れる場合、斜め方向に連結していくことが分かります。
という感じ。
依存関係を考えるとこの斜めごとに独立に考えられるので、UnionFindで集合にして管理をすることにします。（←ここから狂い始める
さて、こうして斜めごとの集合に分けられたものは、さらに2種類に分けることができます。
この画像の黄色と、青色のところの2種類です。緑はどちらにも属しています。
上の方から使う向きを決めていった時を考えます。
Gが真ん中にある青の部分は、全部縦にも全部横にもできるので、別で考えることにします。
そうすれば、残りで考える必要があるのは沢山の黄色です。
縦を使えば横が使えなくなり、横を使えば縦が使えなくなるので、縦と横のどっちか多い方を使えばいいと思うかもしれませんが、黄色が大量にあることを考えると、上の方と下の方で使うべき目がばらばらになるかもしれません。
これをDPで解きます。
dp[i][j]=i番目の連結成分を右上から見ていき、最後に使ったRGWがjの向きだった時の最大値
dpの遷移式がわりあい複雑なので注意する必要があります。
実装方針
右上から全部DFSとかしてもできるんでしょうが、辛すぎて死んじゃうので、UFで連結成分ごとに分けて、青を全部識別した後、右上から順に見つかった黄色から全部辿っていき、DPを更新していくのが楽です。（楽ではない）
実装
かなり大変です。
最後に
誰も読まないと思っているのでかなり雑です。
もしこれを理解したいという奇特な人がいたなら、
からTwitterを特定して、DMをください。
JOI2012-sp-Day1 JOI旗
問題文
https://atcoder.jp/contests/joisc2012/tasks/joisc2012_joi_flag
解説から問題文に飛べます
問題概要
(2k)*(2k)サイズのマス目があり、これをJOI旗に塗る。
N点の文字は既に決まっていて、この文字を変えるためには1か所につきコスト1がかかる。
全てのマスを塗るための最小コストは何？
考察
素直に考えると、それぞれのマス目において4!通りの色の塗り方を試して、小さいマス目のほうに再帰をするという風な解法になるだろう。
ただ、これをしていると計算量が爆発してしまう。
ここで、再帰をしていった先で一文字も決定していない(=どういう風においてもよい）場合を考えると、これは枝狩りをしてよい。
計算の必要のある(=枝狩りをしてはいけない)マスを考えると、それぞれの文字について、K通りの場面にしか現れないので、計算しなくてはならない場面はN*K以下になり、これは十分計算可能である。
よって、再帰の時に、各範囲について、その中に何個のJ,O,Iで決定しているマスがあるか、が判別できればよいことになる。
これは、それぞれの文字が含まれる(2t)*(2t)の範囲を列挙して記録すればよく、mapなどを使えばできる。
注意するべきこととして、毎回愚直に再帰するとTLEするので、メモ化をしないといけない。
ソースコード
#include<bits/stdc++.h> using namespace std; #define fs first #define sc second #define H pair<int, int> #define P pair<int, H> #define Q(a,b,c) make_pair(a,H{b,c}) #define vec vector #define pb push_back #define rep(i,n) for(int i=0;i<(n);i++) const int inf=1e9; int k, n; H a[2000]; char b[2000]; map<P, vec<int>>mp2; map<P, vec<int>>mp; map<P, int>dp; signed main() { cin >> k >> n; rep(i, n) { cin >> a[i].fs >> a[i].sc >> b[i]; a[i].fs--; a[i].sc--; int g = 1; rep(t, k + 1) { int x = a[i].fs / g * g, y = a[i].sc / g * g; mp2[Q(x, y, t)].pb(i); g *= 2; } } for (auto g : mp2) { mp[g.fs] = vec<int>(3, 0); for (auto f : g.sc) { int t = 0; if (b[f] == 'O') t = 1; else if (b[f] == 'I') t = 2; mp[g.fs][t]++; } vec<int>b(3, 0); rep(i, 3)rep(j, 3) { if (i != j) b[i] += mp[g.fs][j]; } mp[g.fs] = b; } auto G = [&](int x, int y, int z, int rank)->int { if (mp.find(Q(x, y, rank)) == mp.end()) return 0; return mp[Q(x, y, rank)][z]; }; function<int(int, int, int)>F = [&](int x, int y, int rank)->int { if (dp.find(Q(x, y, rank)) != dp.end()) return dp[Q(x, y, rank)]; if (rank == 0) return 0; if (mp.find(Q(x, y, rank)) == mp.end()) return 0; int ret = inf; vec<int>c; rep(i, 4) c.pb(i); vec<H>d = { {0,0},{0,1},{1,0},{1,1} }; do { int sum = 0; rep(i, 4) { if (c[i] == 0) { sum += F(x + d[i].fs * (1ll << (rank - 1)), y + d[i].sc * (1ll << (rank - 1)), rank - 1); } else { sum += G(x + d[i].fs * (1ll << (rank - 1)), y + d[i].sc * (1ll << (rank - 1)), c[i] - 1, rank - 1); } } ret=min(ret, sum); } while (next_permutation(c.begin(),c.end())); return dp[Q(x, y, rank)] = ret; }; cout << F(0, 0, k) << endl; }
