37.50.48

%20 の ブログ

KyurideKagamizProgrammingContest(Remixed by ryunosuKe & Kensuke) C - 山登り(Mountain Climbing)

この記事は KyurideKagamizProgrammingContest(Remixed by ryunosuKe & Kensuke) C - 山登り(Mountain Climbing) の解説です。

いくつかの解法があるらしいがこの解法で fastest(33ms)になった(出題されてからジャッジ環境が変化しているのであまりフェアな比較ではない)。

問題文のストーリーに従うのならばクエリが与えられる毎に答えを求める必要があるが、ストーリーを無視すればクエリを先読みして後ろから順に処理できる。
辺が減っていくのを後ろから順に見ると辺が増えていくことになるので UnionFind が使える。
辺が全くない状態から辺を増やしていきたいので、入力で \(x_i\) として出現しない頂点(根は除く)を \(x_{Q+1},x_{Q+2},\cdots,x_{N-1}\) に追加しておく。
元のグラフの部分グラフであるような各連結成分に対し、元のグラフのある葉からその連結成分の根までの移動コストの最小値は次のような DP で求められる。

初期化

\(\begin{eqnarray} dp[v] := \begin{cases} 0&(頂点vが葉である) \\ \infty&(頂点vが葉でない) \end{cases} \end{eqnarray}\)

頂点 \(v\) が属する連結成分の根を \(r[v]\) とする。
\(r[v] := v\)

(すべての辺が使えるときの)根(頂点 \(1\) )から頂点 \(v\) までの移動コストを \(s[v]\) とする(これは累積和の要領で求まる)。
\(\begin{eqnarray} s[v] := \begin{cases} 0&(頂点vが根である) \\ s[p_v]+w_v&(頂点vが根でない) \end{cases} \end{eqnarray}\)

更新

\(find\) 関数を UnionFind の再帰的に代入するやつとする。
頂点 \(x\) と頂点 \(p_x\) の間に辺を張るとき、\(R := find(p_x)\) とすると
\(dp[R] := {\rm min}(dp[R],dp[x]+s[x]-s[R])\)
\(r[x] := R\)

元の問題では辺が減った後の移動コストの最小値を問われているので、後ろから見たときは辺が増える前の移動コストの最小値 \(dp[1]\) をその時点での答えとすればよい。

実装例

区間に関するやつ

1 次元の区間に関するやつのまとめ。誰向けか分からない。

以下で言っている「演算」は、可換でなくてもよいが結合則が成り立つ必要がある(行列同士の掛け算などはこれに該当する)。

累積和

言わずと知れたやつ。
区間和をクエリ毎に \({\rm O}(1)\) で求める。
累積「和」と言っているが、逆演算(加算に対する減算のようなもの)が存在すれば和でなくてもよい( bitwise xor など)。
累積積もこれでできるが、入力に 0 がない場合に限られる( 0 がある場合はセグ木
だと思ってたけど、区間内に含まれる 0 の個数は累積和で求まるので
区間内に 0 が 1 個以上あったら答えは 0、そうじゃなかったら累積積同士の割り算」でできる)。
数え上げで \(f(B)-f(A-1)\) みたいにするやつも累積和の一種。

エックスオア多橋君 は木に対して累積和を使っているイメージ。

いもす法

「最後に累積和をとれば求めたい数列になる」ようにすることで、区間に対する書き換えがクエリ毎に \({\rm O}(1)\) でできる。

セグ木

逆演算が存在しなくても使えるやつ。
RMQ などはこれ。
区間に対する演算と、1 つの頂点に対する書き換えがそれぞれ \({\rm O}(\log N)\) でできる。
書き換えは葉に対して行うことが多いが、そうでない頂点に対しても行える。

BIT

セグ木と似ているが、逆演算ができなくてもいい場合にのみ使える。
区間に対する演算と、1 つの頂点に対する書き換えがそれぞれ \({\rm O}(\log N)\) でできる。
セグ木よりも表現力が低いが、コード量が少なくて済むので(人によっては)実装が楽だったり、コードゴルフに役立ったりする。
転倒数の問題では解説で BIT を使うように書かれていることが多いが当然セグ木でもできる。

平方分割

