Weekly Contest 153 : 1187. Make Array Strictly Increasing

Pythonで書いてあった解法を見て書きました arr1のある位置までで構成できる単調増加列について、最後尾の値をkey, その場合の置換処理の最小回数をvalueとしたdpを考える。それをHashMapでdpとする。 初期値として dp[-1] = 0 を入れておく。 あるarr1上の…

Java(Kotlin)で遅くなる書き方まとめ

こうすると遅い!!! 理由 約10^5回の差分 遅い提出 速い提出 FastScannerでなく標準ライブラリのScannerを使う 400ms カツサンドくん β カツサンドくん β FastScannerでなくkotlin.io.readLine()!!.split(" ") 260ms カツサンドくんβ カツサンドくん β PrintW…

Rustの演算子優先順位表

載っているサイトがいまいち見つからなかったので、プログラミングRustから引用する。 上ほど優先順位が高い。 名前 例 タプル/構造体フィールドアクセス、メソッド呼び出し、関数呼び出し、インデックス point.x, point.m(), stdin(), arr[0] エラーチェッ…

HashMapでdpすることができなくもない

概要 RustのHashMapのラッパーを作ってIndex, IndexMutトレイトを実装すると配列のように使えて便利 でも流石に大きな定義域でループを回すとTLEする HashMapをindexで参照と可変参照できるようにする github.com 昔はあったらしいHashMapのIndexMut実装は↑…

ローリングハッシュ法でご丁寧にmodを取っていると時々TLEする

概要 競技プログラミング 文字列検索の問題 内容 2つの互いに素な数をB, MとしてBの(係数つき)べき乗の和をmod Mしてハッシュを取る M=2^64 としてunsigned intで計算してオーバーフロー前提で計算すると速い Rustだとリリースビルド以外は普通オーバーフロ…

VSCode 拡張の SVG Editor つくった

VSCodeマーケットプレイスはここです ! まだSVGの色々な記法に対応できてないです... previewHtmlコマンドというのがあることを知って、これならなんでもできるじゃん!てことで作りました。VSCodeの現在適用されているテーマの色とかが取れないんですが、透…

(Scala)ある型クラスを実装する任意クラスのインスタンス列が持てるやつ

適当にググってもでてこないのでうんうんうなっていたらできた。僕みたいなうなり声を上げる人が少なくなるようにブログに書いておきます。 ある型クラス F を実装するクラス A, B, C, ... があって、それらのインスタンスの列を引数にとってどこかのクラス …

とあるゲームの最大連勝数の期待値

勝率p = 0.6のゲームがあったとして, x回やったときの最大連勝数の期待値E(x)はいくつか? という話. (元ネタは人狼オンライン...) 式を考えるのが面倒だったのでPythonの練習がてらモンテカルロる(誰か式教えて...). 最大連勝数の期待値 結果 | x | E(x) | |…

院試の昔話

昔々あるところにおじいさんとおじいさんとおじいさんとおじいさんと... 同期が院試(東京大学大学院 情報理工学研究科 創造情報学専攻)について書いてたから何となく書いとこうかなってなったでももうあんまり覚えてないや…受け方は京都も東京も以下の同期の…