- @neetsdkasu #@usakdsteen
ぷいにゅー
- @neetsdkasu #
このツイートにあるリプとかも色々眺めてみたけど、社会人はこうあるべき論がたくさんあって社会って辛そう
twitter.com/ai_oosawa/stat…
- @neetsdkasu #
俺のスマホだめっぽ
バッテリ切れでもないのに死んでやがった
すこし充電したら電源入ったけどほんとダメだはこの機種 - @neetsdkasu #
そういやBIG買いそびれた
- @neetsdkasu #
まぁいいか
ロジサマ続きやっべ - @neetsdkasu #@neetsdkasu
これ
- @neetsdkasu #@neetsdkasu
ランダム選択のとこ最適化で自PC試行577回(スコア1031点)、パイザIOでは試行3030回(スコア1137点)と大幅改善という…
gitlab.com/neetsdkasu/Pai… - @neetsdkasu #@neetsdkasu
次は前のに戻ってコピーのみの最適化をお試す
- @neetsdkasu #@neetsdkasu
まさか改善なしだた、自PC試行126回(スコア973点)、パイザIO試行666回(スコア1031点)…たぶんこれコンパイラが最適化とかしててアロケ発生してなかったとかくさい…
gitlab.com/neetsdkasu/Pai… - @neetsdkasu #@neetsdkasu
結局ランダムセレクトだけアロケが発生して速度殺してたとかか
- @neetsdkasu #@neetsdkasu
ひとまず大幅改善したほうをサブミッするか
- @neetsdkasu #
やった!S級魔力プログラムのコード詠唱成功!「JSの羽」をゲット!! paiza.jp/logic_summoner… #コード詠唱
スコア少しアップ(+50)して880点になったぞやったあ… - @neetsdkasu #@neetsdkasu
ただランダムに選ぶだけの限界というやつ…
- @neetsdkasu #@neetsdkasu
gitlab.com/neetsdkasu/Pai…
よく見たらバグがあった・・・テスト不十分だコラ - @neetsdkasu #@neetsdkasu
提出したのがこのバグで死ななかったってことは、このランダムアプローチは全消し一つも無かったということか…
gitlab.com/neetsdkasu/Pai… - @neetsdkasu #@neetsdkasu
さて、今回の最適化で2秒弱だと3000回は試行できるということが分かった…3秒弱なら大雑把に4500回は試行できるはずだが、ビーム探索するにはたぶん十分ぽそうな回数なんかな…?
- @neetsdkasu #@neetsdkasu
上方のブロックは下方のブロックが消えることによってまとまるパターンと、下方が消える前のほうがまとまってるパターンとありそう
- @neetsdkasu #@neetsdkasu
うーん
- @neetsdkasu #@neetsdkasu
一度全探索するコードを書いてどれくらいのサイズまでだったら解けるのか試してみるか…
- @neetsdkasu #@neetsdkasu
コピーコストは無視できるものとして考えるとして、どのように全探索すべきか・・・
- @neetsdkasu #@neetsdkasu
単純に全ブロックごとに探索するとおっそろしいくらいの回数になってしまうから、それはアカン
- @neetsdkasu #@neetsdkasu
そういやブロック消す処理のもアロケコストかかってそうだけどどうなんだろ?
そっち先に試すか・・・ - @neetsdkasu #@neetsdkasu
全く意味なかった、自PC試行123回(スコア973点)、パイザIO試行663回(スコア1031点)、もしかするとこの程度のアロケはどうってことないのか…?
gitlab.com/neetsdkasu/Pai… - @neetsdkasu #@neetsdkasu
intのサイズ分からんけど仮に4byteだとして2500個なら10KB、小さいといえば小さいか…
- @neetsdkasu #@neetsdkasu
アロケとコピーではアロケのほうがコストたぶん高い、OSがメモリマネジメンしてて空きを探して確保?一塊ならコピーは専用処理とかありそうで速そうな雰囲気ある
- @neetsdkasu #@neetsdkasu
10KBが大きいメモリって感覚は、あれか昭和の感覚か
- @neetsdkasu #@neetsdkasu
セクタとかブロックとかそういう単位のサイズってもっと大きいんだっけか
- @neetsdkasu #@neetsdkasu
ひとまずは2500個程度のアロケコピーコストなんて気にする段階ではないって感じかな
- @neetsdkasu #@neetsdkasu
そんなことより全探索の方法を考えねばネバー
- @neetsdkasu #@neetsdkasu
アロケコピーコストは無視できても全ブロック選択では探索時間かかりすぎる
- @neetsdkasu #@neetsdkasu
ラベリング処理など施してから塊単位で選択するという方法も最悪ケースでは結局は全ブロック選択と同じになるからそれもダメ
- @neetsdkasu #@neetsdkasu
仮に3色じゃなくブロック全部が違う色だった場合、全ブロック数をMとするならM*(M-1)*(M-2)*... (M-min(N,M)+1)という感じか?となると全探索可能なサイズはどんくらいだろか
- @neetsdkasu #@neetsdkasu
ああ、まぁプログラムで計算すりゃいいのかMは1~2500、Nは1~100で表計算ソフトにぶっこむでも計算できそだけど…
- @neetsdkasu #@neetsdkasu
どうみても桁やばそうだな
- @neetsdkasu #@neetsdkasu
nが小さいケースは全探索が可能ではありそう(でもそのテストケース無さそう)
M=100くらいでランダムのが試行8万回くらい行くけどM=8の全探索で24万になってしまうので、全探索は非現時的 - @neetsdkasu #@neetsdkasu
メモ化や枝刈りというのが容易そうならいいんだけど、俺の頭ではちょっと思い浮かばない・・・
- @neetsdkasu #@neetsdkasu
計算ミスったM=8は4万だった、まぁM=9で36万だからどのみち非現実的
- @neetsdkasu #@neetsdkasu
880点超えるのは厳しそうだぞ…うう
- @neetsdkasu #@neetsdkasu
ランダムで消してこの点数にしかならないのに上位は全消ししてるぽいスコア出してるってことは、初期ブロック配置はランダムではなくあえて意地悪に意図的配置とかしてる可能性が?
- @neetsdkasu #@neetsdkasu
RGBR
GBRG
BRGB
みたいな配置をしてるとかなんかな? - @neetsdkasu #@neetsdkasu
今回テストケースを調べ上げるには、1呪文1ブロック消しだとスコア上がらないけど、1呪文2ブロック消しならスコアが1個あがる、全部のケースでちょうど2ブロック消しを1回だけできるのなら、0呪文かそれかで判断できそう、ちょうど2ブロック消しがないならちょうど3ブロック消しとか
- @neetsdkasu #@neetsdkasu
全部でちょうど2ブロック消しが1回できるのならスコアが310からテストケースの個数分増えるはず
- @neetsdkasu #@neetsdkasu
うーん、2回目にサブミッしたやつが1呪文だけ唱えるので一番多く消せるのを選ぶってやつでスコアが2しか増えなかったということを踏まえるとテストケースはどれもかなりバラついてるという異常な感じか・・・?
- @neetsdkasu #@neetsdkasu
RGB
BRG
RGB
適当に考えても何らかの法則性が出ちゃうなあ - @neetsdkasu #@neetsdkasu
GBGBRBRBR
BRBRGRBRB
GBGBRBRBR
とか - @neetsdkasu #@neetsdkasu
ひとまずテストデータのジェネレータを極端にバラバラになるのを生成するようにさせないとテストする意味なさそう
- @neetsdkasu #@neetsdkasu
RGBGBGBRGBG
BRGRGBGBRGB
貪欲法で作れそう - @neetsdkasu #@neetsdkasu
ロジサマの『JSの羽』問題用のテストケース自動生成(バラバラversion)のコードできた…
#ロジサマ #paiza #コード詠唱
out.paiza.io/projects/A1doF… - @neetsdkasu #@neetsdkasu
微塵も優しさを感じないフィールドになるな…
- @neetsdkasu #@neetsdkasu
はぁこりゃスコア上がらんわけだ・・・
- @neetsdkasu #@neetsdkasu
ランダムに消してくの見た感じ、横の連結が発生しやすいっぽいなあ
- @neetsdkasu #@neetsdkasu
あと上位が5000点超えてっからここまでバラバラな感じじゃなくそれなりきれいに斜めに並んでるっぽいのかなあ・・・
- @neetsdkasu #@neetsdkasu
序盤は横の連結が増える呪文を使って、終盤は連結したやつを消してく感じ?
- @neetsdkasu #
まぁいいや
寝る