Google Code Jam Qual 2020 (excerpt)

tatyam @tatyam_prime

縦と横に重複がないように置く→2部マッチング(典型) じゃん

nico_shindannin（診断人） @nico_shindannin

GCJのE、列ごとに決めていっても、最後まで、Hallの結婚定理が成り立ち続ける理由が、たぶん分かった気がするのじゃ。 N*Nの行列で、１列決めるごとに、数字・位置の二部グラフの、全頂点の次数がNから１ずつ減っていく（偏って減ることがない）のが、鍵な気がする。

nico_shindannin（診断人） @nico_shindannin

というか、AGC037 D Sorting a Gridのpdfで、そのまま言ってるのじゃ。当時は、たぶん理解してなかった！ pic.twitter.com/QVepbgCfhz

拡大

kuuso @kuuso1

GCJqualの中ではDがgcjっぽくて良かった．

nico_shindannin（診断人） @nico_shindannin

理解するも何も、焼きなましで通して満足していたからじゃった…。反省…。

tatyam @tatyam_prime

GCJ Qual E - Indicium を O(N^2) で解く hackmd.io/@tatyam-prime/…

koyumeishi @koyumeishi_

latin square 関連の pdf とか見てたときに latin rectangle の拡張はホールの結婚定理でマッチングがどうのこうので可能って確かに書いてあったんだけど、対角成分埋まってるし関係ないかなーってスルーしてた

koyumeishi @koyumeishi_

というか対角成分の埋め方も分割数的な数だけパターン存在しててどうしよう……みたいな感じだった。 種類限定するって発想がなかったの失敗だったなぁ

tatyam @tatyam_prime

GCJ-D です pic.twitter.com/mg1x4vg1we

拡大

Fumiya Suto @pes_magic

QualのEは数字2～3種類だけ良い感じに並べて、それから数字単位で配置するようにマッチングを繰り返せば確かに詰まないな。なぜ列単位で決めようと思ってしまったのか…。

tatyam @tatyam_prime

インタラクティブ問題のコツ ・入出力は関数に切り分ける

nico_shindannin（診断人） @nico_shindannin

やっぱり理解してないのじゃ…。 初期の行・列の空きが一緒だったらいいのかなと思いきや、以下の反例ががありました。 何か抜けてるところがありますでしょうか？ pic.twitter.com/JFflSaKbh1

拡大

maspy @maspy_stars

@nico_shindannin 行ごと（頂点をひとつずつ順に）ではなく、「完全マッチングを１つずつ引いていけばよい」です。この問題の場合には、 「３の位置を決める」→「４の位置を決める」→・・・ ですね。

nico_shindannin（診断人） @nico_shindannin

@maspy_stars ヒントありがとうございます！まだ考えているところです

nico_shindannin（診断人） @nico_shindannin

@maspy_stars maspyさんの方法は、空いているマスのx座標とy座標を二部グラフにしてマッチングする方法ですよね。それで、無事通りました。ありがとうございます！ ただ、そうなると、公式解説にあった、場所と数値で列ごとにマッチングする方法は何を指していたのかが分からなくなってしまいました…。 pic.twitter.com/mrmYmNplwg

拡大

maspy @maspy_stars

@nico_shindannin その通りで、行と列を頂点、マス目が辺と思います。 すいません、公式解説は読んでいないです。

nico_shindannin（診断人） @nico_shindannin

GCJ 公式解説のEの方法、運よく解けるときもありそうだけど（自分の場合もほとんどは通る）、なんか違うような気もしてきたのじゃ。

Fumiya Suto @pes_magic

@nico_shindannin 私も本番同じこと試したんですが、使える行が列によって違うので結果的に偏る事がありダメそうな気がしてます(なお手詰まりになったら対角成分をランダムシャッフルしてリトライという乱択で通しました)。

nico_shindannin（診断人） @nico_shindannin

@pes_magic なるほど。ほとんどは確かに通るんですよね。やっぱり行ごとに決めると言ってる公式解説は？な気がしてきました…。

nico_shindannin（診断人） @nico_shindannin

配信OKなコンテストしたいけど、ガマンするのじゃ…。

nico_shindannin（診断人） @nico_shindannin

でも、配信するプログラマーって、昔はすごく少なかったのに、今は普通にぽんぽんされているので、時代も変わったものじゃのう…（遠い目）

nico_shindannin（診断人） @nico_shindannin

おはようじゃ。昨日Google Code Jamが気になりすぎて、予想以上に時間を使ってしまったのじゃ… 仕事＆競プロの両立も難しいのじゃが、競プロ（アルゴ）＆競プロ（マラソン）の両立も難しいのじゃ。

nico_shindannin（診断人） @nico_shindannin

えらそうに言ってるけど、できてない。 ↓ 「競プロ（アルゴ）＆競プロ（マラソン）の両立」

nico_shindannin（診断人） @nico_shindannin

TLの一般の方々に比べると、わしはだいぶ時間に余裕がある環境なので、甘えはダメじゃ！びしっ！びしっ！