はまやんはまやんはまやん

hamayanhamayan's blog

Max Sum Counting [AtCoder Beginner Contest 216 F]

https://atcoder.jp/contests/abc216/tasks/abc216_f

前提知識

解説

https://atcoder.jp/contests/abc216/submissions/25449760

DPが分かっていることは前提なので勉強してきてほしい。

何から始めるのか

手がつかない場合は問題の弱点を探るのが良い。
今回は条件のうち、maxの上限が5000である部分が弱点となりうる部分である。
maxの上限が5000であるということはBの総和の上限も5000まで考えればいいことになる。
この条件は考察するうえでとても有用な条件であるように見える。

まあ、ここまではいいとして、ここからちょっと思考の飛躍が必要となる。
条件のmaxの値は選択された値の中での最大値によって決まり、
「それより小さい数についてはどのように選択されても変化しない」
といえる。
ここがとても重要な部分で、この「どのように選択されても変化しない」という部分にDPの同一視が適用できそうである。
さて、小さい数について、細かな状態は無視したいので、配列をまずはソートすることにする。
AとBを1つのグループにまとめてAでソートしておく。
max, sumや部分集合の選択方法に順番は影響しないので、ソートしても答えは変化しない。
この状態でDPを考える。

DP定義

dp[i][Btot] := i番目まで選択が確定していて、かつ、「i番目を選択していて」、かつ、選択した要素のBの総和がBtotである組合せ

このDPを更新していくことを考える。
これを貰うDPで実装していくことを考えると、

dp[to][Btot]の更新はto未満である全てのcuに対してdp[cu][Btot - B[to-1]]の総和

が更新ルールとなる。
これをそのまま実装するとO(N2 Bmax)になるので間に合わない。
更新時に利用している値は、toを1から順番に計算していることを考えるとdp[to未満の全て][とある値]の総和を取得していることになる。
これは事前に計算することができる。
よって、
tot[x] := dp[これまで][x]の総和
と定義して、dp[to][any]の更新が終わった直後に、totにその値を入れることで、
dp[to][any]を更新→tot[x]を更新→更にそれを使ってdp[to+1][any]を更新→…みたいな感じに高速に計算ができる。
この辺は累積和を使った更新最適化と捉えることもできる。
https://blog.hamayanhamayan.com/entry/2017/03/20/234711

答えを取得する

これでdp[i][Btot]について考えると、maxの値はA[i-1]になっているので、BtotがA[i-1]以下であるものが条件を満たすものになる。
なので、全てのdpの要素dp[i][Btot]についてBtot≦A[i-1]である組合せの総和を取れば答えになる。

int N;
int A[5010], B[5010];
pair<int, int> AB[5010];
mint dp[5010][5010];
mint tot[5010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cin >> B[i];
    rep(i, 0, N) AB[i] = { A[i], B[i] };

    sort(AB, AB + N);

    dp[0][0] = 1;
    tot[0] = 1;
    rep(to, 1, N + 1) {
        rep(Btot, 0, 5010) if (AB[to - 1].second <= Btot) dp[to][Btot] = tot[Btot - AB[to - 1].second];
        rep(Btot, 0, 5010) tot[Btot] += dp[to][Btot];
    }

    mint ans = 0;
    rep(to, 1, N + 1) rep(Btot, 0, AB[to - 1].first + 1) ans += dp[to][Btot];
    cout << ans << endl;
}

Amusement Park [AtCoder Beginner Contest 216 E]

https://atcoder.jp/contests/abc216/tasks/abc216_e

解説

https://atcoder.jp/contests/abc216/submissions/25449841

この問題は貪欲法で解ける。
勉強熱心な方はDPを思いついたかもしれないが、たぶん正常な反応だと思う。
貪欲法で解けそうな問題が実際はDPでしたというパターンも、逆のパターンもかなり見てきた。

今回は貪欲法の方針を見つけるのはそれほど難しくなく、実装がちょっと大変。

貪欲法の方針

貪欲法で解きますという風な前提があれば、その方針を見つけることはそれほど難しくないだろう。
楽しさを最大化するには、「各操作時に楽しさが最大のアトラクションを選ぶことを繰り返す」という貪欲をすればいい。
その貪欲法で問題ないかという見積もりをする必要があるが、パッと考えた感じ反例が思い浮かばず、
かなり自明な貪欲法に思えたのでそのまま突っ切って実装してACした。
正直これで何回も痛い目を見ているのだが、貪欲法の見積もりって難しいですよね…
基本DPから考えるといいと思います。で、不可能になったら貪欲法という感じで。

