枝豆(@ek_bm)/2019年12月/Page 31

色が変わったんで記事待機だな！？

タグ：

posted at 23:36:44

ちがう、男色じゃない…

タグ：

posted at 23:36:04

TokusiN @toku51n

@semiexp 多項式時間で、が抜けています。倉庫番はSATでは不可能。

タグ：

posted at 23:35:18

@charmychachacha おめでとうございます！！！

タグ：

posted at 23:35:02

万能ではあるらしいが、効率でって意味でした。

タグ：

posted at 23:34:39

男色コーダーの仲間入り！嬉しいのです！ pic.twitter.com/Of7vuoSKyv

タグ：

posted at 23:34:30

連結性も SAT に帰着できるんだけど変数の個数が 2 乗になるなどがよく起きる

タグ：

posted at 23:33:59

SAT は NP 完全なので論理的に正解判定ができるパズルは基本的に SAT に帰着して解けるはず

タグ：

posted at 23:32:22

銀行コン40分全完で、ついに黄色になりました！初めて1900に乗ってから4ヶ月半。長かった…。

タグ：

posted at 23:32:16

zundamochi_1117さんの三井住友信託銀行プログラミングコンテスト2019での成績：76位
パフォーマンス：2400相当
レーティング：1947→2002 (+55) :)
Highestを更新し、初段になりました！
#AtCoder atcoder.jp/users/zundamoc...

タグ： AtCoder

posted at 23:31:46

でっち上げ大会、結局ルール投稿できずじまいだった
今から結果を見てみる

タグ：

posted at 23:29:05

まSATソルバーくんが万能というわけでもないか。他のプログラミングの方法の一般論を知らんので困ってるけど...全探索と枝刈りとかどうやるんだろうね。

タグ：

posted at 23:29:03

単一配置でお願いします。複数配置は形状記憶が闇。

タグ：

posted at 23:27:46

あと、領域分割系はマジでどうしようもなさそう。線を管理するんかな、でも領域の連結性とかあるし、どうしたもんかね。四角に切れのように、配置系とみなすのが精いっぱいかなぁ。シンプルブロックパズルとか解けたらいいのにね。

タグ：

posted at 23:27:09

SATソルバーくん、数字系以外だとマインスイーパーなど配置系にはかなり強そう。「置くか置くか」の二択で、局所的ヒントが与えられてるものは、自然に書けそう。

タグ：

posted at 23:25:05

お絵かきロジックが使えたりしないかなぁ

タグ：

posted at 23:23:23

一方、黒どこも似たような操作が必要だけど、こっちは黒マスを置いてから長さをカウントする必要がので、どうやって論理式に表せばいいのか全然わからなかった。

タグ：

posted at 23:21:16

まだ片面と超上級が残ってる

タグ：

posted at 23:20:35

ついに完成しました
総時間500分くらいでした

タグ：

posted at 23:20:21

そーいえば、美術館のSATソルバーを書こうってなったとき、行と列で自分から見える場所を調べて論理式にする必要があって、「あ、これ競プロで見たやつだ！」ってなった。

タグ：

posted at 23:20:02

Eは嘘つきがいる場合にも矛盾しないように考えて実装したな

タグ：

posted at 23:16:15

zundamochi_1117's replay of 三井住友信託銀行プログラミングコンテスト2019

最大瞬間風速は 76位 (40:24, sumitb2019_f AC) だよ！
atcoder-replay.kakira.dev
#AtCoder_Replay pic.twitter.com/NYK44YxIgB

タグ： AtCoder_Replay

posted at 23:03:21

今回は誤答の回数が相当順位にひびいているな…

タグ：

posted at 23:00:31

今日はにぶたんを意識するまでもなく全完できたのでよかった

タグ：

posted at 22:45:13

家庭内12完を達成した

タグ：

posted at 22:44:16

めるーめるん @melvy_puz

三井住友信託銀行2019 A-F #めるAC #める1日1AC
わーい全完だー．圧倒的算数ｗ四谷大塚で見たｗ

タグ：める1日1AC めるAC

posted at 22:43:47

C 個数決め打ち全探索
D 本質的にはこれが一番難しく感じた。各数字の累積個数を両側から持っておいて，中央の文字を全探索
E 左からかけ算
F 中学入試の算数っぽさ。1周期での差に注目して割り算

