メモ

知らなかったできることのメモとか

1e18+3(codeではll 1LLe18+3)は素数
inv(1e9+7) mod(1<<64) = 13499267949257065399ULL ←これよく考えたら普通にオーバーフローさせながら計算すればよかった
DAGにpathを何個書けば頂点が覆えるか->bipartite matching
和がnになるような1以上の整数達がいる時、種類は√2nくらい (よく考えたら自明だった)
負辺min_cost_flowははじめのポテンシャルだけBellmanFord
木DPでstackoverflow->先にbfsでtopological orderをとる
二人ゲームで手番数が決まっていて相手の手をキャンセルできる手が打てる場合のmin-maxは手番数kとするとk=1,2しか考えなくて良い
挿入,削除ありのk番目の値→setで先頭k個を持つ
Z-algorithmでs[i~]とTのpfx が全部求められる
1文字違い→前からの一致+後ろからの一致=N-1
stack→区間DP
幾何で角度区間のマージ←ベクトルでやると楽かも(ただしもとより180度以上ずれてるとまずそう)
n次関数を足す→差分を取る(BITのあれみたいなのもあるけど,そもそも持つ値を差分にする も有用)
平面上4方向は45度回転で独立なx+y軸,x-y軸になる
数列で大小関係みたいな問題は平面上の点だと思うことが多い そうじゃなくてもdpとかを視覚的に表す方法があるならそれを考えるのもあり(というか図形に落として考えるのが苦手すぎる)(ex.LIS)
tの上限が1e9とかで答えがtの多項式であることがわかってるなら,小さいtについて求めて多項式補間もありうる(数え上げで結構ありそう)(わかんなければ実験も良さそう)
全部がうまく行ってるか みたいなのをクエリごとにはやく判定するためには,何個うまく行っているかを持って更新する 例えば後退解析とかでも,そこに行ける状態の内何個を処理したか を持っておき,それが全部になったらやる、みたいな
DPをデータ構造で高速化するのは貰うDPがいい(範囲のsumやmaxを一気に取りたいんだから).
dp[i]からdp[i+1]への遷移を何も考えずにsegtreeに載せると、区間を意識しなおさなくても連続部分列に対するクエリに応えられる.
連続なものはとりあえず離散的な数え上げ+簡単な積分 に落とす,たとえば∫max(a,min(b,c)) みたいなのはa,b,cの大小関係を決めたものをすべて考える.
こうするとuniform distribution[0,1]からN個独立に取ってきた時のi番目(1-indexed)の値の期待値は? になって、式を描くとベータ関数になることがわかりi/(N+1)になる. (i+1番目)-(i番目) がiによらないので1/(N+1)になることを考えるとわかりやすい.
遷移する順番が関係ないDP→
なんらかの順序でソートすると一部のキーを消せることが多い.あとcount系なら戻せる.
あとこれは最短路問題に落とせて、例えば常にコスト1でbfsになるなら計算量は変わらない.
しかし、「状態を一部に制限しても最短経路が存在する」しかしdpの順としてはこのようなものを実現するうまい順は存在しない,というような状況だと、bfsの方が計算量が良くなる場合がある.
ex:絶対値がK以下の整数がある、何個足せば0にできますか→DPだとO(K^2)状態になるが、bfsだとO(K)状態.

大学/大学院の間に読んだ本

ytsmiling.tech
これを読んで、こういうふうにまとめるのいいなと思ったので僕もやってみようと思います。このリンク先はかなり(特にモチベのある人にとって)役に立つと思います。僕はといえばかなりカス競技プログラミングばかりやっていたので、一般にオススメできる本ばかりでもありませんが、まあそもそもおすすめのためというよりかは備忘録なのでご了承ください。

プログラミングコンテストチャレンジブック

言わずとしれた名著。いろいろまとまっているし、意欲があるならどのレベルの人にもおすすめできます。今ではカバーしきれてない典型も多くありますが。

