Google Code Jam Qual 2020 (excerpt)

laycrs @laycrs

Google Code Jam Qualification Round 2020． 1問目，頑張ってループを書いて数える． 2問目，足りない(か)を逐次補っていく． 3問目，開始時間でソートして順番に暇人に割り当てる．

laycrs @laycrs

4問目，ジャッジがY，Nを返すのを受け取り忘れてWAもらった．両端から1文字ずつ確定させていって，10文字おきに，反転した4種の文字列作ってどこか2個聞けばどれになってるかわかるという場所を全探索して，それを聞いて何が起こったか確定．8*15文字までこれで行けるはず．

laycrs @laycrs

5問目，対角が1つだけ違って他が全部同じ，ってパターン以外は作れそうな気がしたけどやってない．

Yak! @yak_ex

#GCJ #CodeJam やっぱりTLEで落ちたか……

nico_shindannin（診断人） @nico_shindannin

TopCoderでプログラムしてみた 第2447回 （Google Code Jam 2020 予選ラウンド 直後放送） youtube.com/watch?v=cXnPK_… @YouTubeさんから

拡大

tsutaj @tsutaj

うわ、GCJ の E が TLE してた・・・ ABCDe で 75 点

koyumeishi @koyumeishi_

GCJ の E 普通にわからなくて焼きなましたんだけど……

nico_shindannin（診断人） @nico_shindannin

今日のGoogle Code Jam Round 2020 予選ラウンドはどうでしたか？ （放送URL youtube.com/user/shindanni…）

Yak! @yak_ex

@nico_shindannin @YouTube 非公開で見られないです……

koyumeishi @koyumeishi_

GCJ E、ググったら出てきた Jacobson and Matthew's の Latin Square 生成アルゴリズムを少し弄って trace の値を K に近づけるように指向性を持たせて |trace - K| が悪化する場合は確率でスキップする簡易焼き鈍し。 解があれば割とすぐ見つかる

maspy @maspy_stars

GCJ-E：実装していないです。 対角線に使う数値だけ適当に埋めると、残った場所については、正則二部グラフを辺彩色する問題に帰着される。 正則二部グラフには完全マッチングが存在するので、埋まるやつは埋めてしまってからでも必ずつじつまが合う。フロー1,2回流せば解けそう。

laycrs @laycrs

師匠の放送が非公開で見れない…

nico_shindannin（診断人） @nico_shindannin

@yak_ex @YouTube ありがとうございます…。ちょっと配信遅延にもなっているっぽく設定を確認してみます…

nico_shindannin（診断人） @nico_shindannin

すいません、配信が見れなくなっていったので、お待ちください

maspy @maspy_stars

二部グラフの辺彩色は、彩色数 \Delta(G) でできて（Konigの定理、参考資料：slideshare.net/catupper/ss-25…）マッチングをひとつずつ取っていくより高速に解けるはず。（AGC037-Dとかも使える） いま検索していたら、M\log Mのものはありそう。yosupo judgeに入れてもいいかも。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

GCJのE： 対角に同じ数がちょうどn-1個来るとダメ（それ以外ならできる） ダメなケースはk=n+1/n*n-1とn=3,k=5/7だけ。 それ以外は適当に均等に配って、1222みたいな場合は1123みたいにずらす。 あとは図みたいに埋めて、残りの数を完全マッチングを求めて埋めることを繰り返す（詰むことはない） pic.twitter.com/gtFBD1hvoj

拡大

koyumeishi @koyumeishi_

D は対称な位置のペアを考えてやると B + B/2/5 * 2 + 2 回とかそんな感じ

nico_shindannin（診断人） @nico_shindannin

すいません、放送に入れるようになったはずです。 / TopCoderでプログラムしてみた 第2447回 （Google Code Jam 2020 予選ラウンド 直後放送） youtube.com/watch?v=zcQllx… @YouTubeさんから

拡大

Yak! @yak_ex

予選通すだけなら簡単だけど完答できなかったものを「簡単」と言っていいものか。

koyumeishi @koyumeishi_

E やりながら qual は毎年変わった問題あるけど今年はマラソン系か～、 hashcode も参加者増えて盛り上がってるし時代はマラソン人材だな～、とか思ってた

kuuso @kuuso1

GCJqual，全完287thだった．ウェイ．

Fumiya Suto @pes_magic

GCJ Qual、信じて送り出した嘘解法が通って満点だった。Eは対角成分を適当に埋めてあとは行ごとに2部マッチングで埋めていく…と当然詰むことがあるので、詰んだら対角成分をランダムシャッフルしてリトライを繰り返したら通った。真の解法は知らない。

koyumeishi @koyumeishi_

E の K = N+1, N^2-1 は本当に解なしなのかとビビってたんだけど、今思えば対角成分が A,...,A, B みたいなやつは B の行,列に A が必要だけど対角成分にあって不可能だから当たり前だった

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

二部グラフ辺彩色O(MlogM)これかな en.wikipedia.org/wiki/Edge_colo… 1. 魔法で正則にする 2. 次数が奇数なら完全マッチングを見つけて塗る（魔法を使うとほぼ線形らしい） 3. オイラー路を取って交互に振り分けて再帰的にやる かな？

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

詰まないことはHallの結婚定理を使うと示せる（いつもの）