-
masashinakata
- 2442
- 0
- 0
- 0
-
- いいね！0
ツカモ
@tsukammo
コドゲ、Spring2022コンテストのルール翻訳を書きました。 tsukammo.hatenablog.com/entry/2022/04/… #codingame
2022-04-22 01:06:17
koyumeishi
@koyumeishi_
MM 135, フローみを感じたのでちょっとやりたかったんだけど途中で脇道にそれて時間失ったので不参加決めてしまった
2022-04-22 01:37:19
yowa
@yowa
Mリーグ昨日(Day 3)の第一回戦オーラスの 7m、押し引きのボーダーラインは放銃率何%くらいなんだろう。目的はファイナルの優勝確率を最大化、として
2022-04-22 02:00:45
yowa
@yowa
聴牌取れる確率をどう読むかも押し引きボーダーに関係するか。 4人ゲーだと行動の組み合わせが複雑すぎて、簡易モデルを用意してのシミュレーションも難しそうだな…
2022-04-22 02:02:34
koyumeishi
@koyumeishi_
考えてたこと * グラフが二部グラフなら頂点集合から最大流で解を発見できる (同時使用不可辺は事前に使うものを決め打ちするか, 排他関係になるように流し戻す) * 二部グラフにならなくても, S, T に分けたとして, s-s, t-t 辺を決め打てば二部グラフになる
2022-04-22 02:09:07
koyumeishi
@koyumeishi_
* 条件を満たす連結成分 U, V 間に u->v 辺があったとして, u<-v に流量 1 を流せれば u-v を接続できる. このとき逆辺は流量 2 以上のものだけを使って流せれば連結性を保ったまま U-V 接続可能 * b-flow 的なものを思うと, 集合に新しく頂点を追加したとき次数が足りてない隣接頂点があればすぐに
2022-04-22 02:10:47
koyumeishi
@koyumeishi_
... 辺をつないでしまっても問題ない. 少なくとも満たす必要がある \sum B_s = \sum B_t などの条件が整ったときにちゃんと流しなおせば整うので
2022-04-22 02:11:29
koyumeishi
@koyumeishi_
といった感じで, 一つの valid な解に適当に頂点を追加したり削除したりしてフロー解を発見 -> 非連結な成分の接続を試みる -> スコアが上がってたら状態を更新. 解が発見できない / スコアが低下したら破棄 みたいな山登りを多点スタートで successive halving っぽくやろうとしてた
2022-04-22 02:12:09
koyumeishi
@koyumeishi_
頂点を塗り分けて陽にグラフ構築して―と思ってたけどよく考えればランダムに探索しながら, S -> T は辺を追加可能なとき, S <- T は辺を削除可能なときに辿れると思って 動的に色付けしながら増加パス探すようにすれば柔軟でいいな―ってこれランダム探索ですね ランダム探索の人は実質フロー
2022-04-22 02:13:02
koyumeishi
@koyumeishi_
脇道にそれたってのは、使う頂点集合を選べば SAT で解の存在判定できるな(排他辺の関係も込みで)－とSATソルバの資料を漁ってワクワクしてた 日本語資料とかコードとか結構転がっててありがたいなぁとよく見ると半分ぐらい togatoga さんのやつで笑っちゃった。一体何回SATソルバ実装してるんだ(感謝)
2022-04-22 02:22:47
コルン
@colun
twitter.com/nablas_inc/sta… Kaggleのgoldメダルを半年ごとに1個取り続けている状態と、AtCoderでレーティング1600以上（青）を維持している状態とが等価。AtCoderバンザイ！！
2022-04-22 20:28:42
NABLAS株式会社
@nablas_inc
✨記事公開✨ NABLASにある「Kaggle＆AtCoder支援制度」について紹介する記事を公開しました！！ KaggleやAtCoder等の競技プログラミングの実績に応じて、業務時間をコンペ活動に充てることができます💻 計算機資源の支援もあります！ 👇詳しくはこちらの記事をご覧ください
2022-04-21 17:22:05
コルン
@colun
え？ あれ？ wood league 1用のコードを書いてる途中でまだ未提出なのにbronze league行ったよ、、、？ 新ルールとは一体？
2022-04-22 22:19:19