ゆるゆり

言わずとしれた名作。タイトルの通りゆる〜い感じなので百合姫のなかでも特におすすめできます。アニメも面白かったね〜って。既刊は17とちょっと一気買いするには多いですが、気づいたら読んじゃうのでちょっと読んでみましょう。

私の百合はお仕事です!

ガッツリこのジャンルにはまったのはこの作品からな気がします。設定が天才なんだよね。10話でイェーイとなり、11話でウオーとなるので、なります。

気づいたんだけど僕自身オタクの感想見るのあんまり好きじゃないからやめたくなってきちゃったな、一発ネタにしては量が多くなる予感がしているし・・・

捏造トラップ

重いよ〜〜〜

たとえとどかぬ糸だとしても

重いよ〜〜〜2

NEW GAME!

絵がめちゃくちゃかわい〜〜〜

ななしのアステリズム (完結済)

よかった〜〜〜めちゃくちゃよかった、本当におすすめです

やがて君になる (完結済)

最近話題になったので聞いたことある人もいるかもしれませんが本当にマジでおすすめできます、同じ作者の作品はすべておすすめです、天才なので

ぐらんぶる

アホやってて楽しそ〜〜

ふらいんぐうぃっち

アニメが良かったのを思い出して不意に買ってしまった、雰囲気がすごくいいしキャラもかわいい

熱帯魚は雪に焦がれる

二人が仲良くしていてうれしいです、

将来的に死んでくれ (完結済)

ギャグ寄りです、よかった

思春期ビターチェンジ (完結済)

マジで良かったです。関係性・・・

お兄ちゃんはおしまい!

ダメ人間がかわいいと・・・うれしい!

ふたりべや

マッチングが確定してる重い話がないゆるい系のやつ大好きで、それです。
はじめはゆるゆりぐらいのゆるさだと思ってたら、どんどん話が進んでいきマジで共依存みたいになってるし、うれし〜〜

三ツ星カラーズ

アニメからでしたがめちゃくちゃどハマリした、ライブとかにも初めて行ってしまった。
マジでクソガキなので、それが嫌って人もいるみたいですが僕はめちゃくちゃ好きです

苺ましまろ

マジでクソガキ2、順序的にはこっちが先ですが

八雲さんは餌づけがしたい。

だんだん関係がすごくなってきてない?大丈夫?

喧嘩稼業

kindleの中でこれだけ異彩はなってるんですけど、面白いです

薬屋のひとりごと (ヒーロー文庫の方)

コミカライズ2種類あるんですが、こっちのほうがすきです。

くま クマ 熊 ベアー

くまべ

はなにあらし

読むとイェーイとなります

不揃いの連理

twitterでほぼ全部読めると思う、めちゃ良かったので購入した、いいです

世話やきキツネの仙狐さん

生活力があるの本当に羨ましいな

みらいのふうふですけど?(完結済)

OKになった

2DK、Gペン、目覚まし時計。(完結済)

良かった!!自身を持っておすすめできます、9巻で完結済。
基本的に生活力がないやつとあるやつがペアになってると嬉しい、俺の周りには生活力がないやつしかいない

吸血鬼ちゃん×後輩ちゃん

ちょっと悲し〜 けどめっちゃ百合してた

アクタージュ

ジャンプ連載中、すごい

ギャルとオタクはわかりあえない(完結済)

終わっちゃった〜 よかったです

ささやくように恋を唄う

まだ2巻読んでないけど、よいです

それでも歩は寄せてくる

高木さんの作者の人、相変わらずめちゃくちゃかわいい

くノ一ツバキの胸の内

同じく、めちゃくちゃかわいい

SKET DANCE

twiterで無料公開されてた分を読んでて、気づいたら全巻買ってしまった
面白かったです。

性別「モナリザ」の君へ。

まだ3巻までしか出てませんが、続きがめちゃくちゃ楽しみです

すべてがFになる

