読者です 読者をやめる 読者になる 読者になる

null部の部誌

プログラミングの話とか色々。

Women's CodeSprint 3に参加してみた

某プロから「Women’s CodeSprint 3という女性向けコンテストがあるから参加してみて!」みたいなメンションが来たので、ちょっと参加してみました。

結果

6問中4完、188.24点/245点満点で、186位/3541人でした。 Programming Problems and Competitions :: HackerRank
順位表見たら日本の中では2位!とか思ったんですがそもそも日本人8人しかいませんね……少ないなあ………

概観

開始時刻にとりあえず問題をパッと見たのですが、

  • Easy 2問
  • Medium 3問
  • Hard 1問

の合計6問を48時間で解くということで、恐らくTシャツ枠は速解き勝負だろうなと思いました。私は速解き勢になれるほど時間に自由がないので、まったり参加することにしました。

あまり本質的ではないのですが、非ASCII文字を含むコードを受け付けてくれないようで、日本語コメントを書いていると弾かれるのが少々面倒でした。

A. Birthday Chocolate (Easy, 10点)

与えられた数列について、連続するm項の和がdとなるような箇所の個数を求めればよい。

d、m共に小さいので、何も考えなくても数列の項それぞれに対しm項の和を計算するだけで解けます。

「連続するm項の和」ということで、数列の最後の方での和を計算する際に範囲外アクセスをしないようにする必要がありますが、多めに配列を確保しておいて、数列の外にあたる部分はINFで埋めておくと場合分けとか考えなくて済むので楽だと思います。(INFがあまり大きいとオーバーフローするので、d≦31だしINF=32で良いと思います)

B. ASCII Flower (Easy, 20点)

花のAAをr行c列出力する。

AAを1行ずつに分けて考えます。くらいしか書くことがない。

C. Hackathon Shirts (Medium, 30点)

n個の値のうち、v個の閉区間の少なくとも1つに含まれるものの数を出力せよ、というクエリがq個来る。

O(nv)しか思いつかず、まあギリギリ間に合うかな!wと思っていたらクエリがq個来るのを忘れていてTLE。二分探索してチェックする閉区間を減らしたりcout・cinをprintf・scanfにしてみたりと色々小手先の高速化をしてみたらちょっとだけTLEケースが減りました。結局、重なっている区間はまとめて1つの区間として扱うことでACしました。(これは序盤で思いついてはいたんだけれども、区間が1つも重なっていなくて全く高速化されないテストケースが絶対にあるはずだと思っていたので、あまり実装する気が無かった)

区間をまとめる処理については、v個の区間をpairのリストにしてソートし、隣接している区間が重なっている(または接している)かを調べて、重なっていれば一方を更新してもう一方は削除、というのを前から後ろにかけて繰り返せばよいです。

重なっている(または接している)隣接した区間 v_1=(a_1, b_1), v_2=(a_2, b_2)とすると、重なっている(または接している)条件は b_1 \leqq a_2-1で、区間をまとめると v_3=(a1, max(b_1, b_2))となります。
私は最初b_1>b_2の場合を考えていなくてバグらせました。ただただ頭が悪いです。ただこの問題はテストケースを自作するのが簡単なので、すぐに気づけました。

ハマったこと

いろんな位置で削除をすることになるので、ランダムアクセスすることもなさそうだし、区間を表すpairのリストにはstd::listを使ってみました。vectorでTLEするかどうかは知らないです。std::listはあんまり使ったことがないので、色々とハマりました。

std::listはstd::sortができない

std::sortはランダムアクセス可能なイテレータを扱うらしく、双方向イテレータであるstd::list::iteratorは使えないようです。代わりに、std::list::sortを使うことでソートすることができます。ならし計算量はO(N log N)。

双方向イテレータにはoperator +がない

まあ普通に考えればランダムアクセスができないので、itr+5とかできないのはそれはそうなんですが、じゃあ隣のイテレータはどうやって取得すれば良いのだろうと思ったら、std::prevとstd::nextというものがあるようで、たとえばitr+n的なことをnext(itr, n)というように書くことができます。
ただよく考えたらitr2=itr;++itr2;としてループ回せば良い気がします。

eraseの返値は削除した要素の次の要素を指すイテレータ

これはstd::listに限らずSTLコンテナはだいたいそうだと思うのですが、「eraseするとイテレータが壊れるけど、eraseがちゃんと新しいイテレータをくれるからOK!」とか言ってforループ内でeraseすると、消した要素の次を指すイテレータがさらに++itrされてしまいます。今回は、削除した直後のイテレータはマージした結果の区間を指していてほしいので、比較した2つの区間のうち前方にある方を削除することで実現しています。削除しない場合は普通に++itrをします。

そんなこんなで計算量はO(q(v log v+n+nv))です。ハイ。これが想定解な訳ないだろと思って上位陣のコードをちらっと見たんですが、何をやっているのか私には読めませんでした。精進します。

