ゼータ変換とは ゼータ変換とは、$n$ 次元累積和のことです。 $2$ 次元の場合を考えてみましょう。 $n \times m$ の数列 $A$ に対し、 $$ B[x][y] = \sum_{i = 0}^x\sum_{j = 0}^yA[i][j] $$

:::warning パスポート有効期限が入国時に 3 ヶ月以上残ることを確認しておこう ホテル・飛行機はなるはやで予約しよう クレジットカードを複数の国際ブランドで持っておこう 現金はあったほうが良い (なくてもなんとかなる) 4 人での移動なら結構タクシー (Uber / カカオタクシー) を使うべき。 SMS 認証は日本で済ませておこう WOWPASS は便利。T-money へのチャージは iPhone のみ対応 :::

参考資料 : https://www.cmi.ac.in/~ramprasad/lecturenotes/comp_numb_theory/lecture17.pdf 素数判定問題 $n$ bit $(n ≥ 2)$ の整数 $x$ が与えられる。$x$ が素数であるか判定せよ。 素数判定問題は co-NP $x$ が素数でない証拠が与えられたとき、$n$ の多項式時間で $x$ が素数でないことを検証することができるならば、素数判定問題は co-NP に属すると言います。 例えば、以下のようにすれば、多項式時間で $x$ が素数でないことを検証することができます。

 for 文でヒルベルト曲線状にアクセスしたいです。しかも、次の位置への移動をできるだけ高速に行いたいです。どうすれば良いでしょうか？ 解 矢印の向き (縦 or 横) と 行/列 番号が増えるか (+1 or -1) に分けて考えます。増えている矢印には赤の色を付けてあります。

:::spoiler おきもち GCC インストールせずともこれだけで環境ができるならこれでいいんじゃないでしょうか 特に VSCode のデバッグ環境は Clang + LLVM じゃないときびしい！ ::: https://qiita.com/Atsu30/items/6a4c4c070dd76a236fdc に書いてあったが、Xcode v12.5 から Xcode の標準ライブラリがあるフォルダが変わっている。

ICPC 国内予選は今年からルールが大きく変わり，事前の電子的準備が可能になり，提出までに 6 分の時間制限が追加されました． 並列化の威力 AOJ への移植 を見ればわかる通り，ICPC 国内予選の問題は想定解が 8 秒 (定数倍を考えると 3 秒程度が妥当か) 以内に実行が終わるように設計されていると考えられます． しかし，実際の競技では時間制限は 6 分 で，その他の操作を取り除くと，5 分半 (330 秒) 程度をプログラムの実行に使うことができます． $\Theta(n^2)$ の計算量を $\Theta(n \log n)$ や $\Theta(n)$ に落とすような問題を考えてみましょう． 入力長はそこまで大きくしたくないので，$n = 10^6$ 程度が妥当でしょう． 1 秒間にできる "計算" の回数を $10^9$ 回として，$n^2$ 回の "計算" が必要な愚直解で計算すると，$10^{12} / 10^9 = 10^3$ 秒となり間に合いません．

$X, Y$ の近い方までの距離を最大化する頂点 $a$ について考える スクリーンショット 2024-03-27 21.00.03 $X - Y$ パスの中点で二分すると，左は $X$ の方が近く，右は $Y$ の方が近い スクリーンショット 2024-03-27 23.08.23 $a$ が左側にあると仮定すると，$a$ は左側に属する頂点の中で最も $X$ から遠い → 左側の木の直径の端点である

