AOJ 3053 - Phone Number (RUPC2019 Day2 C)

問題 提出コード

解法

配置方法は9!通りなので、全てに対して探索を行いたいです。
ので、ある配置のときにかかる操作回数の最小値の求め方を探ります。
すると、次のようなことをすればよいことになります。

1. あらかじめ、文字列について、どの数字からどの数字への遷移がいくつ存在するかを調べておく

2. 任意のマスから別のマスへの遷移方法を、マンハッタン距離かなにかを利用して求めておく

3. 最初に求めた遷移の個数と今の配置、そして先ほど求めた距離を元にして、現在の配置の操作回数を求める

2つめの操作についてですが、
012
345
678
とマスに番号を付けると、
は上から行目、左から列目に存在しています。
ので、との距離は、となります。
そして、9!通りの配置を調べるとき、のマス目で調べるのではなく、1次元配列に1~9の番号を入れておき、next_permutationで順列を順番に生成しながら、配列の添え字と上のマス目と照らし合わせて調べていくのが個人的に分かりやすいかなと思います。

感想

ぱっと見どうやるのかな～とは思ったのですが、あらかじめ距離等を計算しておくことで、時間内に答えが求められることに気づきました。ただ、これでも計算量は結構ギリギリだろう…と思って提出してみると、意外とはやかったです(c++で0.03s)。

AOJ 3055 - こたつがめを燃やさないで (RUPC2019 Day2 E)

問題
提出コード

解法

マス目を移動する際のコストを辺とみなしながらダイクストラ法を用いていくとよいです。
遷移の種類はいくつかあり、

• コストで、塀でない上下左右の隣接したマスに移動する

• コストで、上下左右の隣接したマスに移動する

• コストで、右上、右下、左上、左下の斜めのマスに移動する

です。
もちろん、下の2つの遷移を行うには、今いるマスを含めて周囲9マスのどこにも爆弾が存在しない、という条件が必要です。
しかし、斜めに移動する遷移を先に行っておくことにより、どの塀がまだ存在しているか、という情報を持つ必要はなくなります。
あとは、これをもとにしてダイクストラ法を用いることによって、答えを求めることができます。

感想

ダイクストラ法で、priority_queueにプッシュする要素は、最短コストを更新(もしくは初めて来た)場合なのですが、現状の最短コストと等しい場合にもプッシュをしてしまうと、ほぼほぼTLEします。
ということを過去何回もやってきたのですが、今回もやらかしました。悲しいです。

AOJ 3052 - Milk (RUPC2019 Day2 B)

問題
提出コード

解法

まず、の際は答えがになるのは自明なので、それ以外の場合について考えます。
個の空き瓶を個の新品と交換したとき、手元にある瓶の個数は個減ります。この減る個数は一定です。
よって、個の瓶が個未満になるまで交換することができる回数は、からを何回引いても未満にならないか、というものと同じになります。
よって、最終的には回交換できることになり、この回数にをかけたものと、最初のの和が答えになります。 modの撮り忘れには注意します。

感想

差が一定なので、差に注目するタイプです。最初から交換できないパターンの場合分けを忘れて、ずっと答えが合わず時間をかけました。

WUPC2019のお話(有志コンテストの準備編)

ということで、今回はWUPC2019に向けて準備してきたことなどをつらつらと書いていこうと思います。数か所問題のネタバレになる部分がありますのでご注意ください。
問題の解法についてはこちらをご覧ください。

emtubasa.hateblo.jp

やったこと

自分は運営サイド初参加で、(一応)途中参加だったので、大事な部分は先輩方に任せ、全体でやるような部分のお手伝いが主な部分であったかと思います。
いくつか羅列していくと、

• 問題の考案

• 解法の"捻出"

• writer解、嘘解法、TLE解等の作成

• テストケースの作成

• 問題文の清書

といったところでしょうか…日程決めや、AtCoderさんとのやりとり等は先輩方がやってくださったので、特にかかわることはなかったです。

問題の考案、解法作成

途中参加ということで、初めからいくつか問題の候補は存在していました。が、せっかく参加するので、問題をいくつか作ってみよう、と思いつくることにしました。
基本的には、自分はまず問題を作成してからその問題についての解法を考える、というスタイルをとっていました。
そのため、あるかもわからない(+自分が解けるかもわからない)問題について1日解法を考えていたりもしました…

