ランダムグラフ生成談義

Cinnamoroll @Cinnamon_VR

作問のときwriter解(自分)のコードがあってるかってどうやって確かめればいいの 愚直コード書いて小さいケースが合うか見ればいい？

idsigma @IKyopro

@Cinnamon_VR 自分はそうしていました

Cinnamoroll @Cinnamon_VR

@IKyopro 大変だ... おきもち回のセット作るのにどれくらい時間かかりました？？

てんぷら @tempura_cpp

ライター解の正当性の証明 : テスターがACしてくれた

idsigma @IKyopro

@Cinnamon_VR Cまでは合わせて3-4時間くらいだと思います(木のランダム生成が少し大変でした) Dは自分が結構バグらせて数時間かかりました Eは2~3日くらいです writer解を合わせるのもそうですが、想定TLEがちゃんとTLEするかとか、想定嘘解法がちゃんと落ちるかとかをどこまで検証するかで割と変わると思います

idsigma @IKyopro

これはかなりある

Cinnamoroll @Cinnamon_VR

@IKyopro それくらいかかっちゃいますよね、ちょっとずつ進めていきます...

idsigma @IKyopro

Kaiten Sushi?は正直勿体なかったかもしれない(じゃあ出す機会が他にあるのかと言われると別ですが)

てんぷら @tempura_cpp

数え上げを作問しましょう！！(テストつくるときに考えることが少なくてすむので)

idsigma @IKyopro

@Cinnamon_VR はい、妥協せずにじっくりやるといいと思います

てんぷら @tempura_cpp

@IKyopro HUPCで出題しても評判はよかったと思います

idsigma @IKyopro

まともな数え上げが生やせない(そもそも解けないしね)

idsigma @IKyopro

@tempura_cpp うーんたしかにそうですね(その話が来る前なので仕方ないんですが) また面白いのが生やせるといいですね…

not @not_522

作問のめんどくさい順、幾何>グラフ>貪欲>構築>その他>DP、くらいの感覚

てんぷら @tempura_cpp

@IKyopro あの問題セットをあれくらいの期間で出せるならけっこう期待できると勝手に思っていて

idsigma @IKyopro

グラフの自動生成は1回作っちゃえば…

てんぷら @tempura_cpp

グラフの自動生成、どうやるのがいいんですか

not @not_522

グラフの自動生成、コーナーケースが多すぎて不可能だと思う

idsigma @IKyopro

@tempura_cpp わーい 真ん中あたりに置けそうなものはいくつかできています、後ろの方は知らないです writer陣的にジャンルがいい感じにバラけそうなので楽しみです

てんぷら @tempura_cpp

@IKyopro てんぷらの進捗はありません(というかGWで放出してしまいそう)

not @not_522

ランダムグラフを作るだけなら、隣接行列にランダムに辺を置いていけばOK

idsigma @IKyopro

@tempura_cpp これを採用しました chillbrains.hateblo.jp/entry/RandomGr…

てんぷら @tempura_cpp

@IKyopro あるところにはあるんだなぁ(感動)

idsigma @IKyopro

@tempura_cpp 基本的には木が生成できればあとはてきとうに辺を追加するだけなので

not @not_522

真面目にグラフを生成したいならAGLがオススメです github.com/iwiwi/agl