あまりにも活字を読んでなかったので読んでみた、まあまあ楽しかった

徒然日和

ゆるくて、良いです

飛野さんのバカ

どっかのサイトで公開されてると思う、かわいくて良いです

まちカドまぞく

めちゃ良となります、おすすめです

ブルーピリオド

実力の話する漫画ぜんぶこわいけどすき

イケメンすぎです紫葵先パイ!

かわいかった

少女終末旅行

よかった、世界観すげ〜

ちいさな森のオオカミちゃん

ジャンルとしては絵本が近いんじゃないか?めっちゃかわいい

拡散的エモーション

昔インターネットで見てたぱげらったって人の漫画です、オエカキストとか好きだった

欠けた月とドーナッツ

twitter宣伝につられて最近買ったんですが良かったです、2巻が楽しみ

上伊那ぼたん、酔へる姿は百合の花

女の子たちがお酒を飲んでいるぜ

鬼滅の刃

なんか話題の割に周りに全然読んでる人がいないのでなんとなく6巻まで読んだんですが、まだそこまでハマってはない

組合せ最適化

たまに眺めてます

ON NUMBERS AND GAMES

面白いです

ヤング図形の話

ヤング図形の話がのっています

いかがでしたか? 今回は「大学で読んだ本」についてまとめてみました!4月からエンジニアなんですが俺どうしたらいい?

TTPC2019

海に潜っていたので不参加でした。

〜終〜

後から解いたら面白かったので各問題についての感想?を並べます(ネタバレあり)


A. 無
B: 無、titech分解みたいに引っ掛けがあると思ったらそれもなかった(まあかんたん枠だからね)
C: 無 (入力 > X をはじいてしまい1敗)
D: 7のgrundy数が3なのがちょっと面白かった、SRM easy にありそう
E: N-1 * N-1 で全0 を作ろう → できた
F: DAGだということにかなりの間気づかなかった、気づいたらかんたん
G: K=1 がコーナーケース、こういうちょうどK回みたいなのはparityかK回以下 にしてしまってもいいケースが多いと思う

H:
おまたせ
map使うBITを使った、値を得るときにcountを見てから値を取得しないと計算量ベースで悪くなる気がする
思考停止で座圧したほうがいいかもなあ

I:
なんか解けそうだけどだるい方針ばっかり思いついたけど、適当に小さいのを計算すればCRTすらいらないのでわりと楽かな

J:
pathごとに線形性使って足すの賢いなあ (は?)
実験したら片方はかんたんな数列だったのでもう片方もごり押しした

K:
面白い、AGCとかにも出せそう
右とどこかスワップ→全体右シフト に言い換えれば整理して終わり

L:
なんの疑いも持たずに O(5^K * |S|) を出したらTLEして、厳しいなあっていいながら定数倍改善したら通ったんだけど、想定オーダーじゃなかった・・・
想定解面白いね、こういう系で半分前列挙は見たことあるけどここまできれいじゃなかったと思う

M:
おまたせ2
これは本当にいくらでもやりようがあるんだけど、逆にそのせいでめっちゃ悩んでしまう(1つの方針を書いてても嫌なことがあったら別の方針に変えちゃうとか)
こういうのはだいたい何やっても多少はだるいから多少は諦めようね
ちゃんと一つ動かしたときの差分にすぐ注目できたのは良かった(最近見てなかったけど)

N:
かなりすき、このセットの中でいちばんすき

まず実数を選べると思ってgrundyを求めるといい感じに周期的になる
Yuriくんはそんなに強い制限を受けてなくて、Muriくんはピッタリが選べないのがつらそう
Yuriはgrundyで勝ててれば勝てる、その他のケースでMuriが勝てるのはどういうときか?
w = l は詰みで、他にも詰めろが結構ある
落ち着いて考えると詰めろの必要十分が列挙できる
詰めろがこれらだけなのは、Muriは適切な操作が1回できればそのあとは自由なことと、十分大きいwではYuriはuをとらないと適切な操作ができてしまう みたいなことからわかる (他にも色々考えたけどだいたいこんな感じ)