平方根分割のほうが適切だと思うが平方分割と呼ばれている。
セグ木と表現力は同じだが計算量が大きい。
区間に対する演算と、1 つの頂点に対する書き換えがそれぞれ \({\rm O}(\sqrt N)\) でできる。
実装が楽。
遅延セグ木の代用品になるらしい。

遅延セグ木

普通のセグ木よりも表現力が高い。
区間に対する演算と、区間に対する一様な書き換えがそれぞれ \({\rm O}(\log N)\) でできる。
いもす法で解ける問題は( TLE しなければ)遅延セグ木でも解ける。
実装がつらい。

尺取り法

区間の右端を伸ばしたり左端を縮めたりする \({\rm O}(N)\) のやつ。
逆演算が存在する場合に使える。
伸ばせるだけ伸ばすやつと、区間の幅が固定のやつがある。

スライド最小値

固定幅の区間に対する RMQ が \({\rm O}(N)\) でできる( deque を使う)。
尺取りっぽい感じがある。
RMQ の一種なので( TLE しなければ)セグ木でもできる。
( TLE しなければ)値とインデックスのペアを使う優先度付きキューでもできる(優先度付きキューでできることは multiset でもできる)。

Mo's algorithm

単に Mo と言う場合もある。
書き換えが起こらなくて逆演算が存在するものに対して、
クエリを先読みして、「区間の左端と右端をそれぞれ \(\sqrt N\) で割った商のペア」についてソートしておいて、
\({\rm O}((N+Q)\sqrt N)\) で尺取りっぽくやる。
区間を伸ばすのを縮めるのよりも先にやらないとおかしくなる場合がある。
累積和と一緒に使うこともある。

Sparse Table

使ったことがないので詳しくは分からないが、そういうものがあるらしい。
書き換えが起こらない場合に RMQ がクエリ毎に \({\rm O}(1)\) でできるらしい。

√1+√2+...+√n

\(\displaystyle\lim_{n\to\infty}\left\{\left(\sum_{k=0}^n\sqrt k\right)-\left(\dfrac23n\sqrt n+\dfrac12\sqrt n\right)\right\}=-\dfrac1{\sqrt{e^\pi}}\) の真偽とその証明について知ってる人がいたら教えてほしい。

偽で、\(\zeta\left(-\dfrac12\right)\) になるらしい。

\(-\dfrac1{\sqrt{e^\pi}}=-0.207879\dots,\)

\(\zeta\left(-\dfrac12\right)=-0.207886\dots\)

CODE FESTIVAL 2018 の参加記じゃないやつ

これはたぶん CODE FESTIVAL 2018 の参加記ではないので読まなくていいです。

予選 A

4:58 で 2 完( AB )。C が分からなかったが(本戦ボーダーは ABD だったらしいので)C が解けていたとしても本戦には行けていない。
一方で、ネット上で交流があり会いたいと思っていた 2 人は本戦に行けることが確定していたので、もし予選 B で THANKS だったら辞退するかもしれないという感じだった。

予選 A があまりに酷かったので解いてない問題を点数の低い順に解いていこうと思った。
400 点埋めをした。
500 点埋めをした。
600 点埋めを途中までした。

予選 B

20:15 で 3 完( ABC )。3 完時点で 41 位タイ。D と E を見て D が分からないから E をいじっていたが結局分からず。
D と E がどちらもしばらく解かれず慢心してもよさそうだったので慢心していた。
最終的に 47 位タイだった。予選 A で通った人や社会人などを除いて数えると通っていたっぽかった(実際通っていた)。

前泊と後泊をすることになったのでせっかくだから前日や翌日に誰かに会いたいと思い、そのようなツイートをしたところ kimiyuki さんから「 golf(コードゴルフ)の会をしよう」と声がかかり、 kotatsugame さんと 3 人で集まることになった。
集まるタイミング的にもちょうどよいので食事会もすることになった。

前日

kotatsugame さんが東京に着くのが 19 時頃になるはずだったのでそのつもりで行動していたが、実際には kotatsugame さんは昼には東京に着いていた。
予定通り 19 時頃に合流し、食事をしようとしてサイゼリヤに向かったが、順番待ちの人が多すぎて一度は引き返してしまった。
席が多いので実はそんなに待たないのではという話になり、結局再度サイゼリヤに向かった。
順番待ちの椅子が 1 脚しか空いていなかったのでじゃんけんをして kotatsugame さんが勝ったが、AtCoder じゃんけんでは kimiyuki さんが勝ちなのでは?となったが普通にじゃんけんで勝った kotatsugame さんが座った。

