数列a,数b,l,rに対し,区間[l,r)でのmin{a[i] xor b}(max{a[i] xor b})を高速に求める
こんにちは。heno239です。
タイトル通りですが、
- 数列aが与えられたとき、クエリ「数b,l,rに対し、区間l<=i<rにおけるa[i]^bの最小値(最大値)を返す」を割と高速にこなすtri木
について書きます。ある問題を解いていた時に必要に駆られて書いたので、ついでにあげとくか、みたいなノリです。
-
計算量
数列aの最大値をAとし、数列の長さをNとします。
初期化でO(NlogA),クエリ毎の計算量はO(logNlogA)です。(クエリ数が2*10^5,N=2*10^5,A=2^30ぐらいなら2秒以内に通ると思います)
適当に書いたので、定数倍が結構重そうです。
-
説明
ソースコードを見ればわかります(過激な主張)
-
使い道
ごくたまに出てきそう
-
いま食べたい寿司のネタ
0.1%の確率で更新を怠るセグメント木
こんばんは。最近実装力に自信がなくなってきているheno239です。
タイトル通りですが、今回は0.1%の確率で更新を怠るセグメント木を実装しました。ソースコードはこちらです↓
gist072edeb5ab1fd40f73fbeb6a2fc01dd7
作っただけじゃ面白くないので、更新を怠らない真面目なセグメント木と比べてみました！
今回の比較では、非常にシンプルな練習問題として
Range Minimum Query (RMQ) | Aizu Online Judge
を用いました！
以下が比較実験の結果となります！
-
真面目なセグメント木
当たり前ですが、通ります。
-
サボる方のセグメント木
いい感じにWAになります。
-
まとめ
いかがだったでしょうか？
ちなみにこの0.1%の確率で更新を怠るセグメント木の使い道についてですが、
-
1.運試しに用いる
-
2.最近ACばっかりでつまらない時や、意味もなくWAを出したくなった時に用いる
-
3.ライバルのライブラリにこっそり忍び込ませ、WAを連発させて蹴落とす
などが考えられます。いずれにしても何かを失う可能性があるので、ご利用は計画的に。それでは。
CODE FESTIVAL 2018 参加記
こんにちは。heno239です。11/17に行われたCODE FESTIVAL 2018本選に参加してきました。色々な人が参加記を書いているのをTLで見かけたので、僕も書きたくなりました。
-
予選
qual A(通称DP festival(←この呼び方僕しか使ってなくない？))で44位で通りました。予選前は通るかどうか怪しいと思っていましたが、僕が苦手ではないタイプの問題セットが出てくれたおかげで、結構余裕がありました。
同学年かつICPCのチームメンバーであるyamunaku君もqual Aで通過していて、すごく安心感がありました。
qual Bは予選落ちしました。危ない
-
本選~前夜~
意気揚々と東京に入りました。用意されたホテルが結構参加者間でバラバラで、「秋葉原でバラバラ！ｗ」とかこっそり思ってました。
夜は朝4時に眠りました。イベントの前夜はいつも緊張で眠れないのでこれぐらいの時間は大したことないのですが、TLの阿鼻叫喚ぶりがすごくて面白かったです。
-
本選~当日の朝~
7時15分にホテルのモーニングコールをセットしていて、その通りに起きました。ホテルが一緒だったyamunaku君と会場に向かうことにしました。
ここで朝食問題が発生します。会場にとりあえず入ってから朝食を調達しようと思ったのですが、会場の近くにコンビニが無くて、かなり苦労しました。「朝食なくて超ショック！ｗ」とか勝手に思っていました。
-
本選~コンテスト本番~
環境などに問題はなく、無事コンテストを始められました。当初の目標は20位以内に入って賞金を手にすることでした。以下はコンテスト中のムーブです。
- A問題を見る。300点ってなに？？？？→あ、1000<=l<=2000か→真ん中固定すればよいのね→1270の時だけ注意しようね。→AC(12:18)
- B問題を見る。答えの式をたてる→愚直に計算すると1000000007%誤差で死ぬと思ったので、値を(係数,10のべき数)の二要素でもつ(6.02*10^23みたいな)→ちょっとミスったけどAC(32:27)
- C問題を見る。AとBよりも簡単じゃね？→AC(40:47)
- 順位表を見て、ふーっと一息つく。明らかにDよりもEが解かれていることを確認。焦りや緊張はほとんどなかった。
- E問題を見る。「i番目の町にいるとき[i-k,i]番目の町のペットボトルを買える」と問題を読みかえて、セグ木使ってAC(47:34)
- D問題を見る。52^3が10万ちょいなので、52^3*90000はやばいなと感じて、52^2になるように色々と試す。しかし全くうまくいかなくて、8回TLEで落とされる。最終的に52^3*30000をちょっと早くして、497msでAC(116:27)。ここが一番の難関でした。なんで実行制限時間2sやねーんって思いました。
- 順位表を見て一息。Dで詰まったため入賞は厳しいかなと思って、半分諦めていた。FよりもGが解かれていることを確認。
- G問題を見る。O(N^2M)がすぐ思いつく。1000^3が通ったMUJINコンの例(
https://beta.atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_f
)があったので、とりあえず書いて投げる。通るんかーい！！！(全力のツッコミ)(133:10) - F問題を見る。分かるけど分かりません。コンテスト終了...
- 凍結された順位表を見ると、19位だが、周りがめっちゃたくさん投げているのに対し、自分は一つも投げていない。怖い...
- 表彰式にて、ギリギリ20位に入っていたことが判明。めっちゃ喜ぶ。
- お疲れさまでした。
パーカーと1万円は自分の努力が具現化されたようで、ものすごく嬉しかったです。
Gで2000^3を投げていたり、これ以上点数の伸びようが無かったことを考えると、実際の実力的にはすごく負けた感じがしています。来年はこういう劣等感が無くなるぐらいには強くなりたいです。
-
本選~休憩時間~
PG battleに出ました。戦犯をしました。ｱｱｱ
初めててんぷらさんと話したり、こたつgameやolpheさんなど、たくさんの人と話せてよかったです。
マリオカート楽しかったです。
りんごさんの挑戦状、面白かったです。
-
本選~リレー~
Aチーム(0,1(mod20)位から構成)に入り、3位でした。僕がしたのは自明を通すことだけだったので、チームメンバーにcarryされた形になりました。肉肉肉肉肉肉18
-
本選~晩さん会,閉幕~
リレーで3位だったため、賞品として2500円/100gの高級お肉が夕食に追加されました。
ところが、全員がめちゃくちゃ遠慮してしまったため、最終的に大量のお肉が残っていました。(美味しかった(小声))
寿司とピザが無限に補給されていて、すごい...って感動していました。あとここでもいろいろな人と会話しました。
閉幕は閉幕、閉幕でした。感動っぽいことをして、お疲れ様でした！
-
その後
kmcの方たちとめっちゃボードゲームしたり、OBのすごい人に寿司を奢って戴いたり(3月までにオレンジになる条件付き)して、京都に帰りました。
-
来年の目標
欲を言うと10位以内が目標ですが、とりあえず20位以内に入れるように頑張ります。CODE FESTIVAL大好き。
信号で黄色になるまでにしたこと
右と左の安全性を確認し、渡った。
JAG夏合宿2018参加記
-
まえがき
タイトル通りですが,JAG夏合宿2018に参加してきました.参加する動機は3つぐらいあって,
-
私はまだ競技プログラミングを始めて日が浅く,競プロをしている知り合いというのが(特に大学外には)ほとんどいなかったので,これを機に知り合いが増えたらいいな、という思い
-
今の自分の実力だとどれぐらい問題が解けるのだろうという疑問
-
夏休みに暇を持て余すことへの恐怖
これらの理由で参加しました.ICPC国内予選のチームメイトであるyamunaku君(@yamerarenaku )も参戦し,意気揚々と(?)東京に乗り込みました.
-
1日目
寝坊して出発時刻が40分ほど遅れましたが,ちょうど集合時間の13時頃に会場に到着.yamunaku君と大学の先輩チームであるZerokan_Sunshineの方々を見つけて少し安心感を覚えつつ,開会式が始まりました.全員が各々前に立って自己紹介するの,驚きでした(とても緊張した...)
その後早速14時からコンテスト.コンテスト中のムーブは
- とりあえずA,B,Cは易しいと聞いたので,AとCをAC(Bもyamunaku君がAC).
- Dでyamunaku君がシミュレーションするだけというも,愚かなheno239は「実行時間やばい！実行時間やばい！」と嘘を連呼し,結局時間を無駄にしてからDをAC.
- E問題読めない,F問題面白そう
- Eは内部の図形の頂点が同一円周上にあることが分かり,yamunaku君の半径にぶたんじゃない？って発言に理解を得る.しかしコーナーケースのパターンでのにぶたんの処理が分からず,沈没.
- F,たくさん図を書いてheno239が嘘を何回も投げる.yamunaku君のideaが正しいかったことを最後は理解し,(頑固すぎたな...)と反省しつつ投げてAC.
- ららら～～ららら～～何も～～わからん～～
といった感じでした.あまり良い成果は出せませんでした.
1日目の夜にAGC027があり,B問題に取りつかれ死んだので,ふて寝しました.
-
2日目
おはようございます.朝が早い.
朝食バイキングでめっちゃ食べれるやんけ～～って言いつつめっちゃ食べました.少しゆっくりしたのち,コンテストです.1日目は2人チームでしたが,2日目は相部屋だった方(以降助っ人と呼ぶことにします)を誘って3人チームで出ました.コンテスト中のムーブ↓
- A,B,Cが数学要素めっちゃあったのでうおおおおおおおおって言いながらさっと通す
- G問題,頂点の周りちょっと見ればよくね？と言って嘘を3回投げてあきらめる.
- DとIはどうみても無理そう
- EやHやJやKを考える
- 僕がEに取りつかれている間にHが通る
- E,bitsetで高速化すれば実は通るんじゃね？って言って投げたら通って爆笑する
- Jで助っ人がすごく良さそうな考察をするも,時間が足りなかった
- K,yamunaku君が考察してた
順位は割とよかったので嬉しかったです.FFT勉強しないとな,と思いました.
その後のコドフォやopencupには出ず,あとはひたすらボードゲームしてました.
-
3日目
あっという間に最終日.今日もがんばるぞ～～～って感じでたくさん朝食をとりました.2日目の方をまた誘い,3人でコンテストに臨みました.コンテスト中のムーブ↓
- はじめのA,B,Cは簡単らしいので,3人で手分けして通す(heno239はBを通した)
- Iが簡単そうだったのでさっと通す
- F,yamunaku君が提出し,たった数件だけWA.割と時間をかけてコーナーケースを見つけ出し,修正してAC.
- J,yamunaku君の考察をまるごと借りて実装しAC.
- Gを全員で協力して通しにかかる.実装はheno239がしていたが,遷移やバグをチームメイトにたくさん指摘してもらって,なんとかAC.
- Kをチームメイトに投げ,自分はDを考える.
- Dの考察が終了し実装するだけになったが,残り時間が45分かつ実装が重いので,めっちゃ焦る
- Dがコンテスト終了1分前に通り歓喜の舞を踊る
こんな感じでした.かなり達成感があって,めちゃくちゃ楽しかったです.この問題セットを用意した方々大好きです.余談ですが,コンテスト中は前の席がGiftedInfants,後ろの席がUKUNICHIAの強豪2チームで,めっちゃプレッシャーがありました.
-
終わり
最終日のコンテストが終わり解散になりました.助っ人の方やこたつがめ(@kotatsugame_t )や碧黴(@AokabiC )さんなどと再会を誓い,オリセンを去りました.
このあとちょっと東京で遊んで帰りました.
-
今
来年こそはICPC国内予選通るぞー！うおー！問題解くぞー！うおー！寿司食べたい.
ABC109 感想
色文字が感想の内容です
-
A問題
a*bが偶数ならcを何にしてもa*b*cは偶数ですし,a*bが奇数ならc=1とすればa*b*cは奇数です。雨降ってる～
-
B問題
N個の文字列を要素に持つ配列をつくり、i番目の文字列の最後の文字とi+1番目の文字列の最初の文字が等しいかをすべて調べます。
注意が必要なのは、(しりとりなので)同じ文字が２回登場するとダメなので、
-
2重ループをまわして調べる(O(N^2))
-
sortしてcountする(O(NlogN))
-
mapを使って出た文字を記録する(O(NlogN))
などをして確認します。同じ文字が2回登場しちゃダメなのを忘れて1WA,悲しい
-
C問題
スタート地点から各地点への距離を求め、最大公約数をとります。最大公約数を取る時なんですが、
1 int gcd(int a,int b){
2 if(a<b)swap(a,b);
3 while(b){
4 int r=a%b;a=b;b=r;
5 }
6 return a;
7 }
という関数をいつも書いてます。4行目が流れるように書けて好きなんですよね。
-
D問題
奇数個のところは動かして損はないので、どんどん掃きだしていくように、
→→→→→→→→→→→→→→→→→→→→→→→→↓
↓←←←←←←←←←←←←←←←←←←←←←←←←
→→→→→→→→→→→→→→→→→→→→→→→→↓
↓←←←←←←←←←←←←←←←←←←←←←←←←
...
と見ていき、偶数個なら放置、奇数個なら次のマスに1渡す、という操作をすると、無駄がなくてよいです。こういう問題、いつも操作回数を出力するのを忘れるので反省したいですね...(2WA)
-
全体的感想
前回前々回の狂気ABCと比べ、標準的なABCだったと思います。twitterのタイムラインを見ていると、みんな楽しそうでした。
