Competitive Programming Editorial & Misc Articles

問題リンク

https://atcoder.jp/contests/abc419/tasks/abc419_f

問題概要

長さ $L$ の英小文字列であって、$S_1,S_2,\dots,S_N$ をすべて部分文字列として含むものの個数を数え上げよ。

制約

• $1\le N\le 8$
• $1\le L\le 100$
• $N,L$ は整数
• $1\le |S_i|\le 10$, 英小文字からなる文字列
• $S_i\ne S_j\ (i\ne j)$

解法

素直に DP する。ここで、各文字列が既に部分文字列として含まれているか ($O(2^N)$ 通り)、およびその文字列の suffix が重なる最長の prefix が状態になる。各文字列の prefix は $M=\sum_i |S_i|$ 個で、DP は全体で $O(2^NML\sigma)$ で動く (ただし $\sigma=26$)。

2023 年の AtCoder 言語アップデートで新しく使えるようになった C# の機能について、競技プログラミングの観点で使えそうなものをピックアップします。

Native AOT

新しいコンパイル方式で、ネイティブのバイナリに変換してくれます。理論上 C++ 並みの実行速度を期待できるので、 C#er にとってはこの上ない福音でしょう。

問題にもよりますが、C++ と C# (JIT) の間くらいの実行時間になります。もちろん、旧来のコンパイル方式 (JIT) も利用可能です。

C# は仕様や機能が比較的モダン [要出典] ながらも、その歴史とともに多くの仕様を追加して増築を繰り返してきた言語です。

また、仕様が大きく異なる多様な処理系が存在したり言語仕様が昔の処理系では非常に不便だったりします。

そのため、コーディングの感覚が実行環境によって比較的左右されやすい言語です。

公式解説と全然違うことをしている……。

問題リンク

https://atcoder.jp/contests/agc027/tasks/agc027_d

問題概要

$N$ が与えられます。次のような $N \times N$ 行列 $a$ を構築してください。

• $1\le a_{ij}\le 10^{15}$
• $a_{ij}$ は distinct
• 隣接する要素 $x, y$ について、$\max(x,y) \% \min(x,y)$ の値は正かつ全て同じ

制約

• $2\le N \le 500$

お久しぶりです。れたすです。

この度は、ブログをはてなブログから個人サイトのブログへと引っ越すことになりました。

個人ブログの中でも競技プログラミングに関連する解説記事やその他の記事はサイト内の「Competitive」から閲覧できるようになる予定です。

エスパーです。正直こっちのほうが分かりやすいです。

厳密ではありませんが証明はちゃんとつけました。

問題リンク

https://atcoder.jp/contests/arc129/tasks/arc129_d

問題概要

長さ $N$ の整数列 $(A_1, \dots, A_N)$ があります。この整数列の両端は繋がっています。

$A_{i-1}, A_i, A_{i+1}$ にそれぞれ $-1,2,-1$ を何回か足すことによって $A_i$ を全て $0$ にできるか判定し、できるなら最小回数を求めて下さい。

制約

• $3\le N\le 200000$
• $-100\le A_i \le 100$
• 入力は全て整数

おもしろかった。気付いたときうわーーーーって言いました。

問題リンク

https://codingcompetitions.withgoogle.com/codejam/round/0000000000877b42/0000000000afdf76

2023/07/16 追記

GCJ のサイトが閉じられたので、代替となるリンクを貼ります。

https://github.com/google/coding-competitions-archive/tree/main/codejam/2022/round_1c/squary

なお、GCJ の過去問のデータはこのリポジトリで参照できます。

問題概要

数列 ${E_i}$ に、$K$ 個以下の整数 ($-10^{18}$ 以上 $10^{18}$ 以下) を追加し、以下の等式が成り立つようにしてください。

• $\displaystyle \sum E_i^2=\left(\sum E_i \right)^2$

制約

• $1\le T\le 100$ (テストケース数)
• $1\le N\le 1000$ (数列の長さ)
• $-1000\le E_i\le 1000$

小課題

• 小課題 1 (9pts): $K=1$
• 小課題 2 (22pts): $2\le K \le 1000$

計算機プログラミングの授業では解説しなかったため没となったスライドを供養します。

本番では使用してないですがほぼ完成しています。あくまでスライドなので、普段の解説記事よりは簡潔かと思います。

お久しぶりです。

計算機プログラミングの授業でこの問題の解説をしたので、普段の解説記事とは違う形式ですがそのスライドを公開しようと思います (教員には許可を取っております)。

最近競技プログラミングを休んでいたのでかなりお久しぶりになっていました。ABC どころか Rated も出ていない……。

ゆっくりのんびり、余裕のある程度にまたやろうかなと思います。

なんか全然公式解説と違うことしてました……。

問題リンク

https://atcoder.jp/contests/arc046/tasks/arc046_d

問題概要

$H$ 行 $W$ 列からなるグリッドグラフがあります。

このグラフにおいて、$(i,j)$ から $((i+1) \bmod H, j)$ または $(i,(j+1) \bmod W)$ に移動できます。

マス $(0,0)$ からスタートして全てのマスを通り、$(0,0)$ に戻ってくるような経路の数を $\bmod 10^9+7$ で数え上げてください。

制約

$1\le H,W\le 10^6$