食事が終わりカラオケ屋に行ったが、金曜の夜なので当然混んでいて順番待ちの人がいたが待ち時間は 10 分ぐらいだったのでそれなら待つかということになった。
部屋に入ると、コンセントが無かった。カラオケ用のモニターやら何やらのためのコンセントは使っちゃダメみたいなことが書いてあったので素直に従った。
ゴルフ会をすると言っても具体的に何の問題を解くかを決めていなかったので、ちょうど 1 週間前に yukicoder で出題された、自分が作問した問題である mod数列 を縮めることにした。
この問題は 2 人は既に解いていて、なおかつ 3 人とも縮めていなかったのでちょうどよかった。

自分はパソコンを開かずに 2 人に対して横からあーだこーだ言う感じで動いていた。
最短コードが Crystal によるものだったので、 kimiyuki さんが Crystal の環境を構築して言語内で縮むかどうかを試していた。
Perl に移植するだけで縮みそうだったので kotatsugame さんが移植したら縮んだ。
やっぱり Perl だよねという話になり、 kimiyuki さんも Perl で縮めたりした。
時間が 1 時間半しかなかったので 1 曲も歌うことなくゴルフも途中で終わってしまった。

ゴルフ会が終わり、少し駄弁った。
自分( x20 )は賞金を獲れるはずがないので kimiyuki さんに賞金は獲れそうですかと訊いたところ、赤もいるしまぁ無理でしょうみたいな応答があった。

解散してホテルに向かおうとして秋葉原駅から神田駅まで移動し、南口から出たかったが東口から出てしまった。
独り言で「分からない」などと言いながら歩いていると、道案内をしてくれそうに話しかけてくれる人がいたので、その人に南口までの道を訊いてホテルまで辿り着いた。

ホテルに着くと、部屋の照明の点け方が分からなかった。分からないのでフロントに戻って訊くと、説明があった(実はルームキーの裏側に同様のことが書かれていることに後から気付いた)。
照明を点けてパソコンを開いてここでようやくツイッターを見ることができた。
靴下の替えを持ってくるのを忘れていることに気付いた。

当日

起床はできたものの、眠すぎて何も分からなかった。
時間がなく、ホテルに付いているらしい朝食も摂れなかった。

道に迷わずに会場に着いた。
座席番号が 057(グロタンディーク素数)だったので当たりじゃんなどと思った。
交通費清算が去年の THANKS ではスマホを持っていないからという理由で紙での申請になったがパソコンじゃダメなのかと訊いたらパソコンでいいと言われたのでパソコンで申請した。

本戦

パーカーは 1400 点以上(配点は 300 300 300 500 600 600 700 900 1000 1200 )なので前から順に 4 完すればいいらしい。
去年は実質参加賞だったと聞いていたので思ったよりボーダーが高い印象を受けた。
無線 LAN が怪しかったので有線 LAN を繋いだがそれでも不安定だった。

A

いきなり分からなくなった。時間をかけて落ち着いてやったら通った。

B

log をとるだけなのだけどなんかうまくいかなかったので紙に書いて落ち着いてやったら通った。

C

折れ線グラフがどうなるかは問題文を読めば分かるので紙に書いてやった。実装でなんか変な感じになった気がするけど落ち着いてやったら通った。

D

何も分からない。順位表を見ると D を解いた人数が極端に少なく、E の方が簡単らしいので E を解くことにした。

E

この問題が一番簡単に感じた。
K が無ければ蟻本(の第 2 版の p.73 )に載っているプライオリティキューを用いる問題とほぼ同じなので K があってもプライオリティキューを用いると解ける。
解けたのでパーカーを得た。

F,G

サンプルが合わない。

H,I,J

開いていない。

順位表凍結時、kimiyuki さんが 2 位になっててすごいと思った。
kotatsugame さんも一時的に賞金圏内になっていてすごかった。
自分( x20 )の最終順位は 59 位で、目標は「 80 位とか 70 位とかをとれれば嬉しい」ぐらいだったのでだいぶ良かった。

昼~夕方

