sataniC++

C++、競プロ、数学などについて色々考えたりします。

University CodeSprint 4 - Magic value

University CodeSprint 4にて50位でパーカーゲットしました!
しかし,題にもある"Magic value"という問題が解けず….

そこで復習したところ得られた知見も多かったため,スライドにまとめました.
(とはいってもEditorialと言ってることはほぼ同じです)

なお,他の問題についてはここに簡単な解法を書いてあるのでそちらを参照してみてください.
(リクエストがあったら別記事を作るかもしれません)

Magic value

問題文

コード

コメント

ans_minはGCDの性質をうまく利用する,
ans_maxはConvex-Hull Trickを遅延セグ木上で展開する,という部分がポイントでした.

ちなみに,「Convex-Hull Trickを遅延セグ木上で展開する」というのは簡単に調べたところLi Chao treeと呼ばれているものに近い気がします(?).


次回も100位以内を目指します!

World CodeSprint 12 雑多解説

World CodeSprint 12にて,ついにコンテスト中全完してパーカーゲットしました!
嬉しい勢いで解説記事を簡単に書いておきます.

なお,コンテスト中に個人slackで書いてたやつのコピペなので,結構適当だったり微妙に間違ってたりするかもしれないのでそこはご了承ください.(いつかちゃんと書くことがある…かも?)


テンプレが長いので初めに示して,問題解説では主要部分だけ書いておきます.
(マクロ多いので見づらいですが,REP,RREP,FOR,RFORはfor関係,VAR,VEC,VEC_ROWあたりは入力関係,OUT,SP,BRは出力関係です)

続きを読む

DISCO presents ディスカバリーチャンネル コードコンテスト2017に参加しました

DISCO presents ディスカバリーチャンネル コードコンテスト2017(DDCC2017)の予選を通過できたので,本選にも参加してきました.
そこであったことなどを書いておきます.
(競プロ成分は少なめです)

続きを読む