タグ：

posted at 22:43:00

TL見てると無限人全完してるな

タグ：

posted at 22:35:40

ノーペナrated10位確定

タグ：

posted at 21:44:02

全完致した

タグ：

posted at 21:43:22

もう1問作成

タグ：

posted at 21:42:04

パズルリーグの問題を1問作って満足してる

タグ：

posted at 21:22:58

非公開

タグ：

posted at xx:xx:xx

非公開

タグ：

posted at xx:xx:xx

非公開

タグ：

posted at xx:xx:xx

しかしにぶたん知ったのちょうど昨年の今頃だったな。懐かしい

タグ：

posted at 20:59:21

非公開

タグ：

posted at xx:xx:xx

銀行コンいくぞ！目指せ全完

タグ：

posted at 20:57:08

日本パズル連盟 WPC体験会8/26開催 @jppuzzles

ところで、HPLでサンプルの動画が送られてけど、序盤の図形を見て「オイオイ読まれたぞ」ってなってました

タグ：

posted at 20:55:35

日本パズル連盟 WPC体験会8/26開催 @jppuzzles

【 #日本パズル選手権 2019 懇親会パズル Q9】

今回の問題の制限時間は30秒です。解答は明日発表予定。 pic.twitter.com/2srXItpPS8

タグ：日本パズル選手権

posted at 20:54:09

【解答】

Q8の答えは「③4」。
できる熟語は「親密（しんみつ）」。

タグ：

posted at 20:52:07

迷ったらにぶたん！（素振り）迷ったらにぶたん！（素振り）

タグ：

posted at 20:51:43

@k_pan_opt Lighthousesに1票

タグ：

posted at 20:49:05

volxa @volxa

@k_pan_opt バッグに一票

タグ：

posted at 20:45:53

めるーめるん @melvy_puz

使用可能なプログラミング言語などないがってなるやつ（今日の）

タグ：

posted at 20:34:52

@QatSimorin @k_pan_opt 完全に見落としてた

タグ：

posted at 19:49:18

同じゲームなのに、カウボーイ、職人、技師それぞれに異なった奥深さがある。毎回自然と頭の違う部分を使っている感覚。ＧＷＴは本当に、リプレイ性の高い名作重ゲーだと思います！！

タグ：

posted at 19:42:10

ＧＷＴ楽しすぎ！！！

タグ：

posted at 19:37:40

非公開

タグ：

posted at xx:xx:xx

非公開

タグ：

posted at xx:xx:xx

非公開

タグ：

posted at xx:xx:xx

@pawakun ぬりかべ-連結-2x2禁
つまり、ヒント以外全部塗る

タグ：

posted at 18:49:44

非公開

タグ：

posted at xx:xx:xx

lakesのルールなんだっけ

タグ：

posted at 18:47:49

@k_pan_opt モチコロってシマの大きさじゃないの？ぬりかべ同様

タグ：

posted at 18:47:15

@k_pan_opt Lakes (定番度がわかんない)

タグ：

posted at 18:47:13

非公開

タグ：

posted at xx:xx:xx

@k_pan_opt モチコロ…？

タグ：

posted at 18:33:43

山本達也 @PuzzleYamamoto

そういえば、私とあの御方の頭の中はこんならしい。 pic.twitter.com/DxK9m4nNFQ

タグ：

posted at 18:29:32

非公開

タグ：

posted at xx:xx:xx

LG2セット4に行ってしまおうか

タグ：

posted at 17:56:24

稲葉直貴（パズル作家） @puzlab

ダブルポジションってどういうルールでしたっけ。

タグ：

posted at 16:33:27

今見るとこれ(遷移行列の自動生成)いける気がする。各状態の黒マスに、それが属する連結部分ごとに連結番号をつけておく。n+1行目を左から順に見て、黒マスの左上と右上が同じ連結番号なら不可、異なる連結番号なら左上の連結番号を受け継いで右上を書き換える。終わったら左から連結番号を振り直す。

タグ：

posted at 16:18:28

アイ @tigereye_werewe

【急募】解きチェック

どなたか！お願いします！！

タグ：

posted at 15:40:32