非対称なゲームで結構やばいんだけど、うまくできていると思った(こなみ)

O:
なんか瞬殺できた、運ゲー

2019
32 32
################################
#S............................T#
#.#.##########################.#
#.############################.#
#..............................#
#.#..#########################.#
#.############################.#
#..............................#
#.#......#####################.#
#.############################.#
#..............................#
#.#.......####################.#
#.############################.#
#..............................#
#.#........###################.#
#.############################.#
#..............................#
#.#.........##################.#
#.############################.#
#..............................#
#.#..........#################.#
#.############################.#
#..............................#
#.#...........################.#
#.############################.#
#.############################.#
#.############################.#
#.############################.#
#.############################.#
#.############################.#
#.############################.#
################################

なんかはじめ微妙に足りなくて双子マラソンか?って思ったけどpopcountが11にならないことに気づいてそうだねってなった


運営お疲れ様です、このボリュームのコンテストはなかなか無いから出たかったな〜

JAG2018 夏合宿

にオンサイト参加しました
びっくりしたんですけどもう5年めなのでほとんどの人が年下だった・・・ 老害

1日目:
(コンテストにすら)遅刻
シミュレーションしながらものをマージしたりするやつを思考停止でid,もの のmapをもったらTLEした, listならlog解除できるけどっていってmaroonに一から書いてもらった あとはボーッとしてたらコンテストが終わった 僕は真に0AC
最後は一旦書いたのでライブラリに入れていたと思っていたけど入ってなかった、かなし

AGCがあった
Eの考察がちょっと間に合わず

2日目:
(writer陣なので)遅刻
ちょっと白い目で見られた
コンテスト開くと裏でいろいろ見たりゆっくりできるので面白いです
参加ありがとうございました
Dが一番好きです(まあ知識が必要なんだけど、めっちゃよくできてる)

OpenCupがあった
つらい回だった
Dの考察とFをやった
でもGとかをワイワイ考えるのはちょっと楽しかった

3日目:
遅刻しなかった
Bで入力が逆順だと思ってWAを出す(は?) よくみたらサンプルが合ってなかった(は?)
Gやべー解法しちゃった(数を一気に遷移するんじゃなくて今作ってる数もキーにもって一文字ずつ遷移)
Hおもしろかった

notさんすごい

帰った

反省:
初手パソコン系でグダグダしてその流れでグダる事が多いので慣れる
紙コーディングはいいけどその前に少し落ち着いて解法全体の正当性を考える

FHC 2018 r2

開始前: ねむい
Sentimental Venus という曲を聞いてウキウキしていた

A: へーこんなの解けるのか
適当にでかくなりそうな例を作る
渡る辺の重みはどんどん小さくなるから実際これがベストっぽい
./a.out < A.in > A.out ってしたらこわれてexpiredしかけたのでこのPCで出るときは注意

B: 読むだけ
Core Dumped して???になった
いろいろ確認してたらexpired
嫌な気持ちになりながら切り替えてCに行く

C: はえーおもしろそう
お絵かきしてみる
_|- みたいなのがあったら切れて、縦横両方向にこれがなければいいのでは?
全く数えられる気がしない
あきらめてとりあえずD読む

D: 普通に問題っぽい
入力が嫌すぎるだろ
ちょっと考えてCに戻る

C:
冷静に考えると2個でいいな
Sの方から見てくと適当なDPになる
書く
バグる
なおす
Bの失敗を鑑みて手元でテストしてからinをダウンロード

D:
図を書いてもよくわからなかったのでとりあえずDPを考える
普通に実家だった
stackで今のoffsetを持っておけば実装が楽(左端はクエリ投げるときだけ変えて、offset変更のときには無視する)
眠かったので微妙にバグらせた
テストせずに(は?)出した

ねむ