実装

さて、少し回り道をしたが、「各操作時に楽しさが最大のアトラクションを選ぶことを繰り返す」で貪欲法を実践する。
言われたまま実装をするとKの値は大きいのでTLEしてしまう。
大きい数を減らしていくと、次に大きい数と一致するときが来る。
この間は地道に-1するのではなく一気に減らすような工夫をすると貪欲法を高速化できる。
このように一定の操作が行われる部分については計算で省略をしながら高速に貪欲法をやっていく。
Aの値は大きい順で使用するので、降順ソートした上で、先頭から使用していこう。

サンプル1の例で考えてみよう。
先頭が102で次が100なので、その間の102+101が使用されることになる。
その次は、2番目が100でその次が50なので、100+99+98+...+51が使用されることになる。
ただ、2回目は1番目が2番目と同じ値にまで減らされているので(100+99+98+...+51)×2が使用される感じになる。
なので、基本的には(A[i] + ... + (A[i + 1] + 1))×(i + 1)を足していけばいいことになる。
iは0始まり、0-indexedで表記している。

このように等差数列の和を利用するので、自作のライブラリtousa_sumを持ってきて計算した。
高校生で「等差数列の和」は習うのだが、競プロやる中学生は知ってそうだな…
まあ、忘れている社会人含めて「等差数列の和」でググれば式は出てくるのでそれを使って実装すればいい。
自分の実装が気になるなら、提出URLに飛んで見てみてほしい。

半端な場合はどうする?

基本的には上記の方針でKを減らしていけばいいが、いつか中途半端になってしまう場合がある。
この場合には、これまでに数が揃っている個数分のA[i]が何回分同時に-1できるかというのを特定する。
これはKを(i+1)で割った答えdになる。
d回分は等差数列の和で計算する。
Kを(i+1)で割った余りmが、残った回数になるので、あとはその分だけ足し合わせて答えが出来上がる。

ll N, K, A[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> A[i];
    sort(A, A + N, greater<ll>());

    ll ans = 0;
    rep(i, 0, N) {
        ll diff = A[i] - A[i + 1];

        ll cnt = 1LL * diff * (i + 1);
        if (cnt <= K) {
            K -= cnt;
            ans += tousa_sum(A[i], -1LL, diff) * (i + 1);
        }
        else {
            ll d = K / (i + 1);
            ll m = K % (i + 1);
            ans += tousa_sum(A[i], -1LL, d) * (i + 1);
            ans += (A[i] - d) * m;
            K = 0;
        }
    }
    cout << ans << endl;
}

Pair of Balls [AtCoder Beginner Contest 216 D]

https://atcoder.jp/contests/abc216/tasks/abc216_d

解説

https://atcoder.jp/contests/abc216/submissions/25449941

貪欲法というかシミュレーションで解く問題。
今回は目標を達成するには、ボールが取り出せるならどんな順番でもいいので取り出していって、
最後に全部取り出せれば達成可能と判定する方針で実装していく。
なので、高速にこのことをシミュレーションしていくことを考える。

このように選択肢があるように見えて、どんな方針でやっても最適解になるような問題がある。
これも正当性判断が難しいですが、とりあえず選択肢が2つ以上あるときに、操作の順番を変えることで
有利な状況が作れそうかというのを例を作りながら確認していくしかないと思う。
点数を見て、実装が大変な系かなという判断を下したのかも。

高速シミュレーション

ボールを取り出す際に毎回筒を確認して、同じボールがあるかを探していく方針はN回取り出す必要があって、
雑に計算すると毎回M個の筒を確認する必要があるので、O(NM)は間に合わない感じがする。
なので、上手くメモを残しながら取り出せるボールというのを高速に取ってくるようにする。
以下、自分の実装について説明する。

以下のようなデータ構造を用意する。

que := 「現在取り出せる同色のボールの組」を集めたキュー
available[i] := 現在色iのボールが先頭にある筒の番号