D. Choosing Recipes (Medium, 50点)

r個のレシピと、p個の材料がある。それぞれのレシピはp個の材料のどれを使いどれを使わないのかが書かれている。p個の材料にはそれぞれ価格が設定されている。材料は一度買うと無限に使うことができる。今、既に持っている材料と、作るレシピの数nを与えられたとき、買わなければならない材料の価格の総和の最小値を求めよ、というクエリがq個来る。

r≦30でn≦10なので全探索しても最大_{30} C _{10} \approx 3.0 \times 10^7なのでまあギリギリイケるかな(適当)

_r C _n の全列挙は、手で書き出す時みたいな感じでやります。

適当にk番目の要素を選んで、 f:id:pizzacat83:20170315204740p:plain

次はk+1番目以降の要素を選びます。 f:id:pizzacat83:20170315205103p:plain

これを繰り返してn個選ぶと、必ず昇順で選ばれるので、同じ組が重複して2回以上数えられてしまうことはありません。

さて、これを再帰関数として実装します。ナップサック問題と違って、単純に各レシピのコストの和を最小化するわけではないので、それまでに選んだレシピの情報を何らかの形で渡す必要があります。引数は今まで選んだレシピのvectorでも良いかもしれませんが、問題文でレシピがビットの配列であることがさんざん強調されていることもあり、「あと何個レシピを選ぶか」「今まで選んだレシピにおいてある材料を使うかどうかのビット配列」「何番目の要素から探索するか」を引数にとって、コストの最小値を返すことにしました。n個選び終わったら、引数のビット配列からコストを計算します。既に持っている材料については、その材料のコストを0にしておけば問題ないでしょう。

ってクエリq個来るじゃないか

まーた複数クエリの分の計算量を忘れていました。さすがにTLEしそうです。なのでメモ化をします。計算量は O(q(2^prn))。おしまい。

ちなみに、「今までに選んだレシピのvector」が違っても「あと何個レシピを選ぶか」「今まで選んだレシピにおいてある材料を使うかどうかのビット配列」「何番目の要素から探索するか」が同じであれば結果は変わらないので、後者を引数にした方が効率的でしょう。「それ以前の状態がどうであっても、これが等しいなら値が等しくなる」ということに気付くことが、メモ化の一番重要なことなのかもしれません。その点では、この問題はレシピをビットの配列として入力させるよりも、使う材料のリストで与えた方が面白かったのではないかな、と思いました。

ところでstd::bitsetはビット演算に慣れていなくても扱えるので良いですね。std::bitset::to_ulongで整数として扱うこともできますし、operator []で配列のように扱うこともできます。std::bitset::to_stringもあるので、デバッグ出力も問題なくできます。良い。

E. Elevator Simulation (Medium, 50点)

与えられたルールに従って、エレベータをシミュレートせよ。

現在テストケース4つくらいWAしているので、以下の内容は誤りを含んでいる可能性が高いです。ACしたら追記します。
2017/03/16追記: ACしました。
「最後に乗車した乗客の降車時刻」を求めるべきであるところを、「最後に降車した乗客の降車時刻」を出力していました。

実装するだけです。私は無限にバグらせることが容易に予想できたので、これでもかとデバッグ出力をしました。

全部vectorでもいけるかもしれませんが、人が待っている列はFIFOって書いてあるしqueueとか使うとよいと思います。「教師は生徒の前に割り込む」というルールは、「教師の列」と「生徒の列」を作って、教師の列が空である場合に限り生徒の列からエレベータに乗せるようにして実装しました。あるいは乗客の情報を優先度付きキューに入れることでもできそうな気もします。

「エレベータが満員の時、後から来た教師は最も遅く乗車した生徒を追い出して乗る」というルールについては、エレベータの乗客から生徒を後ろから探して、その生徒をeraseし、教師をpush_backして、追い出された生徒は生徒の列とは別のstackに突っ込むことで実装しました。追い出された生徒よりも早く列に並んだ生徒は、多分存在しないはずです(証明はしていません)。

エレベータから人を下ろす際は、事前に乗客を目的階でソートしておくと、後ろからどんどんpop_backするだけになります。その後、乗客がまだ残っていれば上昇し、もう残っていなければ下降します。

2017/03/16追記:
最後に乗車した乗客は、将来列に並ぶ人の配列と、全ての待ち行列がemptyになっているかどうかを判定すれば良く、もしそうであればその情報も併せてエレベータのvectorに突っ込みます。この時これ以上人は来ないので、教師に追い出される等を考える必要はありません。エレベータから人を降ろす処理の中で、もし「最後に乗車した乗客」である場合に、その時刻を出力し終了すればよいです。

ハマったこと

std::reverse_iteratorをそのままでeraseはできない