11020パターンが漏れてる、23パターンかな

タグ：

posted at 15:12:12

連結成分で見た方が分かりやすいか

タグ：

posted at 15:11:09

へやわけDPについては、
横5マスの黒マスと分断状態が下記の22パターンになり、
次の行として許される状態は、一つ上の行から決まる、
かな。 pic.twitter.com/LS1OZENnp7

タグ：

posted at 15:07:58

角を考えるとして、辺の影響は、最初の連結成分と、1の側の遷移が何本か消える、というもの。

タグ：

posted at 15:00:49

へやわけのDPでの分断禁の扱いが気になったけど、「同一連結成分のものが黒マスで引っ付かない」でいいのかな。ただ辺に注意しないとだめなのね。

タグ：

posted at 14:47:46

@wand_125 日本語誤読マンでした、すんませんね...Sugarのサイトで公開されてないんですかねぇ

タグ：

posted at 13:43:18

@SP1_winter (iSugarが)何かしらの（ソースが公開されるタイプの）コンテストに出ていたらそこからダウンロードできるかも
と思ったのですが、
学会系で論文やポスターを公開するタイプのコンテストだったのでなかったです。（上記URLがその論文かな）

www.sig-sldm.org/designcontest....

タグ：

posted at 13:38:34

早めに枠取っておいてよかったね。自分のは軽い前菜盛り合わせみたいなのなんで...

タグ：

posted at 13:37:24

なんかアドベントの記事が全部メインディッシュに見えてきた。コース料理なら胸焼けしそう。

タグ：

posted at 13:36:26

@chebunanntoka 現状だとやっぱりしまをつぶすことになりそうだけど、余裕値が線形に減ってるのがかなりヤバい。別の議論が使えるか、もはや人間の手には負えないのか。どうしたもんかねぇ...

タグ：

posted at 13:35:19

@wand_125 むえー、パズルの作問のためにSATコンテストに出るの、ハードルが高すぎる...まあしかし気になりますね。自分はまだそこまでの知識が足りてないですが。

タグ：

posted at 13:32:53

なんかこの辺のゲームは定理で周期性が保証されていたような、関係ないかもだけど

タグ：

posted at 13:30:56

残り95件のツイートを見る

@SP1_winter これのやつですね
www.jstage.jst.go.jp/article/jssst/...
解列挙や制約微調整（≒作問向き）に使えそうで気になってるのですが、
iSugarは公開されてなさそう。
コンテストに出てたらそこからダウンロードできるかも？

タグ：

posted at 13:30:05

@SP1_winter 後者だとは思う。構成の話が広がりを見せたんだけど、逆に上から押さえる手段が足りていない状態。

タグ：

posted at 13:29:40

Dawson's Kayles(って名前なの今知った)に通ずるものを感じる。fibonacci-freak.hatenablog.com/entry/2017/09/...

タグ：

posted at 13:29:34

@chebunanntoka 後者と予想してるけどどうなんだろう。周期16はたぶん縦5から来てるだろうけど、縦の長さを変えたらどうなるか、とかまだまだ興味は尽きない...

タグ：

posted at 13:26:21

しまつぶしの余裕値が減っているのが、「5x1000で法則が乱れる」になるのか、「壁の長さが余裕値を削ってる」になるのか、すら分からん

タグ：

posted at 13:24:05

DPによる探索なので、そのまま周期16の証明までできる可能性も高そう

タグ：

posted at 13:23:23

DP実装の話、唯一解の具体的構築、その応用、は書くつもりなのでまだたくさんある。最大性や唯一性も示せたら嬉しい

タグ：

posted at 13:22:18

Sugar+iSL、ここ数年前にできたんかい。一般人にも遊べるのかねこれ。

タグ：

posted at 13:21:40

いままでへやわけは強い人・調べてる人がわりとたくさんいて、その人たちに聞けばいいかって敬遠してたけど、そろそろ真面目に考察せんとな...

タグ：

posted at 13:19:51

さすがにDP使ってそうだけどね、逆算もできるだろうし。縦5なら結構長くまで解けそうだし。

タグ：

posted at 13:18:39

29 in 5*16edgeをええ感じで付け加える方法が見つかったってことなんかね、すさまじい執念...