例えばi番目の筒の先頭がA[i].front()であるとすると、
available[ A[i].front() ] = i
という風に更新することができる。
だが、更新時に既に値があった場合は、他にも筒の先頭に同じ色のボールがあるということになるので、
取り出すためにqueというキューに筒の番号を追加する
que.push({ i, available[ A[i].front() ] })
自分の番号iと、前もってメモっておいた同色が先頭にある筒の番号available[ A[i].front() ]をキューに入れている感じ。
この実装を

setAvailable(ai) := 筒A[ai]の先頭を評価する

として実装している。
キューを1つずつ処理していくことで同色の2組を削除していくが、2つの筒からボールが取り出されるので
その次のボールをsetAvailableでavailable配列の更新やqueへの追加を行っていく。
これでボールを取り出して、差分として新たに2つのボールが出てくるので、それと先頭が一致しているものがないか確認というのを
上手いこと差分だけを計算することで高速に処理していく。

最後に

シミュレーション後にすべての筒が空になっていればYes。
筒の先頭を評価するときに空の場合は無視することに注意。
あと、筒の管理にdequeを使っている。

int N, M;
deque<int> A[201010];
int available[201010];
//---------------------------------------------------------------------------------------------------
queue<pair<int, int>> que;
void setAvailable(int ai) {
    if (A[ai].empty()) return;
    if (0 <= available[A[ai].front()]) {
        que.push({ available[A[ai].front()] , ai });
    }
    else available[A[ai].front()] = ai;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) {
        int k; cin >> k;
        rep(j, 0, k) {
            int a; cin >> a;
            a--;
            A[i].push_back(a);
        }
    }
    rep(i, 0, N) available[i] = -1;

    
    rep(i, 0, M) setAvailable(i); {
        
    }
    while (!que.empty()) {
        int i1, i2;
        tie(i1, i2) = que.front();
        que.pop();

        A[i1].pop_front();
        setAvailable(i1);
        A[i2].pop_front();
        setAvailable(i2);
    }

    bool ok = true;
    rep(i, 0, M) if (!A[i].empty()) ok = false;

    if (ok) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Many Balls [AtCoder Beginner Contest 216 C]

https://atcoder.jp/contests/abc216/tasks/abc216_c

関連知識

解説

https://atcoder.jp/contests/abc216/submissions/25449969

この問題は2進法についての理解があると解法が思いつきやすい。
このような構築問題は方針がいくつかあるが、Nを見ると計算量的にlogNでやらないとという感じがあるので、
このあたりから2進法が分かっていなくても解けるのかもしれない。
2進法についてはググって調べてきてほしいが、知らなくても解説は読める(はず)

操作を逆に見てみる

合計120回とあるが、とりあえず最適っぽい方針も立てられないと前進しない。
今回は実は操作を逆に見てみることで方針が立てやすくなる。
つまり、魔法Aを使うと-1されて、魔法Bを使うと÷2されることになる。

5 -A-> 4 -B-> 2 -B-> 1 -A-> 0

のような感じになるが、これは丁度順番を逆転させると元の問題に帰着される。
なので、NをA,Bの操作をして0になる様にやっていこう。

構築問題のルールはシンプルに

構築問題に共通で言えるアドバイスとして、なるべくシンプルなルールを採用することである。
複雑だと大体バグるし、ちょっと踏みとどまってシンプルなルールを探す方が期待値が高いことが多い(体験上)。
よって、シンプルなルールを考える。
以下のルールで今回はACできる。

  • 2で割り切れない場合は魔法Aをやる(魔法Aをやるしかないけど)
  • 2で割り切れる場合は魔法Bをやる

再掲すると、

5 -A-> 4 -B-> 2 -B-> 1 -A-> 0

これはこのルールで作られている。
どんな数であってもこのルールを適用することで0になることが分かるだろう。
答える前に魔法の打ち方を反転させるのを忘れずに。

120回に収まるのか?

なるべく回数を抑えるためには魔法Bを多く使うことが重要になる。
今回の方針で重要なのは魔法Aが連続することはないという部分である。
魔法Aをやれば必ず2で割り切れる状態になるので最低2回に1回は魔法Bが行える。
魔法Bを1回やれば2分の1以下にできるし、2回やれば4分の1以下にできるし、3回やれば8分の1以下である。
極端に小さくなっていくことが分かると思う。
実際はlogNになるというか、2進法のビット数分になるというか、具体的には60回くらいで0にできる。
で、毎回魔法Aを挟んでも120回くらいになって間に合うという見積もりである。