弁当を食べている途中で移動することになり、眠い時に食事を中断させられてパニックになった。夜は夜で食べ物が出るので結局弁当はゴミ箱に捨てた。
ルービックキューブタイムアタック」の入賞タイムが自己ベストよりも遅かったので挑戦した。何度か挑戦して 2 分は切れたが結局入賞はしなかった。
kimiyuki さんと話した。
「りんごの挑戦状」を適当に眺めた。

リレー

本来 1 チーム 10 人だが 9 人のチームだった。本戦順位のチーム内順位の「 9 位と 5 位」「 8 位と 4 位」「 7 位と 3 位」「 6 位と 2 位」がそれぞれ「 A 」「 B 」「 C 」「 D 」をペアで考察し、順位の低い方の人が実装するという作戦になった。
チーム内 6 位だったのでチーム内 2 位の leign さんとペアになって D に挑んだ。解法の理解に苦しんでいたので sugim48 さんにも教えてもらって理解できた。実装を始めてから分からなくなって一度戻ったがすぐに分かって一発 AC できた。
チーム全体の順位は最下位だったが楽しかった(食べ物に対する興味が低いのでもし上位になって肉がもらえてもあまり嬉しくない)。

ほとんどの時間で kimiyuki さんと kotatsugame さんと話していた。
そういえば chokudai さんと話していなかったなぁという感じで話した。AtCoder ステッカーをもらった。

終了後

会場を出てからもやはり kimiyuki さんと kotatsugame さんと話していた。
kotatsugame さんは CHUNITHM をしに行くということでここで別れ、 kimiyuki さんと共に行動することになった。

コンセントのあるマクドナルドに行き、そういえば AtGolfer の開発(改良)はどうなったのという話になり、pull request を送ったことがないので(しょうもない)pull request を送ってみようという流れになり操作してもらって送った。
マクドナルドが閉店時刻になったので店外に出て、その後も長い時間話していた。
kimiyuki さんは翌日には別の予定があるがそれは夕方からなので昼過ぎぐらいまでなら予定が空いてるということで翌日にも会うことになった。

神田駅の南口から出ることには成功したが、歩く方向を間違えて東口に辿り着いてしまったので引き返してホテルに向かった。
片言の日本語を喋ってくる客引きらしき人がいた。

翌日

朝食を摂る時間をとれなかったので食べずにゲーセンに向かった。
maimai が( 4 曲を期待していたが) 3 曲設定だった。
2 クレ目の途中で、初プレイの人が間違えて同じ筐体の隣側に来て Aime カードを当てて反応しなくて困惑しているようだったので隣(の筐体)が空いてますよと案内した。
ちょうど 2 クレ目が終わった辺りで kimiyuki さんが来たのでせっかくだから一緒にやってく?という感じで 1 クレ一緒にやった。

昨日とは別のマクドナルドに行ったらコンセントが無かった。まぁパソコン開かなくても話はできるしという感じで話していた。
「 staff only 」と書いてある扉がある方向に向かう一般客が多かったのが面白かった。
混雑時は食べ終わった人はとっとと出て行ってみたいなアナウンスがあったので店外に出た。

無印良品に行ったら「テレビで紹介されました」とかいう雑なポップがあった。

その後も話をしていたが kimiyuki さんがそろそろ時間だというので駅に向かった。一人で散策するつもりもあったが改札を通ってしまったので(眠かったので帰るべきではあるし)そのまま帰ることにした。

総括

話の通じる人と話すのは楽しい。

yukicoder No.673 カブトムシ

この記事は yukicoder No.673 カブトムシ の解説です。

\(n\) 年目の大晦日のカブトムシの匹数を \(X_n\)(ただし \(X_0=0\))とすると、$$\begin{eqnarray}X_n&=&(X_{n-1}+B)×C\\&=&C\cdot X_{n-1}+BC\cdot 1\end{eqnarray}$$となる。この遷移を行列で表すと、$$\begin{pmatrix}X_n\\1\end{pmatrix}=\begin{pmatrix}C&BC\\0&1\end{pmatrix}\begin{pmatrix}X_{n-1}\\1\end{pmatrix}$$であるので、\(X_D\) については、$$\begin{pmatrix}X_D\\1\end{pmatrix}=\begin{pmatrix}C&BC\\0&1\end{pmatrix}^D\begin{pmatrix}X_0\\1\end{pmatrix}$$で求まる。