タグ：

posted at 13:17:20

サイズが16増えるごとにしまつぶしの余裕値が1減ってるのが気になるな。減るにしても不思議な減り方な気がする。

タグ：

posted at 13:15:07

2003年にへやわけMXの概念が生まれて、
2019年の今、角の5 x nのMXの周期が16である予想が立ってるの面白いなー、
歴史が動いてる（？）

タグ：

posted at 13:13:47

アドベント先取りさせててすまんなぁという気持ちになってる

タグ：

posted at 13:13:39

MX(5,n)を実現する配置がところどころ唯一解になるのウケるなぁ、ほんまかいな

タグ：

posted at 12:59:55

てかもっと一般に「グラフの独立集合であって、それらを取り除いたとき連結になるもののうち、大きさ最大のもの」と考えれば、十分学術的な価値がありそう。

タグ：

posted at 12:56:22

1~113,129,234,257について取り急ぎ nishiwake.e-contents.biz/kado-p2 に載せました

タグ：

posted at 12:52:50

トケタ7を入手した(スタッフ配分)

タグ：

posted at 12:52:21

LG2のセット3、早くも解くのが難しくなってきた

タグ：

posted at 12:42:21

角のnx5のMX値の周期は16(n<114のとき)。例として17から33までのMX値と解の総数を示す。
17 32 1
18 33 833
19 35 394
20 37 24
21 39 19
22 40 14185
23 42 5728
24 44 627
25 46 331
26 48 1
27 50 6
28 51 13233
29 53 5376
30 55 232
31 57 166
32 58 249585
33 61 1

タグ：

posted at 12:41:11

5×8は違うな…

タグ：

posted at 12:34:28

@SP1_winter mn+m+nが3の倍数になると若干余裕生まれない？って昨日考えてた

タグ：

posted at 12:33:38

5×100までやっても「5×1000までやったら法則が乱れてぐちゃっとした解が発生したりしないかな」という気持ちになってしまう

タグ：

posted at 12:22:18

「外周があるとだいたいサイズ4減」を信じるなら、5*8とか7*10は十分例外の範疇とも言える...実際30 in 8*11allは厳しそうだし。

タグ：

posted at 12:18:21

やな予感がしたため一応投げておく。24 in 7*10all. pic.twitter.com/jkE69EmoRF

タグ：

posted at 12:12:36

へやわけMX値を一般のサイズで上から抑えるのかなり厳しくて、壁があると今のところ「もしn+1個入るならn個の解がもっとあるはずだ」みたいに全探索するしかない

タグ：

posted at 12:09:17

これ、もしかして打ち上げ花火と似たような例外の可能性ある？

タグ：

posted at 12:08:59

信頼性怪しい気がせんでもない

タグ：

posted at 11:59:10

@wand_125 このハニカム3つ目って、4つの白確定のうち一番下は白確定しないのではないでしょうか pic.twitter.com/8iQluVGsIP

タグ：

posted at 11:57:59

非公開

タグ：

posted at xx:xx:xx

OEISにへやわけの充填数を投稿した人のサイトを見つけた
www.elliottline.com/other-projects...

タグ：

posted at 11:56:25

たとえばMX(3,6)=8なのでMX(3,6)+7+10-2=23だが、7*10には24個は置ける。

タグ：

posted at 11:56:15

てかOEISに載ってるなら、ちゃんと探せば論文見つかりそう...

タグ：

posted at 11:52:28

実際m*nの場合だと微妙に多く置けるかも。

タグ：

posted at 11:51:51

ハニカムスターバトルについてまとめました。
scrapbox.io/wandsbox/%E3%8...

タグ：

posted at 11:51:45

n*nのときMX(n-4, n-4)+2n-2以上になるのは、外周に黒マス置いてから中空のパターンをつかえばよいのでわかる(n偶数でも大丈夫)。それより多く置けるかはわからんですが...

タグ：

posted at 11:49:03

載ってんのかーい

タグ：

posted at 11:44:20

utime @utime1204

・答えの値を決め打ちして探索
・隅から埋める場合、真に上位互換の配置があれば除外
とか有効かもしれないが、多分無効。知らんけど。

タグ：

posted at 11:43:00

下からの評価も、定数ならもう少し複雑な構成になるかも