やろうとするとコンパイルエラーが出ます。そこで、reverse_iteratorが内部的に持っているイテレータを、std::reverse_iterator::baseで取得します。ただし、この内部的に持っているイテレータは、reverse_iteratorが指している要素の一つ前(begin側)を指すイテレータなので、取得したイテレータに+1したものをeraseに渡すことになります。

以下の記事は図解もあってとても分かりやすいと思います。 改善版 reverse_iterator 使用中のerase()の仕方 - 自習室

std::tupleの使い方

「教師か生徒か」「到着時間」「目的階」の3つの情報をまとめて扱いたかったのですが、構造体は比較関数を書くのが面倒なので、std::tupleを使ってみました。宣言はsyd::pairっぽく書けるし、 std::make_pairの代わりにstd::make_tupleなんてものがあります。ただし、pairは値をfirst, secondで扱うことができますが、tupleの場合はget<0>(tpl)みたいな形になります。

まあだからなんだと言われるとそうなんですが、私は何が何番目に格納されているのか訳が分からなくなるし、型が一緒だとその誤りも結構見つけづらいので、やっぱり3つ以上の値の意味を数字と結びつけるのは無理だと感じました。今後は素直に構造体を書いて、分かりやすいメンバ名をつけるようにした方が、総合的に楽だと思いました。

なお、これは個人の感想です。問題なくtupleを扱えるような人であれば、pair in pairみたいなことをしなくても良いので、便利ではないかと思います。

F. Spring Decorating (Hard, 75(30)点)

R, B, Gからなる長さnの文字列を作る。文字列中に出現するRB, RG, BR, BG, GR, GBの個数の上限が与えられたとき、上限6つのいずれも超えない文字列の個数を、 mod(10^9+7)で求めよ。
テストケースの40%は、RG=BG=GR=GBをみたす。

部分点解法

RG, BG, GR, GBはいずれも登場しないので、RBとBRについてのみ考えます。

RBがちょうどx個、BRがちょうどy個出現する文字列の数を考えます。RBの次にRBが、またはBRの次にBRが来ることはないので、|x-y| = 0, 1となります。

(i) |x-y| = 1のとき

x-y = -1をみたす文字列はx-y = 1のRとBを入れ替えた文字列となるので、x-y = 1についてのみ考えます。

これをみたす文字列は、RBとBRだけ抽出すると、RBで始まり、RBとBRが交互に来て、最後はBRになります。すなわち、RBとBRの並びが一意に定まります。

よって、n個の文字列の中でどこが色の境目になるかを決めれば、その色の境目にRBとBRのうち適切な方を割り当てられるので、文字列は一意に定まります。したがってn個の文字列の文字と文字の間n-1箇所から、色の境目となる(x+y)個を選ぶ場合の数を求めればよく、これは \displaystyle _{n-1} C _{x+y}=\frac {(n-1)!} {\{(n-1)-(x+y)\}!(x+y)!}と計算できます。結局これのmod(10^9+7)を計算することになりますが、除算を含む式の剰余を求めるので、ひと工夫必要です。

aとpが互いに素のとき、フェルマーの小定理を用いて除算を乗算に置き換えることができます。知識問題。
yukicoderのwiki合同式について色々書いてあります。 https://yukicoder.me/wiki/mathematical_property数学的な性質 - yukicoder
yukicoderには順列や組み合わせの剰余を求める問題がありますし、確か蟻本にも組み合わせの剰余を求める問題が載っています。

(ii) |x-y| = 0 すなわち x = y のとき

(i)と違って、RBに始まりRBで終わるか、BRに始まりBRに終わるかで、RBとBRの並びが2通り考えられます。ただしこれはRとBについて対称なので、片方について考えて2倍すれば良いです。

あとは(i)と同様で、場合の数は \displaystyle 2 _{n-1} C _{x+y}=2 \times \frac {(n-1)!} {\{(n-1)-(x+y)\}!(x+y)!}となります。

ここまで考えたら、あとはxとyをRBとBRの制約と|x-y| = 0, 1をみたすようにループを回して、総和をとるだけです。

これは罠で

x = y = 0の時を考えます。これをみたす文字列は、上式の通り、「全てR」「全てB」の2通り。ではありません。

「全てG」もこの制約を満たすのです。なお、x = y = 0でないときは、RG, BG, GR, GBのいずれかが出現してしまうので、Gについては考えなくて良いです。私はこれに気づけずINF時間悩み続け、n文字の文字列 3^n個全て調べる愚直解を書いてやっと気が付きました。ふう。

本解

まだACしていません。ACしたら追記します。

ひとりごと

#codelikeawoman ってどういう意味なんだろう。「コンピュータ科学における男女格差の改善を手助けするコンテストです。」みたいなことが書いてあるけど、女性らしいコーディングって何だろう……