ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

AOJ 1161 - 覆面算

枝刈り 全探索

問題
提出コード

解法

愚直に見ていきます。
下の桁から順番に文字を決めていきます。
式が成り立っているかどうかを最後にN番目の文字列と比較するとTLEをします(した)が、それぞれの桁についての数字を確定させた時点で、N番目の文字列で対応する桁と比較してしまえば枝刈りをすることができます。
最後に、2桁以上の文字列の最上位の桁が0になっていたりするのを調べればよいです。

感想

実装がとても汚くなってしまった上、バグをたくさん埋め込んでしまったので、もう少し簡潔に書けるようになりたいです...

AOJ 1169 - 最強の呪文

ダイクストラ法

問題
提出コード

解法

それぞれの頂点にたどり着くときに文字数がxになっているような呪文の中では、最強の文字列が常に一意に決まります。
ループをしない場合、文字数は最大でも240文字程度にしかなりません(頂点数が40、辺に与えられた文字列の長さは最長で6なので、全ての頂点を1度ずつ通るような遷移をしても234文字にしかなりません)。
ということで、
dis[i][j] = 頂点iにいる状態で文字数がj文字となるような文字列のうち、辞書順最小のもの

とすると、これはダイクストラ法で求めることができます。
あとは、dis[g][j]に格納されている文字列の中で辞書順最小のものを基本的に選べばよいです。
が、これだとループの判定ができません。
先ほど、ループをしない場合に文字数は最大でも240文字程度、ということがわかりました。つまり、それより多い文字数の文字列で、現状のdis[g][j]にある文字列よりも辞書順で小さい文字列が存在していれば、それはループによって無限に呪文を強くできる、ということになります。1回のループにかかる文字数は先ほどと同様最大で240程度なので、その2倍の500文字程度を調べればよいです。
ということで、dis[g][j]にある文字列の中で辞書順最小のものを調べ、その文字数が240を超えている(もしくはそもそも文字列が存在しない)ならばNOを出力、そうでなければ辞書順最小の文字列が答えになります。

感想

一度頂点数そのままのダイクストラを考え無理だとあきらめた結果、辞書順最小になるということは、基本的に貪欲に辺を選んでいけばよいので、DFSを枝刈りしていけばいいのではないか、ということでだいぶ遠回りをしました。
よくよく考えると、頂点を増やしてグラフを拡張すればよいことに気づき、無事ACできました。高難度でもグラフ拡張系の割とシンプル(?)なダイクストラが出るのですね…

AOJ 1140 - Cleaning Robot

幅優先探索(BFS)

問題
提出コード

解法

基本的にはBFSをしていけばよいです。
dis[i][j][S] = (i,j)にいるときに、掃除済みの汚れたタイルの状態がSになるような掃除の手順の中での最短手順
とします。
汚れたタイルは高々10枚なので、掃除済みかどうかの情報をbitで持っても、1024通り程度にしかなりません。
あとは、現在のマスから4方向それぞれに進み、BFSをしていくことで答えを求めることができます。マス目を一回走査して、汚れたタイルやスタート地点を探す部分が少々面倒ですが、その部分さえ書ければあとは基本的にいつものBFS…です。

感想

初期化とスタート地点の情報の記録をいっぺんに行ったので、バグを埋め込みました。
考察自体はさっとできたので良かったと思います。

AOJ 1611 - ダルマ落とし

問題
提出コード

解法

区間DPをします。
dp[i][j] = 区間 [i,j]の中で落とせるブロックの最大値
とすると、答えはdp[1][n]となります。
まず、dp[i][i] = 0となります。続いて、|w_{i} - w_{i+1}| \leqq 1ならばdp[i][i+1] = 2となります。
では、dp[i][j]を求めていきます。
まず、dp[i+1][j-1] = j - i - 1 (すなわち、区間[i+1,j-1]のブロックをすべて落とせるということです)かつ、|w_{i} - w_{j}| \leqq 1ならば、区間[i,j]のブロックを全て落とせるということになるので、答えはj-i+1となります。
それ以外の場合、[i,j]を適当な2つの区間[i,k],[k+1,j]に分割し、それぞれで落とせるブロックの最大値の和を求め、kについて全探索しながら最大値を求めればいいです。
dp[i][j] = max(dp[i][k]+dp[k+1][j])
ということです。
あとはこのDPを行えば、答えを求めることができます。

感想

i番目のブロックとj番目のブロックをペアで落とすには、[i+1,j-1]の区間のブロックを全て落とす必要がある、ということに気づき、そこからうまく調べる方法が無いか、を探しました。端の2つのブロックを落とさない場合は、適当に2つの区間に分割すれば最適解を求められるだろう、ということで上のようなDPをしました。

AOJ 1163 - カードゲーム

Dinic法(最大流,最小カット) 二部マッチング

問題
提出コード

解法

フローの典型っぽいマッチング問題です。
始点、終点と、赤青のカードそれぞれを表す頂点を用意し、始点→赤の頂点、青の頂点→終点に重み1の辺を張っておきます。
そして、任意の赤と青のカードのペアについて、取り除くことができるものについては、そのカードを表す赤の頂点から、青の頂点へ重み1の辺を張ります。
あとは、始点から終点への最大流を求めることができれば、答えとなります。

qiita.com


感想