タグ：

posted at 11:41:19

M*3-m*nが定数なのかもよくわかってないし。外周の影響が減ったらもうちょっと詰めれたわ、みたいなのがまだ否定できてない。

タグ：

posted at 11:40:01

ニチョ謎 @nichonazo

本日12時から #なげっぱやりますよー！
先週のお休みを知らずに訪れてしまった方、申し訳ありませんでした。

ウェル問20-2「かんたんだったもの」

一週間寝かせたから難しくなったわけではありません。難しいわけでもありませんよ！

それでは、もうすぐ12時からオープンです。

タグ：なげっぱ

posted at 11:39:23

それは置いといて、オーダーはいいので、細かい定数が気になってます。人間が意味を見いだせるかは不明ですが...

タグ：

posted at 11:37:06

非公開

タグ：

posted at xx:xx:xx

もっとかんたんな構成あったわ...

タグ：

posted at 11:35:54

@SP1_winter @southerwolfie x+y mod3 が 0 のところに黒マスを置く(x か y のときは置かない)

タグ：

posted at 11:34:33

わからんので、機械さんに代わりに殴ってもらおうという魂胆です

タグ：

posted at 11:33:12

これは「しまつぶしの原理」で示せるそうな(詳しくはへやわけMXのアーカイブ見て)。残念なことに、辺がある場合への応用は知られていない。精密化できるかもだけどね。

タグ：

posted at 11:31:52

もっと詰められるかについてはおそらくNOで、というのも中空ケース(辺なし)だいたい(m+1)(n+1)/3個であることが知られています。

タグ：

posted at 11:30:16

m,nが小さいと外周の影響が大きすぎてぶれるので除外で。m,n>3 だとよさそう。

タグ：

posted at 11:28:40

1/3詰めるのは、たとえば(odd,odd)置く→退化した盤面で(odd,odd)置く→ を繰り返せば、だいたい1/4+1/64+...=1/3は置ける(若干ロスがあるのでざっくりだけど)。

タグ：

posted at 11:27:12

mかnが1の時って個数は2だよね…

タグ：

posted at 11:24:46

非公開

タグ：

posted at xx:xx:xx

@southerwolfie たぶん...(頑張れば構成できそう)

タグ：

posted at 11:22:35

今走らせてる愚直なSATソルバーくんだと、マス目が60くらいで探索が困難になってる。

タグ：

posted at 11:22:02

非公開

タグ：

posted at xx:xx:xx

【問題】m*nのマス目のいくつかのマスを黒く塗る。ただし、黒マス同士はタテヨコに隣接せず、白マスはひとつながりになるとする。このとき、黒マスの個数最大Mを求めよ。またS=M*3-m*nを考察せよ。

タグ：

posted at 11:20:20

青まで対象の前回の企業コン見てるけど、最後の木の問題何もわからないな。何らかのdpをするのだろうという木にしかならない

タグ：

posted at 11:20:16

ちゃんと書くか

タグ：

posted at 11:17:44

@pawakun S=(max)*3-m*n として、S=2の例が(7,7)や(5,8)なので、ひとまとめにしちゃった

タグ：

posted at 11:17:13

一部屋だけのへやわけって何ていうの？latinへやわけ？

タグ：

posted at 11:16:36

リストあったら欲しい。なんとなくm,n<=20ぐらいで見てみたい。

タグ：

posted at 11:13:24

3×3と7×7は例外中の例外では(感覚)

タグ：

posted at 11:13:00

連結成分を正規化した Union Find で持って状態全部 map に突っ込めばそんなに大変じゃない気がする

タグ：

posted at 11:12:14

読む
www.jstage.jst.go.jp/article/jssst/...

タグ：

posted at 11:12:09

m*n盤面に分断なしで入る黒マスは「だいたい」(m*n)/3個だけど、たまに効率のよさげな入れ方がある。(3,3)はちょっと例外っぽいけど、とか(7,7)とか(5,8)がそれです。

タグ：

posted at 11:11:47

しまつぶしっぽい評価ができそうなんだけども、具体的にはよくわからん。

タグ：

posted at 11:09:19

これだっけ。まあできそう(外周がややだるい？)だけど、やっぱだるそう。

