ABC120 D - Decayed Bridges
解法
全ての橋が崩れた状態では、どの島からも別の島へ行くことができません。
よって、不便さは、すなわち
となります。
ということで、ここから逆に橋を組み立てていき、不便さを後ろから求めていくことにします。
今現在の不便さがで、次に
を繋ぐ橋をかけるとします。
既にから
へ行くことができる場合、不便さが減ることはないので、
から
へ行くことができない場合を考えていきます。
自身を含む、
から行くことができる島の個数を
、同様に
から行くことができる島の個数を
とします。
このとき、に橋をかけることで、
に含まれる任意の島から、
に含まれる任意の島へ、新しくいくことができるようになるため、
不便さはだけ減ります。
ということで、が、このときの不便さとなります。
そして、自身を含み、
から行くことができる島の個数は、
へ増えます。
あとはこれを繰り返し計算していけばよいのですが、この自身を含み、
から行くことができる島の個数を計算するのに、自分はUnion-Find木を利用しました。
それぞれのグループの根の部分に、根自身を含み、根からいくことができる島の個数を記録しておくことで、高速に計算することができるようになります。
あとは、順番にシミュレーションをしていくことで、この問題のクエリにこたえることができるようになります。
感想
考察自体は結構スムーズに行けたのですが、実装に時間をかけました。ので、自分の中ではもう少しはやく解くことができた、と思っています。ですが、安定して400点問題をはやときできるようになってきている気がするので、うれしいです！
北大・日立新概念コンピューティングコンテスト2018
ということで、初めてマラソンに参加しました。
この記事では、自分が最終的に行ったことと、時系列順に行ったことの簡単な列挙をしていこうと思います。
問題
リンクはこちら
基本的には同じ問題になります。制約が違う部分だけピックアップすると、
A:
3 <= N <= 50 1 <= K <= 50 0 <= d_i <= N
B:
3 <= N <= 300 1 <= K <= 1000 0 <= d_i <= min(N,6)
C:
3 <= N <= 10 1 <= K <= 2^N 0 <= d_i <= 6
といった具合です。
実際、ランキングを見てもわかるように、この部分が違うだけでかなり得点の取りやすさが異なります。
最終的に行ったこと
提出コード(C)
基本的にはA~Cでやっていることは同じです。ただ、一部分岐条件を問題によって切り替えています。
やることは主に2つです。1つめは、Twitter等で公開されていた、「変数がすべて1」のケースの得点のみを狙い、極限まで項数等を削る方法で、2つめが、厳密解を効率よく作成し、両方のケースで高得点を狙う方法です。
変数がすべて1のケースの得点を狙う方法
こちらは、以下のツイートの方法とほぼ同じです。
https://twitter.com/arimasenu/status/1099583866614931456
手順としては、次の通りです。
定数項および1次の項について、係数をそのまま割り振る
正負の項をまとめられるものについてはまとめる
という項が存在していた場合、(
は係数です)
とで項をまとめることができます(
の場合です、逆でもやることはほぼ同じです)。そして、まとめた後の左側の項は、
という部分が負になることはありえない上、変数すべてが1のケースでこの項が0になるため、消去しても問題ありません。
よって、残ったという項についてのみ今後考慮していけばよいことになります。このようにして、どんどん項数を減らしていきます。
係数が負の項について、以下のように係数を割り振る
という項があったとすると、こんな感じです。
つまりは、定数項に係数×(項数-1)を-1倍したもの、そしてそれぞれの変数に係数をそのまま割り振る、という形です。
この操作を行うことで、全てが1であったときのみちょうど-kぴったりになり、それ以外の場合はそれを下回ることがありません。
係数が正の項について、係数を割り振る
という項があったときに、
の項に、うまく係数を割り振っていきます。この際、それぞれの項ができるだけ0に近づくように割り振りたいので、自分は山登り法を用いて調べることにしました。
まず、それぞれの一次の項に均等に係数を割り振ります。その後、それぞれの係数を移動することにより、よりスコアが高くなるような場所がないかを探していきます。係数が正の項が存在していたら、定数項にまとめる
採点のうちの片方、ランダムケースでの得点を完全に捨てているため、捨てられる項は捨てていきます。負の係数の最大値を調整する
例えば、という項が存在していた場合、新規変数を利用して、
とした方が得点が伸びるパターンがあります。
係数の絶対値の最大値をとし、それを超える係数
に分ける、ということを繰り返していきます(
あとはこれを全ての項に対して行います。ただし、新規変数は共有して問題ないので、の最大値が、新規変数の個数になります。
そして、最もスコアが高くなるように
ということで以上が方法の1つめになります。この方法は、複雑な式、つまり項数が多いものに対して適用します。
厳密解を作成する方法
まず、厳密解を作成する方法はいくつか存在します。
notさんという方のブログを見ていただければ、論文に載っている厳密解の作成方法が書いてあるのでそちらをご覧ください。
おそらく自分の解法はこのブログの一番最初に載っているものが近いかと思います(この論文だけよく知らないのでなんとも言えませんが…違っていたり、そもそもこの方法が世に出回っていたらごめんなさい)。
厳密解の作成方法ですが、次数が0~2の場合はそのまま、そして係数が負の場合は、上のブログに載っている方法を利用します(ただし、すこし手を加えているので、後で説明します)。
係数が正の3次以上の項についての厳密解の作成
まずは、次数が3のものについて考えます。係数は最後にかけるだけでよいので省略します。
という項があったとします。ここに、新規変数
を加えると、次のように表現できます。
それぞれに0と1をあてはめてみると、これが
を表現できていることがわかります。
では、4次以上の場合はどのようにすればよいのでしょうか。
という項が存在した場合、
の部分をまとめて1つの変数
と表現できれば、上の3次のケースに帰着させることができます。
ということで、まずは2次の項を、
と置き換えることができないかを調べればいいことになります(項が増えても、あらたに置き換えた変数と、もう1つの変数に対して同じ方法を適用していけば、最終的に1つの変数になります)
ということで結果は以下のような形になります。
の際に
の中身が0になるから動作するかどうかわからないじゃないか、と思うかもしれませんが、その場合でも
が最適になります。
なぜならば、仮にとすると、元々の項
について考えてみると、
の際に
となり、
の項の係数が加算されてしまいます。現在、係数は正のパターンのみに限定しているので、
とした方が、
の項の係数が加算されずに済むため、
が最適となるからです。
ということで、上の式を利用すると、という変数が、新しく
を表す変数になりました。ので、
という項ではなく、
という項を表現する問題に帰着できます。
これを繰り返し、3次になった時に、先ほどの公式に当てはめれば、厳密にを表現できたことになります。
この方法の良い点は、項数が増えすぎない、という点だと思っています。
例えば、と
が存在した場合、
とやると、2つの項をいっぺんに表現できます。
また、という項と
という項の二つが存在した場合、
まず、の
について、
と変形をしてあげてから、
としてあげることで、を表現できますが、
としてあげると、と
の、
の部分が
一つで表現できます。
それだけでなく、
上の式におけるの部分そのものも、実は
を表す項になっていて、
具体的には、という項と、
という項が存在した場合、
でを表現でき、
でを表現できます。まとめて、
としてあげると、これだけで2つの項を表現してあげることができました。
あとは、どの2次変数に対して新規変数を作成するか、の最適解を探せばよく、今回はこちらは焼きなまし法と山登り法(焼きなまし法の条件がうまくかみ合った問題については焼きなまし法を使いました)で探すことにしました。
係数が負の項についての厳密解の作成
こちらは、基本的には上で紹介したnotさんのブログにも書かれている、論文の方針と同じになります。
という項を表現するには、
とすればよいです。
新規変数を1つ用意し、それぞれの変数と
からなる二次の項にはそのまま
を、そして
のみからなる一次の項には、
を割り振ってあげればよいです。
ここで、が大きい場合、
のみからなる項の係数が大きくなってしまいます。
そこで、という二つの変数を用意し、
という基準を設けて、
が
より大きかった場合に
のように分けてあげることで、得点を伸ばせることがあります。
厳密解でない方法の、負の係数に対する処理とほぼ同じものになります。なので、これも三分探索をして、最もスコアが上がるについて調べてあげます。
その他細かい手法
という項が存在して、
という項を作成したときに、
(ただし
)という項を埋め込むことができます。
としてやると、1つの項のみで、4次の項を1つ作成できたことになるのでお得です。
今回は、焼きなまし法等でじっくり時間を費やしたい(実装が難しくて面倒くさい)ので、一部の項のみ、これを適用しました。具体的には、負の係数がある項の変数と、それらの変数より大きい番号の変数1つからなる正の項のみに絞りました。
具体例を出すと、という項が存在したら、
や
のうちのどれか1つが対象になります。
正の係数に対する負が存在するかどうかは、負の係数の項を辞書順ソートしておくだけで、二分探索で調べることができるので、これなら時間がそこまでかかりません。
ということで、記載漏れがなければこれが自分の解法のすべてになります。
あとは、ランダムケースを捨て、全てが1の場合の得点を稼ぐ方法を項数が多いものに対して、厳密解を作成する方法を項数が少ないものに大して行えばよいです。
ということで、最終的な順位はわかりませんが、15個のテストケースに対する得点は次のようになりました。
感想
今回初参加だったのですが、最初のマラソンで2週間のものに出場するのはやめましょう。
自分は、できるとこまでとことんやる性格(自称)なので、ほぼ2週間、隙あらばマラソンのことを考えていたため、他の作業が何もできませんでした…。毎日夜遅くまで考えていたため、特に得点が伸びない時期は明らかに体調が悪くなり、親や友人に心配されてしまいましたｗ
ただ、その分得点がぐんと伸びたときはとても面白いです。普段の競プロで高難易度を解いたり高パフォーマンスを出すのとは別の気持ちよさがありました。
あとは、競プロとは違って、普段強い方々といい勝負ができる可能性があって楽しかったです(でもやっぱり強い方々はマラソンでも強いのですが…)。
提出欄を見ればわかるように、上位の方々は基本提出回数が少ないので、わずかな思考時間であの点数を出していると考えると、いかにすごいかがわかると思います。
今回のマラソンでだいたいどんな感じかわかったので、次にマラソン出る際は、とりあえず数時間のものに出場してみようと思います…ｗ
ずっと同じことを考えて詰まってしまってもあまりよくないので、思考時間を少なくしてリフレッシュするのも大事ですし、それこそ体調が悪くなってしまっては元も子もありません。このあたりも調整しつつ頑張ってみたいです！(この性格があまり向いていないのでしょうか…ｗ)
追記(おまけ)
#HokudaiHitachiProcon2018というハッシュタグを見ればわかるのですが、嘘を混ぜ込んだ解法がほとんどっぽいですね…！！
それでも、上位勢は論理的な嘘(?)というか、他の出場者とは一味違う実装をしているっぽいので、やはり差がくっきりと出ているように見えます。
RE、WAを吐かずに入賞することを期待して数日間待っていようと思います！
3/19追記
僕頑張った pic.twitter.com/IKhTJcU0vJ
— ツバサ (@emtsu_ba) 2019年3月19日
グッズが届きましたー！うれしいですね
ABC119 D - Lazy Faith
解法
すごく簡単にいうと、それぞれのクエリに対して、解の候補が8通りしかありません。なので、調べればよいです。
今いる地点をとしたときに、
より左側にある寺(神社も同様)のうち、一番近いものを1つみつけてひっぱってきます。右側も同様です。
この操作で、寺が2つ、神社が2つひっぱってくることができました。
あとは、それぞれの寺と神社の組み合わせを試していけばよいです。
寺と神社が同じ側に存在する場合
どちらも
これは、寺と神社が逆側に存在する場合
例えば、寺が左側、神社が右側にある場合です。
これは、まず
(
になります。
あとは、これを使って4箇所の位置を特定し、上の4通りを調べ、一番距離が短かったものを出力、ということをクエリの回数だけ繰り返せば答えとなります。
感想
実装悩んでいる暇があったら書いてしまえ！ということで実装していたら、とてつもないスパゲッティコードができあがりました。もうすこしスピーディかつ綺麗に書きたいものですね。
最初、クエリの問題なので、どうせ前計算かなんかだろう、と思っていたのですが、
考察自体は久々に瞬殺できた気がします。
ABC119 C - Synthetic Kadomatsu
解法
全探索をすればよいです。
Aに使う竹、Bに使う竹、Cに使う竹の3種類にまず分けます。
これは、bitで竹を表現して全探索するとやりやすいかと思います。
ビットの部分集合を列挙する方法はこちらをご覧ください。
さて、その後は、それぞれについてコストを計算します。Aについて計算してみます。
まず、のコストが必要です。
あとは、
を計算して、これらを足し合わせると、Aを作成するのにかかるコストが計算できます。
同様にB,Cについても行えば、その合計値の最小値を探すことで、答えを求めることができます。
感想
bitの部分集合を列挙する方法を探すのに数分かかりました(他の方とのトーク履歴に残っているので、いつもそこから探しています…ｗ)。そして、誤読をしていて、全ての竹を使わないと勘違いしていたり、そもそもバグを埋め込みすぎていたりしたため、先にDに飛びました。
なかなか実装の重いCではないかなと思います…
ABC023 D - 射撃王
解法
最大値の最小値を求めよ、といえば！二分探索です、ということで二分探索をしていきます。
点を達成できるかどうか、を二分探索で調べていきます。
ここでの達成できるか、はぴったりではなく、点以上を達成できるかどうか、になります。最終的に最小値を二分探索で求めていくため、ぴったりの値が最後に残ることになるので、
点以上かどうか調べるだけでよいです。
ということで、点以上かどうかを調べる方法が以下になります。
まず、となる
が存在したら不可能です。
あとは、を超えないような、
番目の得点の最大値になるような秒数
を求めます。
を計算すると、その秒数が求まります。
あとは、この値を昇順でソートしたときに、
となるような
が存在したら不可能、存在しなければ可能になります(
は0-indexedです)。
あとはこれをもとにして二分探索を行うことで、答えを求めることができます。
感想
夏休みぐらいのときに、先輩から「最大値の最小や最小の最大値を求める問題では二分探索がしたくなる」と教わったので、実際にその通りに実行してみたら、サクっと解けました。
加えて、最近の練習会で、半開区間を利用した二分探索の実装方法を教わったので、二分探索に関してはバグなく通すことができました(となるパターンを考慮しきれていなかったのでWA自体は出したのですが…)。
この手の問題をサクサク解けるようになると楽しいです！
ABC023 C - 収集王
解法
まずは行目を選択すると固定して考えてみることにします。
行目を選択した場合にアメが
個得られるとします。
同様に、列目を選択した場合に
個得られるとします。
この時、個のアメを得るには、
を満たすものならばいいように見えるかもしれませんが、実は違います。
にアメが存在していた場合、
および
それぞれにそのアメがカウントされているため、実際は
個である可能性があるからです。
同様に、にアメが存在していた場合で、実際に
を選択して
個得られるパターンというのは、
を計算すると
となります。
しかし、にアメが存在していない場合は、
となるマスが、求めるマスになります。
の種類は
なので、全てを探索するわけにはいきませんが、
となるようなマスの個数を求めるのは、二分探索を活用することで求めることができます。よって、うまいこと工夫をして、最初に述べた2種類のコーナーケースを考慮しつつ、計算ができるようにしたいです。
そこで、以下のようにすればよいことになります。
となるようなマスの個数を求める
を固定したとき、
となるような
の個数がわかればよいです。これは、
を昇順にソートすることで、二分探索を利用すれば
のとなっている
で計算できます。
個のアメの座標
について、
となっているものが存在するかどうかを調べる
存在していたら、上の計算から引いてあげる必要があります。となっているものが存在するかどうかを調べる
存在していたら、上の計算に足してあげる必要があります。
以上の計算をすることで、重複なく、求めたいマスの個数を数え上げることができます。
感想
最初、について二分探索をしたときに、辻褄が合わないマスが出てくることはすぐにわかったのですが、そこをどうするかで悩みました。
このような都合の悪いケースが出てきたときに、他の解法を探すか、そのケースだけうまく辻褄を合わせる方法があるかを調べる2択が発生すると思うのですが、今回ははずれを引きました。
ここら辺の勘というか経験といいますか、どちらについて考えればいいかがわかれば、ぐっと考察時間が短くなるような気はするのですが…