例年よりかなり問題の質が良いのでうれしい データ構造ゲーといっても今年のは面倒とかじゃなくて小奇麗な感じ(は?)

B: スタックオーバーフローだったっぽい 最近踏んでないから忘れてた デバッグオプションのGLIBC系のせいで制限超えてしまったっぽい? 外したら大丈夫だった
というか速度の問題もあるしinに対して実行するときはdebugはずそう(提出したあとにやればいい)

MUJIN 2018

開始前: 賞金あるやん!ありがとうございます 海外勢もいないし頑張りたい

A,B:無
C: Bとの落差で少したまげたけどやるだけ
D: 設定が意味不明すぎて混乱したが結局サイクル検出のようなことをやればいい バグるだろうなあと思って書いたらバグらなくてたまげた サイクル検出はライブラリ化してるけど、それの最終状態でvis=1になるやつをcountすればいい(自分用メモ)
E: また迷路かよ… よくあるdijkstra亜種, 辺の長さが今いる時刻によって変わるけど、別にトポロジカル順に見れることに変わりはない
F: 去年のTCO final でみて結構なるほどなって思った 大きさ順でdpしていくと候補が増えていくDPになる
G: 係数a,b,cとしてabc空間を考えると三角錐みたいになる, 同値条件を考えるとa-a' : b-b' : c-c' = A:B:C ただしA,B,CはAp+Bq+Cz=0なるもののうちgcd=1のやつ になるので、同値類を数えたければ(a,b,c) in X かつ (a+A,b+B,c+C) notin X みたいなのを数えれば良くて, 式立てればできる まあ式を写し間違えて死ぬほどバグらせたんですが

H: それになりうる状態のmaskを持ってDP みたいなやつ たまに見る(ex. 去年のTCOのbreakfastみたいな名前の問題)
実際は状態が少ない 系
慣れてないと実装がちょっと混乱する 集合の集合が出てくるし
元のDPを考えると、DPのキーの集合がキーになる

CF #500

大失敗。


記念すべき500回目らしい
出ちゃうか
6問

C読む
うーん
とりあえずAに行く

A:
Aにしてはむずくない?
AGCのyosupo回でみた
mxとmnが同じ側なら幅N最小で違う側なら半分ずつだな

B:
できる限り操作をすると長方形いくつかになる
これを得れば答えもすぐわかりそう
(x,y) と (x,y') に辺を生やせば
冷静に考えると x-y で辺を生やせばいいな
答えは連結成分-1

C:
取るべき値は少ないので現在の値を持ってDP?
ちょっと面倒そう
選ぶやつを固定すると、適切な位置でコストを発生させれば (何個選んだか, 直前選んだか, 2狛江選んだか) でやれるな
TLE
は?
内側でK * 3 の vectorを毎回宣言してたのを外側にしたらTLEが取れた
5000 * 2500 * 3 でこんなに遅いのか・・・

順位絶望だったが順位表見てもD以降全然解かれてなくてたまげる
とりあえずD読む
D:
はえ
とりあえず手でいろいろ試す
連結成分の数は高々2しか減らないことによる下限があるな
(abab,baba) みたいなのならこれを達成できる
2kなら一回使えば↑の王道ルートに乗せれそう?
2k+1 も一回使えばいけそう こっちはこれで最適
逆から考えると場合分けがわかりやすいな

何通りか場合分けして書く
WA
えー
場合分けが足りてないことに気づく
書く
WA
えー
手元で試すとまだ場合分けが足りてないことに気づく
終了

結局a abab みたいなケースは2回ですら無理だったのでまだおかしかったんですね

異常な場合分けによらない解法:
2減らせるなら2減らす, みたいな貪欲を実装すればよかったっぽい?
yosupoのコードはかなり短かった

反省:
実装方針(こいついつも同じ反省してんな(いや今回は行けると思ってしまったのがなあ... 実際もうちょい時間あれば行けたとは思う))


E,F: まだ読んでない