ll N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    string ans = "";
    while (1 <= N) {
        if (N % 2 == 1) {
            ans += "A";
            N--;
        }
        else {
            ans += "B";
            N /= 2;
        }
    }
    reverse(all(ans));
    cout << ans << endl;
}

倉庫番ロボット [パソコン甲子園2020 予選 I]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0436

解説

https://onlinejudge.u-aizu.ac.jp/solutions/problem/0436/review/5811448/hamayanhamayan/C++14

解くのにかなり手こずった。難しかった。
ちょっとだけ遠回りも記しておこう。

遠回り

ダイクストラで解けないか考えて実装までしたがTLEした。
xy座標が[0,300]の範囲の点を状態として、遷移は上下左右の4移動と、移動可能なななめ移動である。
ななめ移動部分は無限に行けそうに見えて、実は

  • とあるy座標に対してx座標が[0,300]のどれか
  • とあるx座標に対してy座標が[0,300]のどれか

のどちらかとなる。
なので、遷移は301×2+4になるので、状態数とそこからの遷移で考えると、まあ、間に合わないのだが、
aojなので間に合ったりしないかなーとか思ったが当然のようにダメでしたね…

方針はあってる

ちょっと他の解法見ながらズルをしながら考えると、遷移を貪欲に絞ることが求められるようだ。
最短経路を取る問題は始点から終点までピンと糸を貼るような問題になるので、
一旦戻るような遷移にはならない。
一旦戻って(見た目勢いをつけて)移動しているようなものは糸を引っ張るようにすると、
戻らない経路に移る。
よって、始点から終点まで移動する場合、必ず終点の方向に移動することになる。
具体的には、x0≦x1、y0≦y1であるときに、遷移(a,b)から(c,d)を考えると、
a≦cかつb≦dを満たすことになる。
これにより遷移が一方向になり、遷移によってループすることがなくなる。
つまり、ダイクストラというよりDPで計算ができるようになる。

実装に落とし込んでいく

ここまで分かれば、それほど難しくない。
必須ではないが、問題を簡単化するためにx0≦x1、y0≦y1となる様に座標を調整しておこう。
具体的にはx0>x1であれば、図面を反転させることで、位置関係を変化させずに大小関係を修正できる。
反転させると、座標が負の数になってしまうので、+301で平行移動して正の座標にしておこう。
301とするのは壁の場所を調整するためである。

DP

dp[y][x] := (x0, y0)から(x,y)に移動する最短距離

としてDPを計算していく。
移動は常に単調増加していく感じで実装する。

dp[y][x]からdp[y+1][x]とdp[y][x+1]に遷移する。
これに加えて、y座標が奇数であれば、棚の上側にいるので、右上へのななめ移動ができる。
x座標が奇数であれば、棚の右側にいるので、これも右上へのななめ移動ができる。
ななめ移動はsqrt関数をうまく使ってコスト計算をする。

dp[y1][x1]が答え。

int X0, Y0, X1, Y1;
double dp[305][305];
const int MA = 302;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> X0 >> Y0 >> X1 >> Y1;

    if (X0 > X1) X0 = - X0 + 301, X1 = - X1 + 301;
    if (Y0 > Y1) Y0 = - Y0 + 301, Y1 = - Y1 + 301;

    rep(y, 0, MA) rep(x, 0, MA) dp[y][x] = inf;
    dp[Y0][X0] = 0;
    rep(y, Y0, Y1 + 1) rep(x, X0, X1 + 1) {
        chmin(dp[y + 1][x], dp[y][x] + 1);
        chmin(dp[y][x + 1], dp[y][x] + 1);
        if (y % 2 == 1) rep(xx, x + 1, X1 + 1) chmin(dp[y + 1][xx], dp[y][x] + sqrt(1 + (xx - x) * (xx - x)));
        if (x % 2 == 1) rep(yy, y + 1, Y1 + 1) chmin(dp[yy][x + 1], dp[y][x] + sqrt(1 + (yy - y) * (yy - y)));
    }

    printf("%.10f\n", dp[Y1][X1]);
}

高速道路網 [パソコン甲子園2020 予選 H]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0435