最初変なDPを考えていたのですが、よくよく考えるとマッチング問題だなぁ、と思ったので上のけんちょんさんのサイトを思い出しました。
けんちょんさんは偉大です…

AOJ 1162 - 離散的速度

ダイクストラ法

問題
提出コード

解法

dist[i][j][k] = 都市jから都市iに速度kで移動してきたときにかかる時間の最小値
とすると、現在の都市、1つ前の都市、現在の速度、現在経過した時間をひとまとめにしつつダイクストラをすればこの配列を埋めることができます。
キューから取り出した要素に対して、現在の都市から行くことができる別の都市について、3つの速度パターン(現在の速度に[tex-1,0,1]を加えたもの)を当てはめつつ、経過時間を計算していきます。
答えは、dist[g][j][1]の最小値になります。何か大きな値で初期化をしておき、dist[g][j][1]がどこも更新されていなければ、答えはunreachableとなります。

感想

はじめ、dist[i][k]で計算していたため、ある閉路について、時計回りに行くパターンと反時計回りに行くパターンを両方考慮しきれていませんでした。
こういうパターンに素早く気づくことも大切そうです。

ICPC 2019 国内予選 参加記

番外編 ICPC

ICPCの国内予選に参加しました。模擬国内はこちら

名前の由来は、チームメンバーに共通点がほとんどなかったことです(1999年生まれということは一致していましたが...)

目次

前日まで

模擬国内で(コーチに煽られるぐらいのレベルだったため)危機感を持ったので、1日最低1ACすることにしました。チームメンバーのスラックのチャンネルをひたすら荒らす人になりました。

自分が解けない問題は、メンバー2人をメンションで召喚し(最悪)3人で考察したりもしました。
結果、昨年卒業した先輩の精進ポイントをギリギリで上回ることに成功しました。

当日

自分は1,2限が存在していたので4時間しか眠れませんでした。朝6時ぐらいにスラックで呼びかけると、夜更かしをしているmi_tesseract君が反応をしてくれたので雑談をしていました(9時前ぐらいまでmi君は起きていました)。

その後、3限があるTsuzu君を待つため、同級生と猫のぬいぐるみで遊んだりしていました(猫でおままごととか蟻本でおままごととか言っていたのですが今思うとわけがわかりません)。

この時に事件は起きました。
朝9時直前あたりで寝る、と最後に言い残したmi_tesseract君からの連絡が途絶えたのです。

結局14:20分ごろに連絡が来ました(本人曰く想定通りらしいです)。よかった。

コンテスト本番

予定通り、僕がAを、Tsuzu君がBを、mi_tesseract君がCを読みます。
自分はそのまま問題を通しました。全体で3番目だったらしいです。

その後、Tsuzu君がBをすぐに実装できるとのことだったのでPCを明け渡し、自分はCの考察を聞きに行きました。
そして、考察を聞いた感じ、「これは探索するだけ」となったので、Tsuzu君のBのデバッグの隙を伺いつつ実装を始めます(直後にBはACしました)。
Tsuzu君とmi_tesseract君はDの考察を始めます。…が、自分のCの考察漏れがあったことに気づく＋とんでもないバグを埋め込んだ(答えを常に定数の-1で出力してるのに気づきませんでした)ので、修正に時間がかかってしまいました。計算量重めのコードだったので、修正後にわくわくしながら待機→WA(は？)。
結局、このままではダメそうとのことだったので、mi_tesseract君に入力以外の全て、つまりほぼ1から書き直してもらうことになりました。
その間に、Tsuzu君が1人でDの考察を終えていたので、その正当性を確認し(僕はほぼ聞いてうなずいていただけ)、二人がバグ探し等PCを交互に使いながら実装をすることに。
結果、どちらもほぼ同タイミング(開始から1:40ほど経過)でACしました。

Bまでの時点では順位が怪しかったので3人で「はやく打ち上げだけ参加して帰りたい…」などと言っていたのですが、このタイミングで初めて順位表を見てみると、なんと19位。何かの夢かと思いました。

その後、EがやるだけっぽいのでTsuzu君に完全に投げ、僕とmi_tesseract君でFの考察をしていました。
が、Fを解ける気がせず、Tsuzu君の後ろで踊ったり、2人で雑談をしてTsuzu君を笑わせる係をしていました(??)。
結果、実装は終わったのですが実行してみるとそもそも入力のタイミングからバグっていそうということがわかり、直後にコンテストが終了しました。

結果

4完で27位、特に何もなければ無事予選突破です。

C問題のバグが無ければ、同大学の1位であるPICOPICOPONチームに勝てるかもしれなかった、ということに気づき、ひたすら謝っていました(そうでなくても今回はA以外何もしていないのでただのお荷物です)。


コンテスト後

恒例？の打ち上げを行いました。

ｼﾝﾔｶﾄｰさんをはじめ、昨年卒業された先輩方も打ち上げに駆けつけてくださり、終電ギリギリまでいろいろなトークで盛り上がっていました。

最後に

とりあえず、このチームでまたコンテストに出られそうなので、とてもうれしいです。
今回は完全におんぶにだっこ(コーチにも同級生にも笑われました...)だったので、アジアか何かでこの恩を返したいとおもいます。
とりあえずこの夏はまた精進したいと思います(まずはAtCoderで黄色になりたいですね)。
まずUS配列のキーボードを買わないと…

おまけ