KUPC2019参加記
なぜか京都会場で申し込んだら台風で東京会場が中止になったので大勝利した
KUPC2019の東京会場ですが、登録TAに勝利して楽しみにされていたことかと思いますが、残念ながら台風19号の参加により中止とします。
— KUPC2019 (@kupc_official) October 11, 2019
オンラインでの参加は可能ですので、自宅からバーチャルオンサイトということで我慢してください。
なお、京都会場は予定通り開催いたします。#kupc2019
コンテスト前
Swarmで京大のクスノキのメイヤーになった。5秒で自己紹介をする必要があったので「Joeです。う し た ぷ に き あ 王 国 笑から来ました」と手短に済ませた。もうひとりei13333という人がう し た ぷ に き あ 王 国 笑から来ていた。
昨年の冬はほとんどの人が「じょーさん」と呼んでいたのに今では9割ぐらい「じょえさん」になってきている気がする。ちなみに初出はniuezくん。
てんぷらさんに社会性が下がったことを指摘され厳しくなった(結局ぼくが眠かっただけっぽい？)
コンテスト
なぜか潜伏してやろうという気になっていたがABCDまで解いて手が止まったのでとりあえず提出した。CがWAで厳しかった。こういう重りの問題は3ベキ！というのは2年前ぐらい前に考えたことがあったので知ってたはずなんですが、なんか2ベキをしていた。思考のズルをせず地道に構成してたら普通に解けた。
E,F,Gを3並列で考えていたがどれも詰めきれなかった。コンテストはダメでした
懇親会
阪大勢がすごかった。じゅぴろくんがめっちゃ酔ってた。じゅぴろくん元気？笑
カシスオレンジをピッチャーで頼みました pic.twitter.com/xYkMpkBkc3
— 自宅番兵@🈚️ (@homesentinel_) October 13, 2019
これは酒を飲むうし
しいくんが前見たときよりキラキラしてた。酔ったしいくんがちょっとアグレッシブでよかった(よい!)
王国民がみんなかなり飲んでいておもしろかった。
がぜるくんに発見されていたようなのに発見できなくて残念だった・・・
うしくんと一緒に余裕を持って帰路についたはずなのに京都のバスが複雑すぎて、検索して出てきたバスに乗ったはずなのに謎の方向へ進み始めてかなり困った。
やばいバスに乗ってしまったらしくうしくんと意味不明なところで途中下車した
— Joe (@xuzijian629) October 13, 2019
電車を調べると新幹線発車3分前京都着と言われてさすがに怖いのでタクシーを拾った。新幹線ホームでうしくんとバイバイした。
最後に
KUPC運営ありがと〜。オンサイトは楽しいですね。東大はやらないの？笑
う し た ぷ に き あ く ん 笑 っ て 何 ？ 笑
たぷりすたべる
フフホト市旅行記
突発旅行！じょえにきあくん笑
夏休みも最後の2日だし一泊二日で国内旅行したいなぁ〜と思っていたところ、実はラボのセミナー開始まで1週間あることに気づいたので、遠出しようと思いました。 ぼくはわりと突発旅行をよくするそうですが、海外旅行で、当日に旅行を企画したのは初めてだったかもしれません。
ちなみに突発旅行のメリットとして、天候によって行き先を選べるので外れることがない、というのがあります。デメリットはなんですかね？友達を誘っても来てくれないことでしょうか(来て〜〜〜〜〜〜〜〜〜><)
場所を決める
じょえくんは人気(ひとけ)のないところを旅するのが好きです。東京だと毎日いろいろ考えることが多くて人生つらそうに思えることでも大自然を目前にすると、「まじでどうでもいいなこれ」という気分になれます。
もともと行きたい場所はいくつかあって、たとえば中国だとラサ(ラサ単体というよりかは、西安から鉄道で標高を上がっていくときの景色の変化すべて)、ブータン/ネパールなどの高山帯、キルギスタン、タジキスタン、トルクメニスタン、イランあたりの去年行き損ねた中央アジア〜中東エリアでした。いずれも、気候的に日本と大きく違う場所で、自然の広大さを感じられる場所です。こういうところにいると、普段の研究とか仕事とか人間とかがどうでもよくなって心が落ち着きます。人も少ないし、英語が聞こえないのもポイントが大きいです(知っている言語を聞くと疲れちゃうので)。ちなみにこれらのエリアは世界史でよく登場するエリアで、ウィキペディアなどで復習しながら散策すると、めちゃめちゃ楽しいです。
今回行き先に決定したフフホト市は、内モンゴル自治区の省都で、ぼくも直前(というか当日)まで存在を知りませんでした。去年、新疆ウイグル自治区のウルムチに行ったので、○○自治区つながりで調べたら出てきました。内モンゴルというだけあって、ちょっと市街地から離れると草原や砂漠が広がっているようで、モンゴル語もちらほら見られるということで、エキゾチックな街大好きマンとしてはめちゃくちゃ行きたくなりました(ちなみにこれまでに行った一番好きな街は去年行ったコルガス市です)。
チケットを検索すると、往復9万ぐらいであったので即購入して荷造りして出発します。ホテルもとりあえずサポートがちゃんとしていそうなシャングリ・ラホテル フフホトを2泊分予約して、街の様子を見つつ行程を決めていくことにしました。こういう短期間突発旅行の場合、街の様子をホテルの人に聞いたり、ツアーを探してもらったりすることが多いのでそういうデスクがちゃんとしてそうなホテルを選ぶのは重要です。あと単にリラックスしたかったので良い目のホテルを。
（休みいっぱいまで旅行しようと思ったので日曜夜に東京に戻ってくる航空券をとったのですが、AtCoderの最強コンオンサイトとかぶってたことに気づかなくて泣く泣くオンサイトをキャンセルしました…）
フフホト市まで
とりあえず成田空港に行って、中本と中国用のSIMを買います。8日間、毎日500MBまで使えるやつで2500円ぐらいでした。中国だとGoogle等のサービスが使えないことは有名だと思いますが、香港回線を利用しているSIMまたはレンタルWi-Fiを使えば問題なく利用できます。レンタルWi-Fiが一日あたり2500円とかで高すぎたので絶対に使わないほうがいいと思います(ア)。ちなみに過去にじょえにきあくんはレンタルWi-Fiを予約したのに受け取り忘れて保安検査を通ったことがあり、現地でSIMを買うということをしたことがあります。
成田→上海→フフホトで、それぞれ3時間半、2時間半程度のフライトです。午前中の便に乗って、その日の夜に着きました。フフホトは同じ自治区のウルムチと違って保安検査がほぼほぼなく、平和な印象を受けました。
飛行機の行き先表示がガバガバで香港になってて乗ったあと焦りました(これ、最後まで香港になってました)。
それと、フフホト市は漢字で呼和浩特と書きますが、中国語ﾁｮｯﾄｼｶﾃﾞｷﾅｲぼくは読み方がわからなかったので乗り継ぎの空港で行き先を聞かれたときにだいぶ困りました。フフホト行きの飛行機に乗ったタイミングで初めて読み方を知りました(hu1he2hao4te4)。
空港の標識はこんな感じで、見たことない種類の文字があったのでウキウキになりました。空港からホテルまではタクシーで30分ほどでした。料金は50元(1元17円程度)程度でした。ぼくは中国に行きなれているのでいつものことでしたがタクシーの運転手がSNSで通話しながらスマホを操作しながら運転しているのでなかなか限界な空間です。ホテルはダウンタウンのど真ん中にあるみたいで、諸々の場所へのアクセスがよかったです。ホテルにつくと21階(スイートを除くと最上階)のかなりよさそうな部屋に割り当てられていてテンションがあがりました。
海外でお風呂がちゃんとしているのはポイントが高い
カラム：中国のスマホ事情
今回の旅での一番の失敗は、微信や支付宝などのSNS、電子マネーの準備をまったくせずに中国に行ったことです。去年トランジットで一瞬北京にいましたが、現金でのタクシー支払いを断られたりしてだいぶ電子マネーがないと生きていけない雰囲気になっていましたが、完全に忘却していました。SIMを差し替えているので、日本の電話番号もないし(SIMも電話番号なしのもの)、新規アカウント登録もできなくて困りました。一応微信はアカウントを持っていたのですが、100年間ログインしていなかったら二段階認証的なものが発動して困りました。SIMを差し替えると二段階認証が基本的にできないのでやばいですね。
中国だと街のほとんど至るところにレンタルサイクルがありますが、これの支払いも電子マネーなので厳しいです。まあぼくは足で歩くのがまあまあすきなので耐えましたが、やはり電子マネーを準備しておくに越したことはなさそうです。
フフホト市内
ホテルの部屋から見た景色です。ビルがあまりに多くて全然草原じゃないじゃん！と思うかもしれませんが、人がいない方向に10kmほど離れるともう草原があり、ゲルもちらほら見ることができます。
ホテル周辺を散策するだけでも雰囲気を楽しめます。お店の看板にモンゴル語が混じっているのがいいですね。ちなみに現地人にモンゴル語読めるかを聞いたのですが、全く読めないとのことでした。
(写真はシャングリ・ラホテルから塞上老街まで歩いたときの景色)
これ、ピンイン表記がバグっていないか
完 全 に 本 郷 三 丁 目
夜も街の中心付近は明かりが多く、出歩ける感じでした。気づいたら数箇所蚊に噛まれていてテンションが下がりました。
フフホト市郊外
フフホトはアルタン＝ハンが築いた南モンゴルの古都ですが、北側を見るとよさそうな山地が横に広がっていて、安全そうで街を作るにはかなり適した場所なように感じました(適当)。
大きな池がありました。きれい。
ゲルもちらほらありました。地盤をコンクリートで固めた固定式のものと、木でできた移動式のものがあります。都市化した窮屈な生活を嫌う人たちがわずかではありますが、こういった郊外で生活しているみたいです(by wikipedia)。
ちなみに、ここらへんまでは市内からタクシーで50元程度(20~30分)で行けますが、帰るためのタクシーがほぼ存在しないので、帰る宛を見つけてから行ったほうがいいです。ちなみにぼくはここで人生初のヒッチハイクをして市内へ戻りました。
近場(?)の観光地
希拉穆仁草原
発音はXi1la1mu4ren2です。最初見たとき中国語っぽさを感じなかったんですが(~murenってなんか英語とかにもありそうじゃないですか)思いっきり中国語でした。
道中からみた景色です。山岳地帯と草原地帯を走ります。
馬に乗れたりします。乗りました。もともと乗るつもりはなかったのですが日の入りまで時間をつぶすために乗りました。馬に乗ると戦闘時にだいぶ有利になるということがよくわかりました。首から上を狙われる心配がほとんどなさそうなので。その代わり馬につける鎧は重要だと思う。キングダム完全理解。
ゲルの中に入れます。チンギス・ハンが飾っていて本当に信仰しているのがわかりました。モンゴル式コール飲酒の儀を受けました。马奶酒といって馬のミルクでできたお酒を飲みました。しつこくなくて飲みやすかった。
9月下旬に行きましたが、結構草が黄色がかっていました。6,7月に行くと青々とした草原を見られるみたいです。人が多いらしいけど。
ぼくの影です。なげえ〜
草原からみた夕焼けと羊たち
他
フフホト市の東西南北にそれぞれ大きな観光地があるらしく、北は希拉穆仁草原で、南は老牛湾とよばれる、黄河が蛇行している一帯で、西は库布齐沙漠とよばれる砂漠、東には草原＋中国最大級の風力発電地帯があるみたいです。個人的には草原以外は、別にこの地以外でも体験できそうなものだった(砂漠は以前アラブ首長国連邦でそれなりに楽しんだ)ので、草原だけに行くことにしました。距離は希拉穆仁草原が市内から2,3時間程度で、他は市内から150kmほどするので、行き来するだけで丸一日かかります。
料理
これらはホテルのレストランの写真です。ここの名産はやはり羊肉で、あっさりとした噛みごたえのある肉です。日本だとあまり見ない気がするし、見たとしても脂の乗ったラム肉！みたいな感じで見る気がしますが、中国や中央アジアで食べる羊肉は逆にさっぱりとした感じがウリな気がします。パクチーと和えた羊肉を食べたのは初めてでしたが、かなり美味しかったです。あと黄河で取れた魚とかが食べられる気がします(黄河からは100km以上あると思いますが)。中国ではかなり魚料理が多いですが、川魚な気がします。唐辛子などのスパイスと組み合わせた料理が多くて、日本みたいに刺し身で新鮮な味を〜みたいなのは難しいです(これはこれで美味しいです)。
これは希拉穆仁草原で食べた羊の太もも部分の丸焼きです。クソ高かったです。一人で注文しても食べきれるわけがないのでだいぶ厳しかったです。
ちなみにホテルの朝食バイキングには日本食コーナーもありました(寿司はカリフォルニアロールだったので食べていません。そばを食べましたが麺が伸びていました)
まとめ
よかった点
- うーん、まあ行けたのが良かった
- 街が比較的平和だったし、きれいだった(重要)
良くなかった点
- 2,3人で行ったら費用が多分半額近くになっていた。たけえ
- 思ったより360度草原ではなかった。それはそう。そうだったら観光地にならない
- 車やバイク運転できる人なら自分で借りて回るのがよさそう(砂漠だったら私有地とかなさそうだけど草原はそれなりに放牧がされていて私有地とかありそうなのでめんどいかも)
最後に
う し た ぷ に き あ く ん 笑 っ て 何 ？ 笑
ゆるふわオンサイト2に参加した
before contest
普段会わない人と新宿でご飯でも食べようと思ったが、12:30頃に起床。そのまま会場へ向かう
contest
A, B, Cを開いて解く。速解き勢がいなかったためかFA。ちなみに見せ場はここで終了です
D: n-dwich box 最初、正規表現でも使って'||'でsplitして#の個数を数えようと思ったけど、'||'で愚直に区切るのはやばいことに気づいて時間を溶かし連続FAがきれる
E: usagi vs kame 実は入力が単調だったのでO(N)で解けたらしい。最近鈍っているのでこういうのでつまづきがちだと思っていたがサクっとかけたのでよかった
F: mneme game C, D, Eより簡単だった。三角数でmodとるみたいなことをやる
G: double range cards はじめ、カードが重なってる領域求めるのが面倒すぎると思ったが、よくよく考えると求める必要がなかった。
H: gori uho game 深さ優先探索を愚直実装した。TLE心配だったが爆速だった。冷静に考えればだいぶ枝刈りされるはず。
ここまで、経過時間は53分でしたが、多分1分以上考えた問題がなくて、だいぶ実装コンテストな印象を受けた。しかしコンテスト終了までこのままの点数でいることになるのである…
I: pino assort
制約を誤読してしまって、別々の箱に入っていると思っていた。pino assort買ったことねえ… にぶたんみたいなことをすればいけると思ったが、これに20分ぐらいかけてしまったため、残りの問題が楽そうだったらそっちやろうと思ってとりあえず飛ばす。今回の反省はpino assortを購入したことがなかったことですね#ゆるふわオンサイト pic.twitter.com/fobhP2c4TK
— Joe (@xuzijian629) September 14, 2019
J: swapping paths さすがにDPをするだけなんだけど、端に進めない場合があるので、数学ゲーではなくて、かなりしっかりとしたDPを書く必要があるっぽい。これを実装するぐらいならIをやると思って飛ばす。
K: fuzzy search queries Suffix Arrayのcount_substringの実装の中に現れるlower_bound, upper_boundの実装を流用すればそのまま解けそうという気持ちになる。点数的にもおいしいしこれを実装するのが一番楽だと思い、これを解くことにする。 Suffix Arrayを10000年見ていなかったため、単にlower_boundの結果から一つずつarrayをさかのぼっていくことをすればよかったところを、lower_boundの実装ミスを疑ってしまい、永遠にデバッグをしてしまう(普通にぼくの実装への勘違いが原因で、SAはバグっていなかった)。厳しい。蟻本もう二度と見なくていいかなと思ってたけど蟻本に乗ってたらしいし普通にもってこりゃあよかった。
L: 残り時間がなかったので1分ぐらい考えて、わからなかったので飛ばした。
結果
2400点でいろいろな人に負けた
after contest
- そすうささんと初めてしゃべった
- matsuさんとprdさんと、高速化の仕事ってやばくないかという会話をした
- matsuさんと、テストケース作成は闇！ｗやはりmod数え上げ！という話をした
- ぷにくんに中本食べすぎじゃないかと心配された
- う し た ぷ に き あ く ん 笑 っ て 何 ？ 笑って聞かれた。これ最近のオンサイトで毎回聞かれる。何？
個人的にあの問題セットは頭と手が両方ついている状態でも2:00で解き終わる気がしなかったので時間は2:30でもよかったんじゃないかと思いましたが、全完者もいましたし結果としてはベストな時間だったのかなと思うなどした。
問題あたりの考察要素は前回のゆるふわコンのほうがあった気がしますが(とくに前回のラストの問題で、距離の問題を最小費用流で解くものは初めて見て感動した)、今回もコンテスト・懇親会ともに存分に楽しめました。ありがとうございます。
そういえば2週間後ぐらいにGirigiriコンを開くかもしれません。コンテストを開くか開かないかのどちらかです。
GNU C++ ext/rope
ext/ropeの日本語の記事が皆無だったので使い方を書く。
できること
配列みたいにして使います。
- ランダムアクセス
- 任意箇所への要素の挿入
- 任意箇所の要素の削除
がでできます。
サンプルコード
#include <bits/stdc++.h> #include <ext/rope> using namespace std; using namespace __gnu_cxx; void print(const rope<int> &v) { for (int a : v) { cout << a << ' '; } cout << endl; } int main() { rope<int> v; v.insert(0, 1); // 0番目に1を挿入 print(v); v.insert(0, 2); print(v); v.insert(1, 3); print(v); v.erase(1, 1); // 1番目から1文字削除 (substrみたいに使う) print(v); }
結果
1 2 1 2 3 1 2 1
Macでchainerを使う(CUDA, cuDNNと)
CuPyのインストールはこちら
pip install chainer
して
import chainer
すると
>>> import chainer /Users/xuzijian629/.pyenv/versions/anaconda3-5.3.1/lib/python3.7/site-packages/chainer/backends/cuda.py:143: UserWarning: cuDNN is not enabled.
と怒られます。
stackoverflow.com が参考になります。
>>> from cupy.cuda import cudnn Traceback (most recent call last): File "<stdin>", line 1, in <module> ImportError: dlopen(/Users/xuzijian629/.pyenv/versions/anaconda3-5.3.1/lib/python3.7/site-packages/cupy/cuda/cudnn.cpython-37m-darwin.so, 2): Library not loaded: @rpath/libcudnn.6.dylib Referenced from: /Users/xuzijian629/.pyenv/versions/anaconda3-5.3.1/lib/python3.7/site-packages/cupy/cuda/cudnn.cpython-37m-darwin.so Reason: image not found
としてみると、dylibが見つからないと言われるので、明示的にシンボリックリンクを作ってやるといけました。ぼくの場合、cudnnはcudnnenvで入れたので~/.cudnn/versions/v6-cuda8/cuda/lib/libcudnn.dylibにdylibがあったのですが、このシンボリックリンクをCUDAのパスである/Developer/NVIDIA/CUDA-8.0/lib/以下に作ってやるとうまくいきました。
このあとimport chainerすると普通にうまく動きます
GPU対応Macでpytorchを使う
以前はcupyをインストールしましたが、今回もなかなかに面倒でした…
バージョンについて
最近のpytorchをビルドするにはCUDA 9.0以上が必要なのですが、CUDA 9.0以上にした状態でcupyをインストールしようとすると、nvccのエラーを吐かれる（上の記事参照）なので、今回は古めの0.4.1をビルドしました。cupyを諦めるか、一度インストールした状態だと最新版をビルドできるかもしれません（未検証）。
CUDA, cuDNNの設定をする
CUDAの設定はほぼできていたので、上の記事のままです。cuDNNについては、cudnnenvを使って8系をインストールしました。pip install v6-cuda8したあとに出てくる環境変数情報をしっかり.zshrcに追加しておきます。
Xcodeをupdateする
cupyのビルドは8未満にしなきゃいけませんでしたが、今回8.1にしました。
git cloneする
Mac用のpytorchディストリビューションはGPU非対応なので自分でビルドします。
が参考になります。
今回は0.4.1をビルドするのですが、一部のレポジトリがcloneできないので
How install old version pytorch 0.4.1 from source? · Issue #19457 · pytorch/pytorch · GitHub
に従って以下のようにします。
$ export CMAKE_PREFIX_PATH=[anaconda root directory] $ conda install numpy pyyaml mkl mkl-include setuptools cmake cffi typing $ git clone --branch v0.4.1 https://github.com/pytorch/pytorch.git pytorch-0.4.1 $ cd pytorch-0.4.1 $ git rm --cached third_party/nervanagpu $ (edit .gitmodules as described in the link) $ git rm --cached third_party/nervanagpu $ MACOSX_DEPLOYMENT_TARGET=10.12 CC=clang CXX=clang++ python setup.py install
1時間ぐらい待ちます。
import torch
torch.cuda.is_available()
Trueが出たら優勝！
TTPC2019に参加しました
team omorisuJoe(@omochana2, @risujiroh. @xuzijian629)で参加して5位（オンサイト2位）でした！
もともとteam Girigiriで参加すると思っていたのですが、ぼく以外のteam GirigiriのメンバーはTTPC2019募集開始日からすでに相手を決めていたらしく、会場であたふたしていたらすごすぎる2人組に拾われてチームが結成されました。
コンテスト中のムーブをまとめて行こうと思います。問題としては、A, C, F, Hを担当しました。
A (1:18)
[Joe] 貢献度0を回避するために無理を言って担当させてもらった。問題文を5文字ぐらいしか読まずにコーディングしてたらT年以降の開催年を求めるところをT回目の開催年を求めてしまい、一度すべてを書き直した。
B (3:16)
[risujiroh] これ提出時点で3位だったらしい。はやすぎる
D (13:39)
[risujiroh] ぼくのCがWAだったのでとりあえず先にやってもらった。
E (31:45)
[risujiroh] Cが永遠に通らないので先にやってもらう。
C (41:44)
[Joe] あまりにも合わないのでomochana2くんに投げようと思って問題を解説していると、の条件を見落としていることに気づいて発狂する。
__builtin_clz(a)はa = 0のときに32が返ると思っていたら未定義動作っぽくて16000ぐらいの結果が返ってきてびびった。7 WAして戦犯になる。
G (1:48:26)
[omochana2] 1時間ぶりの進捗。いつの間にか解かれていたという感じでびっくりした。
F (2:03:33)
[Joe] あまりにも考察が進まないのでrisujirohくんにとりあえず考えたことを報告しているとグラフがDAGであることを告げられる。これまで担当している問題すべてで誤読していることに気づいて非常に厳しい気持ちになる。DAGだし愚直DPを考えてみると愚直DPができることに気づくので実装する。通る。
M (3:10:22)
[omochana2] 初め実装をぼくがするかみたいな流れになって、アルゴリズムを解説してもらっていたのだが、解説してもらっている途中によりシンプルな実装方針を提案したところomochana2くんが実装を継続することになり、通してくれた。全方位木DPは多分どちらかというと苦手な実装なので助かった。
O (3:42:11)
[risujiroh] 実装がだいぶ気合だったようで、正解かどうかパッと見でわからないし、ジャッジをすぐには書けなそうだったので提出デバッグするか〜という流れになった。WA連発するかなと思ったのに初提出から10分程度ですぐにACになってだいぶびっくりした (2 WA)。実装がうますぎる
H (3:59:03)
[Joe] UnionFind的な操作は見えるが、クエリ逆順とか先読みとかの方針でもなさそうなので、愚直に状態をマージできるかを考えると、だいぶ重いけどできることに気づく。Implicit Treapを改造すると、Priority Queueの機能追加版で上位k個の累積を好きなkに対して返せるデータ構造を作れるのだが（kが定数ならpriority_queueを2つ保持すれば実装できる。詳細はPrioritySum）、これをちょっとさらにちょっと改造して、Pをpriorityとして、Xの供給があるときに最大でどれだけ需要を満たせるかを効率的に求められるデータ構造を作った。これをUnionFindのノードに乗せてやればよい。実装の本質はPrioritySum部分だが、これは自分のもっていたPrioritySumを今回のpriorityに対応させるだけで済んだので実は実際の実装はだいぶ軽かった。
K (4:07:38)
[risujiroh] 初め、omochana2くんがFFTでは？という考察をしてくれて、risujirohくんと練っていたところ、bitsetでいけるのでは？という流れになり
int n; cin >> n; string s, t; cin >> s >> t; reverse(begin(s), end(s)); reverse(begin(t), end(t)); bitset<101010> a(s), b(t), mask; if (a.count() != b.count()) { cout << "MuriyarokonnNaN" << '\n'; return 0; } for (int k = 0; k < n; ++k) { int x = ((a ^ b) & mask).count(); int y = ((a ^ b) & ~mask).count(); if (y <= x) { return cout << k << '\n', 0; } bool t = a[n - 1]; a <<= 1; a[0] = t; a[n] = 0; mask[k] = 1; }
というすごい短いコードで一瞬でACしてくれる。この時間にしてオンサイトFAだったみたいです。
間に合わなかった問題
I
これ初提出が1:37:46でだいぶ序盤から考察されていた。結果的にrisujirohくんが序盤に高速化を諦めたのが吉だったみたいで、彼はその後さまざまな問題を通してくれたので助かった。ぼくがあとを継いでいたが、解説のように事前処理をしてO(Q)に落としこむ方法に結局もちこめず、積の中でが何度現れるかをカウントする方針を高速化することを頑張ってしまった。
J
omochana2くんとrisujirohくんが終盤担当していた。答えがとした場合と
とした場合の答えの線形結合で書けることをrisujirohくんがすぐに見出し、OEISしたり
の解法を二項係数とか使ってO(N)に落とせないか、という話をしている間にコンテストが終了した。だいぶいい線までいっていたようで(?)惜しかったなという気持ちになった
最後に
こうしてみてみると全員それなりに貢献できたんじゃないかと思う。序盤大量にWAを出してしまったことや誤読しまくったことや、コミュニケーション不足で気づいたらrisujirohくんもぼくもIを解いていた、みたいなことがあったが、自然と修正されて後半はかなりコミュニケーションがあった気がする。とりあえずオンサイト2位で非常にうれしいです。
楽しい問題を揃えてくれた運営の方々もありがとうございます。
そういや最近じ ょ え た ぷ に き あ く ん 笑と対面で呼ばれる機会増えました。何？
う し た ぷ に き あ く ん 王 国 笑 っ て ど こ 笑 pic.twitter.com/qi9NvAcels
— Joe@TTPC (@xuzijian629) August 31, 2019
