Writerをした時の話
この記事は Competitive Programming (1) Advent Calendar 2018 4日目の記事として書かれたものです。
はじめに
と言っていましたが、予定を変更 (という名のテーマ決めの失敗) して、2016年に書こうと思っていたテーマで書くことにします。
テーマは「Writerをした時の話 (TopCoder SRM 694)」です。
経緯
元々一番好きな競技プログラミングのコンテストはSRMだったので、18歳になったら1回writerやってみたいなぁとずっと思っていて、2016年の春に18歳になった時から問題案を考え初めました。
そして6月の頭に6問(5問)完成して、7/10に行われたSRM 694のwriterをすることに決定しました。準備はJavaで想定解を書かないといけないなどかなり大変でした。
結果はこんな感じでした。
今振り返ってみると、Div1はHardがかなり簡単で、全完が20人近く出るのも当然だなという感じがします。(こういうセットはHard早解きゲーで順位がついてしまうので微妙ですね...) Div2も上位陣は3問とも見た瞬間に解いているような点数を出していて、もう少し捻りがあっても良かったかもしれません。
前置きはこんな感じで、以下各問題にコメントや背景を書いていこうと思います。 (自力で解きたい人はあとがきまで飛んでください)
問題の詳細
MakingPairs(Div2 Easy)
概要:
同じ数字が書かれたカードを2枚組み合わせてペアにできるとき、最大でペアはいくつできるか
コメント:
流石にやるだけだと思います。このスロットに捻った問題を置く必要はないし、変なストーリーを入れて読解に時間を掛けさせるのも本質ではないので、こんな感じの出題をしました。
DistinguishableSet(Div2 Med, Div1 Med)
概要:
N人にM問のアンケートに回答してもらった時、M問の部分集合であり、N人のその集合に対する回答が全て異なるようなものはいくつあるか
(Div2版はN<=50, M<=10で、Div1版はN<=1000, M<=20)
コメント:
もし問題の部分集合2^M個すべてに対して、回答がN人みな違うかチェックしていいなら簡単です。それがDiv2 Medです。
Div1 Medでそれをやるとどう実装しても通らないはずで、もし通ったら定数倍最適化の†天才†です。
ここで余事象の発想で、「ある2人がいて、回答が一致する」(<=>「全て異なる」)ような集合をカウントすることにすれば、
「N人のうち2人の組み合わせを取って、その2人の回答が一致する問題の集合にフラグを立て、最後に各集合からその部分集合にフラグを伝搬する」
という解法にたどりつけると思います。実装は無なので完全なる一発ゲーです。
このセットでは一番気に入っている問題で、「アキネーターってどう実装されてるのかな？」って疑問を持った時に出来ました。
UpDownNess(Div2 Hard)
概要:
長さNの順列で、P[i] < P[j] > P[k]なる(i,j,k)の組がK個あるようなものは何通り？
コメント:
「DPは左から順に見るもの」みたいな固定観念があると全く解けません。(少なくとも今までどの数字を使ったのか？を覚えていないといけないため)
「順列の問題は小さい順/大きい順 に挿入して考えるとよい」っていう典型発想があれば瞬殺です。
完全に教育的問題なので、このスロットに置きましたが、普通にガンガン通されてびっくりしました。
TrySail(Div1 Easy)
概要:
非負整数の集合を3つに分け(空集合はダメ)、各々の集合に含まれる整数のxorを取り、その総和を最大化してください
コメント:
dp[i][a][b][c][mask] = (i番目まで見て、各々のxorがここまでa,b,cで、3つの集合が空集合かどうかはmaskにエンコードされている という状況はあり得るか)
というのがノータイムで出てくると思います。
これだと落ちるんですが、冷静に考えるとi,a,bからcは一意に定まるので、一つオーダーが落ちてこれで通ります。
実は、空集合はダメ、と言っているんですが冷静に考えると (a xor b) <= a+b なので、これは無視しても大丈夫です。(無視すると上の落ちる解が通ってしまったようです)(悲しいね)
流石に競技プログラミングが下手すぎると思う......
SRMDiv0Easy(Div1 Hard)
概要:
初めすべて0の配列に区間加算クエリを何回か行います。加算した値は[L_i,R_i]のどれかであることが分かっています。
このとき、最終的に得られた配列は全要素が等しかった。こういうことがあり得るか、あり得るならその値として考えられるものの最大値を求めよ
コメント:
パッと見めっちゃ難しそうじゃないですか？僕はそう思います(てへぺろ)
配列の差分を取るとフロー(最小流量制約つき最大流)になるので、蟻本に小さく書かれているアルゴリズムを実装すると通ります。
この問題は、「なんか数列の差分を取ってうまく解ける問題作れないかな～」って考えていたら区間加算クエリがフローに対応することに気づいて出来ました。正直トプランの方々には秒で見抜かれていた気がします。
あとがき
多くの人にとって、役に立ったり参考になる記事ではないと思いますが、競技プログラミングの1つの側面として興味を持って頂けたら幸いです。
来年はアルゴリズムの話ができるよう早めに準備をします。