タグ：

posted at 11:08:23

n×n の盤面に入る黒マスの個数ってどれくらい調べられてるんだろ

タグ：

posted at 11:08:15

へやわけだったら面倒なことで有名な DP したほうが(実行速度は)速いかも

タグ：

posted at 11:02:37

ただの上級手筋のオンパレードです()

タグ：

posted at 10:51:16

今度のパズルリーグはたまたま選手として出れることになったけど一体どれだけ勝てるんだろうかと思いながらインストを見ている

タグ：

posted at 10:38:14

もう少し濃いシャー芯買うかー

タグ：

posted at 10:24:28

うまいこといじって34個入りそうな見た目をしてるけど、だめそう

タグ：

posted at 10:12:20

33 in 10*10all pic.twitter.com/S3tDHZPJGa

タグ：

posted at 10:06:58

僕が堪え性がなく1分くらいで探索打ち切ってるから説あるし、もうちょっと見守るかね

タグ：

posted at 10:04:18

うんやっぱ8*8やね。7*7で18個はいけたので、8*8で22個がどうか。

タグ：

posted at 10:03:30

まあまともに探索したら最低O(2^mn)で到底ダメなわけで、それを高速で解を拾ってこれるSATソルバくん凄まじいわけだけども、どれくらい高速なのかが定量的にはわかんねぇ

タグ：

posted at 09:58:18

四隅辺の10*10に黒マスは33個置けるけど、それはなかなか判定してくれない。34個置けるかどうかも判定しんどそう。

タグ：

posted at 09:41:52

さすがに言い過ぎかね。探索空間に対し解の個数がめちゃくちゃ少なかったら、普通にめっちゃ時間かかるっぽい。

タグ：

posted at 09:40:20

上限を求める感じだったら、悩みまくってたら無いと解釈していいのかね。さすがにそれは暴論？

タグ：

posted at 09:33:20

SATソルバーくんの速度がイマイチわからん。一つの解を拾ってくるのは相当早いけど、解がないときに延々悩み続けてる。悩み続ける時がおそらく計算量maxで、その時の大体の速度が変数の個数とか式の個数とか範囲の大きさで評価できればいいんだけど...(まあもちろん式によるといえばそこまでだけどね)

タグ：

posted at 09:32:11

作戦は例のpdfの通り、別の変数を用意して木にして確かめるとしてやった。変数3倍しかも一つは範囲が広すぎる感じになっちゃったから遅くなったんかね。

タグ：

posted at 09:29:10

へやをわけてないへやわけのSATソルバーを書いて、7*7に黒マスが17個まで置けることを確認したが、8*8に置ける個数の確認にすごく時間がかかってる。

タグ：

posted at 09:27:29

アドベント初日から面白くてハードルが高い

タグ：

posted at 09:15:15

山崎さんに製材所プレイをぶつけようものなら、死が待っている・・気しかしないｗｗｗ

タグ：

posted at 08:35:42

ＧＷＴも５０戦くらいやってるとそろそろトリックプレイやりたくなるんだけど、皆さんが強すぎてなかなかそれを許してもらえないｗ

タグ：

posted at 08:34:48

今日は関西から友人が来て、一日中ＧＷＴができるという超幸せな日！
最近やってなくて腕は鈍ってるだろうけど、全力で楽しみたい！！

タグ：

posted at 08:29:11

volxa @volxa

戯れにいつもと違うルートにそれてみたら、中々いつものルートに戻れず、30分強余分に歩く羽目に。疲れた。

タグ：

posted at 07:14:24

非公開

タグ：

posted at xx:xx:xx

非公開

タグ：

posted at xx:xx:xx

白岡市民(295) @Whitehill9

SVS(041)のThermometerはいいぞ #vsSVS

タグ： vsSVS

posted at 00:28:21

Tridってロシア発だしロシア語由来だったりしないかな。どうせTriangular Gridの略だろうけど

タグ：

posted at 00:27:11

HPLセットの中では唯一Tridを解いたことがない。理由はわかりやすくて、ラテン苦手変型盤面苦手なのでコンテストで出たら間違いなく触れないからである。

タグ：

posted at 00:25:58

1週間後は自分の番だ

タグ：

posted at 00:05:07