前提知識

解説

https://onlinejudge.u-aizu.ac.jp/solutions/problem/0435/review/5811215/hamayanhamayan/C++14

まずは問題の整理をしていく。
与えられている地点と道路はグラフとしてマッピングすることができる。
この条件で面白い部分がある。

「どのように道路をたどっていっても、同じ地点に戻ることはない。」

これはグラフにループ構造が無いことを示している。
よって、このグラフはDAGであることがこの条件から分かる。
DAGはループの無い有向グラフのことであるのだが、DAGであることの有用性の1つとしてDPが行えるということがある。

この問題の前に

DAG上での問題という前提で考えると何回も似たような問題を見てきた。
トポロジカルソートをした上で、その順番でDP更新をしていく。
今回は2種類のDPを作っていくのだが、ちょっと別の問題を使って理解を深めていくことにしよう。

「始点から各地点に行くまでに何通りの移動方法があるか」という問題を考えてみる

「始点から各地点に行くまでに何通りの移動方法があるか」

これはDPで計算が可能である。

dp[cu] := 始点から地点cuに行くまでに何通りの移動方法があるか

そのまんまなDPテーブルであるが、これを計算していけばいい。
トポロジカルソートをして、ソート順にDPを更新していく。
最初はdp[0] = 1として、更新時は地点cuから地点toへ移動可能だとするとdp[to] += dp[cu]とすればいい。

まず、これが理解できる所まで来ないと、この問題を理解することは難しい。
DPをしっかり理解していることと、トポロジカルソートをしっかり理解していることが必要なので、
そちらを学習してくるのもいいかもしれない。

では、これは理解できているものとして、もう少し進んだ問題を考える。

「始点から各地点に行くまでの全ての経路の長さの和は」

以下のように2つのdpを使って計算していこう。

comb[cu] := 始点から地点cuに行くまでに何通りの移動方法があるか
tot[cu] ;= 始点から地点cuに行くまでの全ての経路の長さの和

tot[cu], comb[cu]がすでに計算されているものと仮定して、tot[to], comb[to]をどう計算するか考えよう。
combについては先ほどと同じなので、comb[to] += comb[cu]でよい。
問題はtotであるが、これまでの経路の長さの和は考慮されるべきなので、tot[to] += tot[cu]は決まっている。
これで考慮されていない長さはcuからtoに移る長さの分となる。
長さは1で固定で、本数は丁度comb[cu]と一緒になっている(!)
なので、考慮されていない長さの分も足してtot[to] += tot[cu] + comb[cu]で更新ができる。
初期状態はtot[cu] = 0, comb[cu] = 1で始まる。

元の問題

さて、やっと元の問題に戻れる。
今回求めたい問題は「始点→地点i→終点」となる全ての経路の長さの和を求める問題である。
これを分割して求めることにする。
始点からの経路と終点への経路に分けて計算する。

始点→地点iに至る全ての経路の長さの和を求めるには、1つ前にやった問題をやれば求めることができそうである。
仮に地点i→終点の移動方法が1通りである場合は、1つ前にやった問題の結果をそのまま使用すればいいのだが、
複数ある場合は、その組み合わせ分だけ、その経路の長さの和が使われることになる。
なので、地点i→終点の移動方法も計算したくなる。

始点→地点iの計算は先ほどやったが、同じ問題を地点i→終点で計算するにはすべての辺の方向を逆転させて
同じ計算をすればいい。
辺の方向を逆転させることで経路が変化することはないので、これで問題ない。

答えのアルゴリズム

長々書いてしまった。答えを簡潔にここから書き始める。

始点→地点iについて、comb, totを計算する。これをcomb1, tot1としておく。
次に辺の方向を逆転させて、同じ計算をして、
地点i→終点について、comb, totを計算する。これをcomb2, tot2としておく。

各地点iについて、
始点→地点iの全ての経路の長さの和はcomb1[i] * tot2[i]で計算ができ、
地点i→終点の全ての経路の長さの和はcomb2[i] * tot1[i]で計算ができるので、
「始点→地点i→終点」となる全ての経路の長さの和はcomb1[i] * tot2[i] + comb2[i] * tot1[i]となる。