今回作成した問題

自分は、Choose Your Charactersと、Artistの2問を作成しました。
どちらも、細かい(?)話はもう一つの記事に書いてあるので、興味があればそちらをご覧ください。
前者は、問題の枠組みを作成してから、自分でも解けるような解法になるように条件、制約を設定しました(結果的には高速化が可能だったので制約は引き上げられることになりましたが…)。後者については、最初から制約や条件を決めてから、解法を半日ぐらいかけて出しました(が、結局それが嘘だったのは秘密です)。
あと数問作成したりもしていましたが、つまらなかったり、解法がわからなかったり、時間が遅すぎたりしたのでお蔵入りとなりました。
先輩方に話を聞いたところ、問題の作成方法は問題ごとにバラバラみたいで、あるアルゴリズムを作りたいからそれに合わせた問題を作成する、というパターンもあるみたいです。それはそれで問題の作成難易度が高そうです…

writer解、嘘解法、TLE解等の作成

解法をいよいよコードに落とし込んでいきます。今回、できる問題については全員がwriter解を作成する、というのが目標だったため、そこそこのwriter解を書きました。
とはいっても、今回の問題は自分にとって難しいのが多かったため、ヒントだったり答えを教えてもらいながらが多かったです(むしろ、最終的に出題された問題の大半は自力で解けていない気がします)。ここで初めて実装したアルゴリズムもありました。
嘘解法や、変な貪欲解等も作成していきました。真面目に解いた問題が嘘解法でも役に立つのが、すこし悔しかったです。

テストケースの作成

テストケースは、ランダムなケースと、手で作成したケースの2つを用意します。
また、上で作成した解法や、このテストケースは、github上で管理します。
そして、今回はrimeというツールを利用して、randomケースの作成や解法の一致(と同時にTLE、WA...等)の確認を行っていきます。
こちらのツールの使い方については、beetさんの記事がわかりやすいので割愛します。
ここで驚いたのが、ランダムケースの作成の難しさ、です。
例えばChoose Your Charactersの場合、特に何も考えずにランダムにケースを生成すると、答えが"1 2"になるケースがほとんどになってしまいます。
同様に、Artistの場合は、答えが"0"になります。
そこで、ある程度故意に変数を偏らせたり、一部先に手で変数を決めてから残りをランダムに埋めていくことで、きっちりと答えがばらけるようにする必要があります。
最初は適当にランダムに配置すればいいや、と思っていたのですが、そんなことなかったです。
また、手でいくつかのテストケースの作成も行います。
一番変数が小さく(大きく)なるケースはもちろんのこと、ランダムケースでは対処しきれない、様々な嘘解法を落とすケースを作成しなければなりません。
ただ変数が大きいだけのケースよりも、解くのに時間がかかる最悪ケースを考えたり(これは解法によって最悪ケースが変わってきたりもするので、想定できる範囲の解法すべてに対応できるようにします)、貪欲や乱数を利用しつつ、細かい部分を想定解よりも時間がかかる解法で解く、といった嘘解法を落とすようなテストケースの作成も必要になります。
また、ハッシュを利用する問題では、ある程度弱いハッシュの作成方法だと落ちるように、ハッシュを衝突させたりもしました。
誰がどのような解法を提出してくるのかがわからない分、この部分はとても難しいと感じました。実際、嘘解法が通るといったコンテストもちらほらありますし、それだけ大変だということを改めて実感しました。

問題文の清書

そして、ある程度完成に近づいてきたら、いよいよ問題文の清書です。
問題文は、誰が読んでも理解できることを目指さなければならず、これまた難しい作業です。普段ブログを書いてるときのように、パパパッと適当に書くわけにはいきません。
例えば、Choose Your Charactersの問題の

この部分ですが、かなり悩みました。
最初は、数式だけ表示していれば確実ではあると思っていたのですが、それだと直感的な理解ができないと思い、文章だけで表現することを試みました。
ということで、一番最初は

• 同じ数字のペアが2回以上現れることはない。

