diverta 2019 Programming Contest

てんぷら @tempura_cpp

@kroton_pc それはわりと直感的にできて、Bの個数に対するAの割合が高いやつを前に持っていくといいです

kroton @kroton_pc

@tempura_cpp 考えてみますー

satanic@研究💪 @satanic0258

こんな？ pic.twitter.com/PcZJRBj2B6

拡大

kroton @kroton_pc

あーなるほど 各文字列内ですでに成立してるABはどう並べても変わらないから考えなくて良くて、そうすると(Aの個数, Bの個数)だけ考えればよくて、これは隣接する二項間で改善するようにswapする例のアレに落ちるのか

kroton @kroton_pc

「隣接する二項A, Bをどういうときにswapしていいか(スコアが改善する or 劣化しない)の十分条件を考えて、AのみBのみに依存したなんかの量が2つでてきて、その量でソートする例のやつ」 って覚えてます

kroton @kroton_pc

これ十分条件だからこの量の大小が逆転していても実際はswapできることがあることには注意

kroton @kroton_pc

順序が自由ってなかなか手ごわいからこういう順序を固定できるアプローチ知っとくといいよね

kroton @kroton_pc

順序が自由な問題に対するアプローチ - 隣接二項swapできる条件考えてると順序を固定できる - 挿入DP - 2^n - n! これ以外なにかありますか

kroton @kroton_pc

挿入DP以外はなるべく順序固定したいぞって気持ちで考えていかないと厳しそう 貪欲に落ちがちな気もする

kroton @kroton_pc

解法をテクニックに、テクニックを気持ちに昇華させていきたい

kroton @kroton_pc

これ答えとまでは言わずとも問題設定から有効そうなアプローチを列挙しておすすめ考察パスをサジェストするとかはできそう

kroton @kroton_pc

あとで解く atcoder.jp/contests/cpsco… community.topcoder.com/stat?c=problem… judge.u-aizu.ac.jp/onlinejudge/de…

keymoon @kymn_

@kroton_pc 条件を決めれば貪欲できたりする場合もありそうです(自明っぽいですが、最大値の最小化問題で順序自由をよく見る気がしたのもこれに近いかなあと)

kroton @kroton_pc

@kymn_ なにか例題ありますか？お暇な時でいいので教えてください！

keymoon @kymn_

@kroton_pc ネタバレになってしまいますけど、これとかが該当しそうです(これまた最近のものですけど) atcoder.jp/contests/cpsco…

kroton @kroton_pc

@kymn_ ありがとうございます！

kroton @kroton_pc

atcoder.jp/contests/cpsco…

chokudai(高橋 直大)@AtCoder社長 @chokudai

AtCoderにおいては、参加ユーザに対して「お客様は神様」とは思ってはいないんだけど、ユーザが参加してくれることによってスポンサーさんからお金が貰えるのは間違いないので、当然感謝するべき立場だと思ってるよ。だからこそ無料で色々提供しているわけだし。

chokudai(高橋 直大)@AtCoder社長 @chokudai

こちらも時間を頂いているわけだから、当然それを使う価値のあるコンテンツを出していかないといけない。ただ、「コンテスト自体の価値」以外を保証するのは、今のAtCoderの体力では難しいのよね。解説PDFやらのクオリティも正直ちょっと厳しい。

chokudai(高橋 直大)@AtCoder社長 @chokudai

コンテストの価値は保証するけど、それ以上は「ないよりはあった方が良い」って形で提供しているのが実情で、当然それを提供した初期は有難られたんだけど、一度提供したものって当然あるべきもの扱いされていくみたいで、最近はクオリティに不満が出るケースもかなり多い感じになってる。

chokudai(高橋 直大)@AtCoder社長 @chokudai

こういう感じになってくると、「不満に対応できなくなるから、しっかりしたクオリティが安定提供できるもの以外は、最初から提供するのをやめよう！」って感じになっちゃうんだけど、それってみんな不幸せになるので、ここの匙加減がかなり難しいのよね。

kroton @kroton_pc

えー1時間くらい考えてた問題全然解けないからよく問題見たら全然違う問題解いてた〜 いえ〜い！

kroton @kroton_pc

CPSCO2019 Session1 F - Fruits in Season atcoder.jp/contests/cpsco… おもしろかった にぶたんして下限を打ち決めると半径のようなものが出てくる その半径と中心 t[i] から範囲を作って考えると結局これに落ちる snuke.hatenablog.com/entry/2019/01/…

kroton @kroton_pc

僕が誤読した問題 「果物iをj日目に食べると満足度はA[i] - abs(j - t[i]) * B[i]です。満足度の合計の最大値はいくつですか？」 問題ちゃんと読めや

kroton @kroton_pc

CPSCO2019 Session3 F - Flexible Permutation atcoder.jp/contests/cpsco… 解法の例題として教えてもらったので最初から答えは知っていたんだけど、これめっちゃ面白い