int N, M;
int u[2510], v[2510];
//---------------------------------------------------------------------------------------------------
pair<vector<ll>, vector<ll>> getCombination(int root) {
    vector<int> E[50];
    TopologicalSort ts(N);
    vector<int> ord;

    rep(i, 0, M) {
        E[u[i]].push_back(v[i]);
        ts.add_edge(u[i], v[i]);
    }
    ts.sort(ord);

    vector<ll> comb(N, 0), tot(N, 0);
    comb[root] = 1;
    tot[root] = 0;
    fore(cu, ord) fore(to, E[cu]) {
        comb[to] += comb[cu];
        tot[to] += tot[cu] + comb[cu];
    }
    return { comb, tot };
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) cin >> u[i] >> v[i], u[i]--, v[i]--;

    auto p1 = getCombination(0);
    rep(i, 0, M) swap(u[i], v[i]);
    auto p2 = getCombination(N - 1);

    rep(i, 0, N) {
        ll ans = p1.first[i] * p2.second[i] + p2.first[i] * p1.second[i];
        cout << ans << endl;
    }
}

加工機 [パソコン甲子園2020 予選 G]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0434

解説

https://onlinejudge.u-aizu.ac.jp/solutions/problem/0434/review/5811086/hamayanhamayan/C++14

シミュレーション高速化していく問題となる。
加工後の高さをもっていきながらシミュレーションをしていきたい所ではあるが、盤面が大きすぎる。
なので、加工された部分のみを保持しながらシミュレーションを頑張っていくことにする。
各所、切削をしていくが、その切削によって表面積がどう変化したかという感じで、差分計算をしていくことにする。

初期状態

最初は、全部つるつるの状態なので、6面の表面積を足したものになる。
具体的には2WD + 2DH + 2HWが初期状態となる。

差分計算

切削をしていくが、その際の表面積の変化は周りの高さがどうであるかに依存することになる。
4面あるので、4面について場合分けを書いていってもいいが、実際にはやっていることはさほど変わらず、自分のように
dx, dyを使用して4面を同じコードでさばいていくことにする。

盤面をすべて持つことはできないので、mapで保持することにする。
map<int,map<int,int>>みたいにしてもいいのだが、mapはまあまあ重いので、配列でx座標については配列にして置いている。

中で3択の場合分けをしている

場合分け1: 盤面からはみ出してしまう場合

はみ出す場合は、そちら側は切削した分だけ表面積がなくなってしまうので、ans -= z[i]をしよう。
反対側の表面積があるのでは?と思うかもしれないが、そちらの側面もループであとで考慮するので、
このはみ出す方向に対する表面積としては減るだけ

場合分け2: まだ切削してない部分と面している

この場合は切削した分だけ表面積が増えるので、ans += z[i]すればいい。

場合分け3: 既に切削している部分と面している

この場合はちょっと複雑なのだが、差分計算でよくやる、「現状を消す→処理→現状を足す」ということをすればいい。
現状を消すの部分は、今切削している所と今見ている隣接している所の高さの差が現在生じている表面積になっているので、
ans -= abs(changed[xx][yy] - cur)とする。
これで、切削処理をするので、curがcur - z[i]となる。
それでから現状を足すので、ans += abs(changed[xx][yy] - (cur - z[i]))とする。

注意点

これで最終的にansを答えればいいのだが、オーバーフローに注意。
long longで全体的に計算すること。

ll W, D, H; int C;
int x[101010], y[101010]; ll z[101010];
map<int, int> changed[101010];
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> W >> D >> H >> C;
    rep(i, 0, C) cin >> x[i] >> y[i] >> z[i];

    ll ans = 2 * W * D + 2 * D * H + 2 * H * W;

    rep(i, 0, C) {
        ll cur = H;
        if (changed[x[i]].count(y[i])) cur = changed[x[i]][y[i]];

        rep(d, 0, 4) {
            int xx = x[i] + dx[d];
            int yy = y[i] + dy[d];

            if (0 <= xx && xx < W && 0 <= yy && yy < D) {
                if (changed[xx].count(yy)) ans -= abs(changed[xx][yy] - cur), ans += abs(changed[xx][yy] - (cur - z[i])); // 場合分け3
                else ans += z[i]; // 場合分け2
            }
            else ans -= z[i]; // 場合分け1
        }
        changed[x[i]][y[i]] = cur - z[i];
    }

    cout << ans << endl;
}