という一文だけでした。
自分の中では、同じ入力と、反転させた入力の両方を表現しているつもりだったのですが、これだとわかりにくいかもしれないということだったので、

• 問題文の条件と矛盾する入力は与えられない。

という文章に変更しました。しかし、これだと結局矛盾した入力がどういうものかわからない可能性があるため、最終的に上の画像のような文章になりました。
これにより、問題文をさらっと読める方が増えたかどうかはわかりませんが、自分の中では納得できる文章になったと思っています。
このように、どの問題文についても、誰が読んでも理解できる問題文、というのを目指して全員で確認していきました。
また、問題文はhtml形式で書いていくのですが、自分はこれを触るのが初めてでした。
そのため、最初はほかの方のを真似してそれっぽくやっていたのですが、文法をかなり間違えていたため、大変でした…

解説PDFの作成

自分はD問題の解説を作成しました。
問題文同様、できるだけ多くの人が理解できるように書かなければならないので、とても難しいです。理解できなかった方々、文章力が足りず申し訳ないです。
また、普段ブログに解法を書く際は、いきあたりばったりでささっと書くことが多く、大した見直しもしないのですが(そのためバグがたくさんありそうです、見てないのでわかりませんが、ごめんなさい)、今回はきちんとしたものを作成しなければならないため、余計に難易度が上がっていました。AtCoderさんの普段のコンテストの解説は、とてもシンプルかつわかりやすく、綺麗にまとまっているのですごいと思います。
おそらく、完成した解説PDFは数日後にアップされるかと思うのでいましばらくお待ちください。

完成

こうして、問題文、想定解、テストケースが揃ったので、AtCoderのサイトにアップをして完成です。
問題の得点は、人によって500点だったり700点だったり、得意分野等によっても難易度が変わってくるので、今回はざっくり100~300でまとめることになりました。
結果、あのような配点になりました。
問題の順番も結構悩んだ部分で、要求される知識や考察力、得意分野によってバラバラなので、これが最適、と決めるのはなかなか難しいです。実際、E問題とC問題は、数日前に順番が逆になりました。必要されるアルゴリズムの難易度が理由です。結局、問題を解く際には、得点よりもコンテストの順位表から判断するのが一番賢いかもしれませんね。

当日の動き

基本的には、Clarの対応と、順位表を眺めるだけです。
Clarの対応はほとんど先輩方がやってくださったので、自分は順位表を眺めていました。
嘘解法で通されていたりしないか、どんな別解があるかのチェック等をしたり、参加者がどんなケースで落ちているかを確認していました。
直前に加えたコーナーケース等がすごい機能していて、眺めている側としては面白かったです。
また、ちらほら自分達とは違うやり方で通している問題があり、これもまた面白かったです。
ただ、A問題で詰まっている人を見ていると少し胸が痛かったです。

感想

楽しかったです！主な作業が春休みに入ってからだったので、自分の時間をある程度ゆったりと使うことができました。グループワークをするのもなかなかない経験で、しかもいろんなツールを使ったりしながらだったので、新しいことだらけで面白かったです。
高難易度の問題を自力で全然解けなかったのが唯一悔しい点です。
また何か機会があれば、コンテストを開催したいなぁと思っています。

WUPC2019のお話(解法編)

ということで、今回は各問題についての簡単な解法と、その感想です。
まだ解けていない問題もいくつかあるので、ご容赦ください…
運営側としてどんなことをしたか、についてはこちらの記事をご覧ください。

emtubasa.hateblo.jp

各問題の方針と感想

A - WAsedAC

問題
提出コード
早稲田の先輩方と言えば、やはりこのチーム名ではないでしょうか。もうすぐWorld Finalもあるみたいなので、頑張ってほしいです！
今回のコンテスト唯一の簡単枠。後ろから貪欲に見ていけばよい、というものです。
実質の簡単枠はこれだけな気がしています(B問題は少し考える必要があるため)

B - 10puzzle

