Growth Record of Lettuce Farm

競プロの記録・解説をします

【ご報告】ブログを順次引っ越します

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

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

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

fairy-lettuce.github.io

続きを読む

AtCoder Regular Contest 129 D - -1+2-1 解説 (エスパー→証明)

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

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

問題リンク

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
  • 入力は全て整数
続きを読む

Google Code Jam Round 1C 2022 B - Squary 解説

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

問題リンク

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
続きを読む

AtCoder Beginner Contest 091 C / AtCoder Regular Contest 092 A - 2D Plane 2D Points 解説スライド

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

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

drive.google.com

AtCoder Grand Contest 029 B - Powers of two 解説スライド

お久しぶりです。

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

drive.google.com

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

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

AtCoder Regular Contest 046 D - うさぎとマス目 解説

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

問題リンク

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

問題概要

HW 列からなるグリッドグラフがあります。

このグラフにおいて、(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

続きを読む

Educational Codeforces Round 91 E - Merging Towers 解説

解説記事や Editorial などをざっくり見ても自分の解法の解説が無かったので。

問題リンク

https://codeforces.com/contest/1380/problem/E

問題概要

n 個の皿が m 個のタワーに置かれています。皿は直径がそれぞれ 1,2,\dots,n であり、直径が i である皿はタワー t_i に置かれています。また、各タワーには上から直径が小さい順に皿が置かれています。

あなたは m 個のタワーのうち 1 つに全ての皿が乗っているようにしたいです。タワーは以下の操作を何回か行うことでまとめます。

  • 好きな i,j\ (1\le i,j\le m,\ i\ne j) を選ぶ。タワー i から上から何個か (全部でも良い) の皿を取り、同じ順番でタワー j の上に置く。このとき、動かす皿は全て操作前のタワー j の一番上の皿よりも小さくてはならない。

タワーを 1 つにまとめるのに必要な操作回数の最小値を、タワーをまとめる難易度と呼ぶことにします。

さて、m-1 個のクエリ a_i,b_i が与えられます。i 個目のクエリはタワー b_i の皿を全てタワー a_i の皿とまとめ、新たなタワー a_i にすることを意味します。新たなタワーも皿は上から小さい順になるようにします。これは難易度には関係しません。

全ての k=0,1,2,\dots,m-1 について、k 番目のクエリまでを処理した状態でのタワーをまとめる難易度を求めてください。

制約

  • 2\le m\le n\le 2\times 10^5
  • 1\le t_i\le m
  • 1,2,\dots,m までの整数がそれぞれ少なくとも 1 回以上 t_i に現れる。
  • 1\le a_i,b_i\le m,\ a_i\ne b_i
  • クエリ a_i,b_i はどちらのタワーもそのクエリの時点で存在するようなものが与えられる。
続きを読む