あとは mod をとりながら繰り返し2乗法で行列累乗するだけ。

yukicoder No.638 Sum of "not power of 2"

この記事は yukicoder No.638 Sum of "not power of 2" の解説です。

a をなるべく小さくしたいので、可能なら a=3 にしたい。
b のとりうる最小値も a と同じく 3 なので、6=3+3 よりも小さい N は N=a+b で表せない。

以下、N≧6 について考える。

a=3 としたときに b=N-3 が 2 の整数乗でないという条件を満たしていれば、求める (a, b) の組は (3, N-3) である。
そうでないとき、a=5 とすると b=N-5 が条件を満たさないことはほとんどない。
なぜならば、N-3 と N-5(という、差が 2 であるような 2 数の組)がともに 2 の整数乗であるので、これを満たすような 2 数の組は (N-3, N-5) = (4, 2) 以外に存在しないからである。
つまり、N=7 のときは a=3 も a=5 もダメで、N≠7 のとき、求める (a, b) の組は (5, N-5) である。

まとめると、

  • N<6 または N=7 のとき -1
  • そうでないとき a=3 が OK なら (a, b) = (3, N-3)
  • そうでないとき (a, b) = (5, N-5)

となる。

「正の整数 x が 2 の整数乗である」は (x & x-1) == 0 で判定できる。

#232871

ll N;
{
	rd(N);
	if(N<6||N==7)
		wt(-1);
	else if(N-3&N-4)
		wt(3,N-3);
	else
		wt(5,N-5);
}

yukicoder No.619 CardShuffle

この記事は yukicoder No.619 CardShuffle の解説です。

考え方

問題を見ればセグ木を使えば解けることは予想できる。

セグ木に載せるべき「部分的な計算結果」どうしをつなげて掛け算をしたときの掛け算の影響範囲を考えると、「部分的な計算結果」は a+b+c の形をしていると都合がよいことが分かる。

セグ木の各ノードに a+b+c の形をした式の「 a, b, c の値」と「 + または * の演算子」を載せる。

数字カードはセグ木の葉ノードに対応し、演算子カードは葉でないノードに対応する。

数字カードは a+b+c の形にならず、値を 1 つだけもつ。また、値を 1 つだけもつものどうしを * でつないだ場合も値を 1 つだけもつ。

値を 1 つだけもつ場合は x-x+x のようにしておくと都合がよい。a+b+c の形になる場合は b は負になり得ないので、b が負であるならば値を 1 つだけもっていると判定できる。0-0+0 の場合は b が負にならないが、辻褄は合う。

a+b+c と d+e+f の掛け算については 4 通り考える必要があり、

  • b≧0 かつ e≧0 のとき a+(b+cd+e)+f
  • b≧0 かつ e<0 のとき a+(b)+cd
  • b<0 かつ e≧0 のとき cd+(e)+f
  • b<0 かつ e<0 のとき cd+(-cd)+cd

のようになる。一方、足し算については x-x+x のようにしておいたことにより場合分けが不要になり、

  • a+(b+c+d+e)+f

のようになる。

交換クエリにおいて、演算子カードの交換が発生し得るので、「カード列のインデックス→セグ木のインデックス」の変換ができると楽。

交換後の再計算の際に、値の入っていないノードとの計算をする場合がある。その場合は 0 との足し算をするようにすると楽。

入力の読み込み方

セグ木上を通りがけ順で移動しながらその場所に入力の値を載せていく。

入力を読み込む毎にインデックス変換用の配列にインデックスを入れる。

前処理としての計算も入力を読み込むついでにやってしまう(左側で再帰、真ん中で演算子を読み込む、右側で再帰、左右の計算結果どうしで演算、の順でやる)。

カード列のインデックス
               8
       4              12
   2       6      10      14
 1   3   5   7   9  11  13  15

 
セグ木のインデックス
               1
       2               3
   4       5       6       7
 8   9  10  11  12  13  14  15

交換クエリ

数字カードの交換の場合は交換したカードの親ノードから根に向かって再計算する。

演算子カードの交換の場合はそのノードから根に向かって再計算する。

質問クエリ

計算範囲の左端と右端から同時に根に向かって親ノードが一致するまで演算していき、それぞれの計算結果どうしで演算する。

実装例

#226631 一応この記事を書いている段階では最速らしい。