問題
提出コード
パズル問題です。
基本的な方針ですが、マス全体の最大値を考えます。
全てのマスを全部0にしたいのですが、これはどこかのマスに5が存在する、もしくは最初からすべて0であるかのどちらかが成り立っていないといけません。ので、まずはその条件を満たしているかどうかを調べます。
この後は、上の2種類のうち、前者のみについて考えていきます。
全てのマスの最大値が4以下である場合、5である場合、6もしくは7である場合、8である場合、9である場合でまず場合分けが行われます。5の場合は1回の操作で、6,7の場合は2回の操作で、8の場合は3回の操作で、9の場合は4回の操作で全てのマスを0にすることができます。これは、全てのマスの最大値が5になるように調整する回数+全てのマスを選択して0に置き換える1回、の合計となります。
ですが、これにはコーナーケースが存在します。1行N列、もしくはその逆のパターンです。5が書かれているマスが端以外に存在すると、その左右のマスを1回で選択することができなくなってしまいます(5より大きい数が存在している場合に5を選択すると消えてしまうため)。ので、それぞれの部分に分けて計算していく必要があります。
具体例を出すと、
9 5 9 5 8
のようなマス目があると、左側の3つのマス目をまとめて3回操作を行って
2 2 2 5 8
となり、一番右のマスに対して2回操作を行って
2 2 2 5 2
となります。そして、最後に全部のマス目に対して操作を行うことで、全てのマス目が0となります。
こんな感じの場合分けを行うと、無事ACすることができます。
条件が少し細かいので、バグを抱えやすいかなと思います。
パッと解ける人は解けそうだけど、気づかない人は沼にはまりそうな問題です。まぁ、パズルなので…

C - Permutation City

問題
提出コード
全然思い浮かばなくて、結果先輩に解法を教えてもらいました。
まず、ある頂点についてみた時、そこから1つだけ辺を通っていける隣の頂点の集合をとします。すると、の中から任意に2つ頂点を持ってくれば、この頂点のペアは距離が2以下になっています。また、自身も、このの中に入れても問題ありませんし、入れなくても大丈夫です。
ということで、基本的にグラフを木とみなしてdfsをしつつ、その戻り際にペアを作成していくことで、うまく答えを作成していきます。
再帰関数を用意します(solve()とします)。引数が次に見る頂点の番号です。
戻り値を以下のように設定します。

• 今見ている頂点を含め、頂点を根とする部分木全ての処理が終わっていれば-1

• 頂点を除く、頂点を根とする部分木の処理が終わっていれば

すると、solve関数では次のようなことをすればよいです。

1. 今見ている頂点と隣接していて、かつ処理がまだ終わっていない全ての頂点について再帰を行う

2. 再帰をした際、戻り値が-1でないものをリストに記録していく

3. 操作が完了した後、リストの中身同士でペアを作成していく

4. リストに格納されている頂点の個数が奇数であれば、自身もリストに格納し、同様にペアを作り、戻り値として-1を返す

5. リストに格納されている頂点の個数が偶数であれば、を戻り値として返す

とすると、だいたいはうまくいきます。が、この場合にうまくいかないコーナーケースが存在して、dfsを開始した最初の頂点について呼び出したsolve関数がを戻り値として返すパターンです。このとき、最初の頂点のみ処理が終わっていないので、このままだと問題の条件を満たすことができません。
そこで、最初の頂点については、どこかしら隣り合った任意の頂点とペア、もしくはトリオを作成するようにコードを書き加えてあげれば、無事にACすることができます。
この問題、思いつくのも理解するのも解説するのも難しい気がします。..........

D - Choose Your Characters

