Growth Record of Lettuce Farm

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

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

競プロ解説 AtCoder

問題リンク

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 j が A_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 解説

競プロ解説 Codeforces

謎制約。

問題リンク

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

AtCoder Beginner Contest 198 E - Unique Color 解説

競プロ解説 AtCoder

最近似た問題を見ていたのでその解説を見て難しい解法にハマりました。

Editorial と同じ解法と、自分の解法を両方紹介します。

問題リンク

https://atcoder.jp/contests/abc198/tasks/abc198_e

問題概要

N 頂点の木が与えられます。頂点 i は色 C_i で塗られています。

頂点 1 から x への最短パスに色 C_x が頂点 x 以外に現れないような頂点を良い頂点と呼びます。良い頂点を列挙してください。

制約

  • 2\le N\le 10^5
  • 1\le C_i\le 10^5
  • 与えられるグラフは木
続きを読む

AtCoder Beginner Contest 198 D - Send More Money 解説

競プロ解説 AtCoder

久々に ABC でやったらいけないミスした……。

問題リンク

https://atcoder.jp/contests/abc198/tasks/abc198_d

問題概要

覆面算 S_1+S_2=S_3 を解いてください。

制約

  • 1\le |S_i|\le 10
  • S_i は英小文字のみからなる。
続きを読む

AtCoder 黄色になりました

色変記事 AtCoder

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

今回はこの通り、AtCoder 黄色になったので、そのご報告とか色々をいたします。

  • 前回 (AtCoder 青色・その他) の色変記事
  • 色変報告
  • AtCoder 黄色になるまでにやったこと
    • 精進記録
    • 身につけたアルゴリズム・データ構造
      • 何の迷いもなく書ける・使えるようになった
      • 調べたら使える・ちょっと苦労するけど書ける程度
      • あまり理解していない
  • 青のときから変わったこと
  • おわりに
続きを読む

AtCoder Regular Contest 114 C - Sequence Scores 解説

競プロ解説 AtCoder

解説記事を書くのはかなりお久しぶりになってしまいました。

問題リンク

https://atcoder.jp/contests/arc114/tasks/arc114_c

問題概要

1 以上 M 以下の整数からなる長さ N の数列 A に対して、f(A) を以下のように定義します。

  • 長さ N の数列 X があり、初め全ての要素は 0 である。f(A) を、次の操作を繰り返して X を A に等しくするために必要な最小の操作回数とする。

    • 1\le l\le r\le N と 1\le v\le M を指定する。1\le i\le r に対して X_i を \max(X_i,\ v) で置き換える。

全ての A に対する f(A) の和を \bmod 998244353 で求めてください。

制約

  • 1\le N,\ M\le 5000
続きを読む

AtCoder Beginner Contest 190 D - Staircase Sequences 解説

競プロ解説 AtCoder

ABC 反省文シリーズ。

問題リンク

https://atcoder.jp/contests/abc190/tasks/abc190_d

問題概要

整数からなる公差 1 の等差数列のうち、総和が N であるものはいくつあるでしょうか？

制約

  • 1\le N \le 10^{12}
続きを読む