注意 : ここに書いたコードの verify はしていません 長さ $2n$ のセグ木にする 非再帰セグ木サイコー！ 一番すきなセグ木です p.35 struct SegmentTree { int n; vector<T> seg; SegmentTree(int n): n(n), seg(n * 2) {}

これめちゃくちゃ高速化の余地だよな pic.twitter.com/AOpexViDUj — tatyam (@tatyam_prime) February 21, 2022 $\bmod p$ で掛け算をするとき、以下のようなコードが現れます。 uint32_t mod_mul(uint32_t a, uint32_t b, uint32_t p){ return static_cast<uint64_t>(a) * b % p; } $p$ が 32 bit であるとき、$a \times b \bmod p$ を計算するコードです。$a, b$ が 32 bit なので、$a \times b$ を 64 bit で計算する必要があります。 これをコンパイルした結果のアセンブリを見てみましょう。

1 年目と 3 年目の分で WF に行ったので、WF 2 回制限で選手を引退 院生以上でないとコーチができないため B4 の JAG スタッフが誕生… Day 0 11:00 集合 列車遅延で 11:05 到着 机はすでに設置されていて、ディスプレイとかの機材の設置が行われていた (業者がやってくれるらしい) 延長ケーブルの配線をする 配線を動かないように養生テープで留める

変数は箱である？ a = 1 と書いたら、箱 a に $1$ を入れる box.png b = a と書いたら、箱 a に入っている $1$ をコピーして箱 b に入れる box.png というのはよくありそうな説明ですが、 Python の実態に即していません。実際、リストを使った時に混乱を招くことになります。

Wolfram Language を覚えよう Wolfram Alpha はそれっぽく書けば AI の力でうまく解釈してくれるんですが…  長すぎると解釈してくれないことがあります。 簡潔に書ける Wolfram Language を覚えましょう。 

マラソン:running: 問題 https://oj.uz/problem/view/IOI10_languages https://www.ioi-jp.org/ioi/2010/tasks/tasks_jpn/day1/t4_language/index.html IOI では 56 の言語が使われています。 それぞれの言語の Wikipedia からランダムにページを選び、本文の連続する 100 文字を取り出してデータセットを作りました。 データセットでは、 1 つの文字に 1 〜 65535 の値がランダムに、 1 つの言語に 0 ~ 55 の値がランダムに割り振られています。 長さ 100 の数列 $E$ が与えられる → 言語を予測する → 答えが返ってくる

問題文 https://www.ioi-jp.org/ioi/2007/problem/day1/sails-prob-j.pdf https://oj.uz/problem/view/IOI07_sails 船に $N$ 本の柱が立っていて、 $i$ 本目の柱の高さは $H_i$ です。 柱は $H_i$ 個の区間に分かれていて、そのうち $K_i$ 個を選んで、帆を張ります。 ある帆の非効率さを その帆と同じ高さで、かつ前にある帆の数とします。 帆の非効率さの総和の最小値を求めてください。 $N ≤ 100000$

tatyam 原案問題を集めました 自明 問題 難易度 コメント トラックの移動 500 時事問題

スニペットを失ったことだし modint を書き直したいな〜 ACL の modint をベースにいい感じの modint を作ろう 追加機能 operator>>, operator<< で入出力できるようにしよう 2_M のように、suffix をつけて modint を作れるようにしよう constexpr に対応しようちょっとしたところがコンパイル時に計算されてうれしい ついでに mod を uint32_t にしてみよう

まえがき LARSCH の読んだので解説記事を書こうと思ったが、説明が難しくてなかなか書けない… Monge を理解していきたいので Monge の記事を書きます。 完全に理解しているわけではないのでご了承ください。 Monge の読み方 もんげ〜 と読みます。嘘です。 Monge の定義 実数からなる $N \times M$ 行列について考えます。

[1] グリッドにする 犬のみを取り出した時 / 猫のみを取り出した時 の順序を固定すると、以下のようなグリッドグラフの左上から右下への最短路になります。 このとき、各マスにおいて、マスの左上から右下に行くときに 右折 / 左折 をするべきかどうか考えます。 例えば、このマスでは、$3B_1 + 2A_5 < 4A_5 + 5B_1$ なので、このマスで右折するべきではありません。 これを全てのマスに行うと… 右上と左下の範囲に入れなくなります。

今日は aising2020 F - Two Snuke (Diff : 2741) を解けるようになっていきましょう。 母関数 (generating function) 母関数とは？ 数列 $A = (A_0, A_1, A_2, …)$ の 母関数 を $$ A(x) = A_0 + A_1x + A_2x^2 + \cdots = \sum_{n = 0}^\infty A_n x^n $$

不等号に注意 問題文 https://apio2020.toki.id/assets/statements/swap_ja.pdf https://oj.uz/problem/view/APIO20_swap $N$ 頂点 $M$ 辺の重み付き無向グラフが与えられる。 $Q$ 回の以下のクエリにオンラインで答えよ。 頂点 $X, Y$ から同時に車が $1$ 台出発し、頂点 $Y, X$ に向かう。 しかし、道は車 1 台分の幅しかないので、途中で方向を変えたり、すれ違ったりできない。