問題
提出コード
まずはについて考えていきます。
ある区間について、その区間内でキャラに対して不利なキャラの数をとします。すると、その区間の幅に対し、となるようなが1つでも存在していれば、その区間は問題の条件を満たしません。逆に、全てのに対して上の条件を満たさないならば、これは解の候補になります。
あとは尺取り法を用いながら、での更新、およびで確認をしていけば、で答えを求めることができます。
さて、これを高速化しなければ、この問題を解くことができません。
今回は、の確認と更新の部分に注目します。
となるようなが存在するかどうかの確認は、の最大値だけをピックアップして確認するだけで、あっという間に行うことができます。これを実現するために、セグメント木を利用すればよいです。
ということで、をセグメント木に置き換えてしまえば、ある区間が条件を満たしているかどうか、をで求めることができるようになり、結局でこの問題を解くことができるようになります(一見に見えるかもしれませんが、相性の更新回数はたかだか回、最大値を確認する回数も回になるので、このような計算量になります)。
これです(最新作のやつ探したんですけどなかったです…オンラインの専用部屋かどこかでボイスを聞けた記憶があるので、聞きたい人は是非)。
ということで人生初の自作した問題です。
自分が公開した際は、想定解が高速化する前のものでした。気づいたらすごい高速化されていたのでびっくりしました…w
せっかくなので、自分の好きなもので問題を作ろう、とした結果がこれです。スマブラ要素がどこにもない…
初めは、相性の段階をもっと多くして、ポイントのようなものを計算していくような問題にする予定でしたが、単純に解き方が思いつかなかったのと、相性の表現が伝わりづらい(スマブラをやってる方々なら微有利、微不利といった単語が通じますが、一般的には通じなさそうです)ので、やめました。

E - Artist

問題
提出コード
まずは、180度という部分に注目しつつ、実験をいろいろします。
そして、i行目の、黒いマスの個数をとします。
すると、(x,y)というマス目で切り分けた時、、がなりたつことがわかります。これはつまり、を文字列として考えた時、との区間が回文になっている、ということです(これは列でも同様です)。
あとは、このような条件を満たすの個数を調べればよく、回文判定をするのにManacherやローリングハッシュ等を用いれば、時間内に答えを求めることができます。
ハッシュの衝突には注意しましょう。
大学の実話から生まれた問題でした。この問題で一番楽しかったのは、サンプルケースの3つ目を書いているときです…
ちなみにこんな絵を描きます。

何の絵かは想像にお任せします。
自作したとき、個人的にはこれめちゃくちゃ面白い！となったのであわてて提案しました。が、先輩方に瞬殺されてしまったので少し悔しいです(流石です)。おそらく、やるべきことに気づく+必要な知識が揃っていれば瞬殺です(そのため、最初はC問題に配置されていました)が、肝心な必要となる知識が普段は見ない(と言いたいのですが、数日前に数問、この知識が必要な問題があったみたいです)ので、この位置になりました。

F - RPG

問題
提出コード
最小カットを考えます。
「戦闘場面から次の戦闘場面への道のり」にすべて分解します(出発地点から最初の戦闘場面、そして最後の戦闘場面から終着点の部分は捨てます)。
そして、s,tという頂点を用意し、それぞれの道のりについて、

• sから道のりの最初の頂点へ容量の辺を張る

• 道のりの途中にある頂点を2つに分解し、1つめの頂点から2つめの頂点に向かって、その頂点で回復所を作るコストを容量とした辺を張る

• 道のりの最後の頂点からtへ容量の辺を張る

という操作を行います。あとは、sからtへフローを流し、最小カットを考えれば答えとなります。

G - Teishoku

問題
提出コード
定食の種類がとてつもなく少ないので、すでに準備した定食の種類を、ビットで持つことにします。
番目の定食を食べたときにのビットがたつとします。
現在の準備した定食の状態がであるとき、そこから先に発生する不満度の合計の最小値
とします。
すると、

となります。
あとは、今の状態の際に、の定食を準備するとどれぐらいの不満度が発生するか、を高速に求める方法がわかればこの問題を解くことができます。
番目の定食を準備した際に番目の定食を注文した人の中で発生する不満度の合計値
とすると、欲しい情報は、 (ただし、はに含まれない)
となります。
なので最終的には、を前計算で求めることができればよい、ということになります。これは、累積和を使い、入力された定食の注文の情報を後ろから見ていくことで前計算が可能です。
これを自力で解けたのは結構うれしいです。しかも、考察自体もかなりさらっとでき、実装もすんなりいったので、大満足です。

H - Doki Doki Programming Clubs! (3/11追記)

