Growth Record of Lettuce Farm

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

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

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

問題リンク

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

問題概要

数列 {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 はどちらのタワーもそのクエリの時点で存在するようなものが与えられる。
続きを読む

ZONeエナジー プログラミングコンテスト “HELLO SPACE” F - 出会いと別れ / Encounter and Farewell 解説

問題リンク

https://atcoder.jp/contests/zone2021/tasks/zone2021_f

問題概要

N=2^n 個の頂点 0,1,2,\dots,N-1 について、N-1 個の辺 (i,j) を張って全域木を構成したいです。ただし、(i,j) について、i\oplus jA_1,A_2,\dots,A_M のいずれかと一致するような辺 (i,j) は張れません。

全域木が構成できるか判定し、出来る場合は構成の仕方を 1 つ示してください。

制約

  • N=2^n として、1\le n\le 18
  • 0\le M\le N-1
  • 0\lt A_1\lt A_2\lt\dots\lt A_M\lt N
続きを読む

Contest 2050 and Codeforces Round #718 (Div. 1 + Div. 2) D - Exploror Space 解説

謎制約。

問題リンク

https://codeforces.com/contest/1517/problem/D

問題概要

n\times m のグリッドグラフが与えられます。4 近傍で繋がっている各辺には道の長さが与えられています。

全ての (i,j) について、k 回移動を繰り返して最初の位置 (i,j) に戻ってくるとき、移動経路の距離の最小値を答えてください。戻ってこれなければ -1 としてください。

制約

  • 2\le n,m\le 500
  • 1\le k\le 20
  • 1\le (各辺の長さ)\le 10^6
続きを読む