問題
提出コード
完全な解説ACです。頭良すぎませんか…？
というクエリが与えられたとき、の部員の方が少なかったとします。その際、回で計算を終えようとすると、側のレートの数列を前計算で、長さの数列に縮めておく必要があります。
縮めた後の数列に記録されるレートは、
となります。
ということで、あらかじめ前計算をしておき、各クエリに対してで答えればいい、となるのですが、これだとテストケースによっては前計算で時間がかかりすぎてしまいます。
ということで、前計算をする範囲を、長さまでの際のみに限定し、ともに以上であった際は素直に定義通り計算するようにすると、どちらも時間内で解けるような計算量で抑えることができます。また、一度行った計算は二回目以降行わないようにメモをするのも忘れないようにしましょう。
詳しくはこちらのツイートなり、後日アップされるであろう解説PDF(に書いてある…と思います)を読んでいただければと思います。

https://twitter.com/yamerarenaku/status/1104721694919290880

ということでとりあえず現時点で解けているのはA~G(+H)の7問です。

全体の感想

む、難しいです…
A,B,Gは自力で解くことができましたが、他はヒントや解説をもらってから解く形になりました。結構な初心者お断りコンテストになってしまっていそうです。が、どの問題も個人的には面白いと思っています！

コンテスト後の感想

A

いきなり普段のABCで300点ぐらいの問題だったので、配点だけ見て参加して解けなかった人には申し訳ないと思っています。
ですが、ここのACの人数を見ると、かなりの人が参加してくださったみたいなのでうれしいです。

B

虐殺問題になりました。コーナーケースに気づかないと永遠に死にます。
見ているぶんには面白かったです。

C

自分が全く歯がたたなかったので、結構な割合で解かれていたので悔しいです。

D

高速化の方法に気づくかどうかが肝だったので、もしかしたらE,Gあたりより後ろに会った方がよかったかもしれませんね。

E

回文に気づきさえすればあとはググれば解けます。
2冪modで出している方が結構多かったのでごめんなさい(数日前に衝突させるテストケースが追加されました)

F

思ったより解かれていなかったです。

G

200点の中では、かなり解きやすい部類だと思います(AtCoderの問題に近い気がします)。
実際、結構な人数が200点の中でGを最初に解いていました。

H

解法を知りません。が、メモをしないと落ちるという情報だけ知っていましたので、そのTLEだけをみて遊んでいました。

I,J

わからない、すごいの二言につきます

最後に

参加してくださった方、ありがとうございました！
自分もH以降が解けたら、またここに追記していきたい…です。

ABC121 C - Energy Drink Collector

問題
提出コード

解法

とにかく値段が安いものから買っていきたいです。
よって、値段と個数の上限をセットにしつつ、値段の昇順でソートすると、あとは個買えるまで貪欲に買っていけば答えを求めることができます。

感想

問題がすごくわかりやすくて解きやすいです。好き。

ABC121 D - XOR World

問題
提出コード

解法

についてxorを取るとき、についてxorを取った結果と、についてxorを取った結果の2つの数字について、改めてxorを取ればよいです。ということで、の区間の数字についてxorを取った結果を求めていく方法を探ります。
これは、それぞれの桁について、xorを取った最終的な結果が1か0かを計算し、最後に加算していけばよいです。
の桁についてみた時(ただし、 とします)、0から順番にビットを見ていくと、これはまでで1回ループをします。
ではビットが0、ではビットが1になっています。
そして、この1回のループでは、ビットが立っている数の個数が個なため、xorをとると0になります。
ということで、まずはをで割った余りをとしたとき、についてのみ考えればよいことがわかります。
あとは、上記の区間についてビットが立っている個数を調べればよく、
以上しかビットが立っていないことから、
からを引いた結果が奇数ならばこの桁の最終的な結果は1、偶数なら0、となります。
そして、の場合ですが、これは4つ数字が増えるごとに1回ループをします。
ということで、4で割った余りが1か2であれば答えは1、そうでなければ0となります。
これを、について操作を行い、それぞれの結果について改めてxorを取れば、答えとなります。

感想

今回は後ろから読んだため、最初に解いた問題となりました。
やりたいことはすぐに浮かんでいたのですが、ボケっとしていたら、引き算をする値や割り算をする値を間違えたり、コーナーケースであるの部分にひっかかったりしました。
ただ、WAを出さずにそこそこの速度で通せたので、満足です。
後ろから解いていたので、提出コードのリンクを間違えてA問題のものにしてしまったのは秘密です