The 2017 ACM-ICPC Asia Yangon Regional Programming Contest 参加記
はじめに
kazuma, nakano, 僕の3人でチーム KazumaDragon としてミャンマーの Regional に参加しました．
ミャンマーで開催されるのが今年が2回目とのことで，まだ記録が少ないと思うので参加記を書こうと思います．
前半はプラクティスとコンテストについて，後半は旅程の全てを（大体）時系列順に箇条書しています．
プラクティス
- 開始前にスコアボードを見ると5問もある．なんか雑に開始した気がする．
- Aは線形方程式，Bは式をパースして場合分けを丁寧に頑張るだけ，CDは（僕は）読んでない，Eは基本貪欲に取っていく枝狩り探索？みたいな出題．Bは途中で問題の修正が入った．
- 意外とまともだなあ．去年も見た目はまともらしかったしね．
- とりあえず環境を確認する．
- IntelliJ，NetBeans，Eclipseなどがある．Java勢に優しい．
- 普通のテキストエディタもターミナルが一緒についてるそこそこ使えるやつがあったのでそれで書くことにした．
- というかVimがあるって書いてあったのに vim を叩いたら無いって怒られた．困るよ〜．
- テンプレートを書いて，WAを出すコードを投げる．CE．は？
- C++11 すら使えないらしい．環境はいいんだからオプションちゃんとつけてほしい．多分最適化オプションもついてないので pragma optimize しましょう！
- 修正して出す．TLE．なんでやねん（これは僕が提出先を間違えていただけで向こうは悪くない
- 気づいて再提出．ちゃんとWAが来る．良し．
- REを出すコードを投げる．REがちゃんと返ってくる．やったぜ．
- TLE の限界やスタックサイズの確認もする．予想よりまともで安心．手元でちゃんと動くなら大丈夫そう．
- そろそろAC1個だけ貰いに行くかということで，Aがやるだけなのでちゃんと読む．
- 行列と列ベクトルのサイズが早速書いてない．Clarの練習用にわざと書いてないんだろうなと解釈する（ほんまか？
- Clarを投げたら予想通りのサイズで安心．書く．バグる．なんとかAC．
- 色々あってこの時点で終了まで20分ぐらい？まあACいらんし適当に過ごそうと考える．
- 終了20分前ぐらいにスクリーンと照明が急に音を立てて落ちる．草．なんで落ちたのか未だに不明．
- 終了直前にまた照明が音とともに落ちる．なんでや．
- ちなみに手元のPCは落ちないので安心してください（？）
- ここで終了．一応結果を伝えると，E問題がめっちゃ通されてました．
- なんだ問題自体は普通じゃん．難易度もPracticeの割には高かったように思う．
- 難しかったねーと適当に感想戦をする．
関係ないけど，うちの大学の実験室よりはるかにPCのスペックが良かった．弊大学は†悔い改めて†
本番
- カウントダウンとともに開始．パスワードを入力してログインするところから始まる．
- 僕がテンプレートとか用意する間に他の2人に問題を読んでもらう．
- Practice で作ったファイルが全部残ってて草．これええんか？
- なんかGがセグツリで高速化する実家DPらしいので書く．初期化部分をミスってバグったがAC．
- 次にDが素数と合成数列挙するだけと聞いたので書く．WA．やべえ．
- flush のせいかなと思い flush して提出するもWA（めっちゃもったいない）．うーん？
- コード読んでる限り変なところは無いので後回しにしてしまう．（なんで問題文を読み返さなかったのか）
- （他の問題概要を聞いていたが順番を覚えていない．確か I を聞いた気がする…サンプル合わなくてIの誤読に気がついた？だったかな）
- Aを読んだらやるだけだが実装どうするか迷ってしまう．他の問題考えながらということで後に回す（これも微妙な選択かなあ
- Dは少し誤読していたらしい．文字列が与えられるんだけど，space を含むらしく getline が必要とのこと．Practiceでもそうだったけどやたら getline 書かされるなあ．直してAC．
- Fが簡単らしいので概要を聞いて書く．なんか僕の理解が甘かったらしく変なコードを書きかけてしまい，kazuma が見かねて代わりに書く．AC．ごめんなさい．
- （ここから1時間ぐらい辛かった気がするがなんで辛かったのか覚えていない）
- Cの概要を聞いたが制約がヤバすぎる．テストケースの数 10^5 ってなんやねん．クエリじゃないんだぞ．
- しかも各テストケースで 10^10 ぐらいの出力が要求されるらしい．えぇ…．流石に Clar を投げるがよくわからない返答が返ってきて，なんかよくわからないため後回しにすることにした（これが結果的に一番もったいなかった）
- JとLは見た目がやばくてみんな敬遠していた．（結果的には正しかった
- Bを読んだので kazuma に伝えたら実家なのでかけるとのこと．僕が書くより早そうだったため任せてしまう．
- union find木だけ僕が書いたんだけど，結構バグらせてしまった（大反省）．それ以外もちょっとだけバグって時間をロスするが，一応ACする．
- 裏で簡単だと聞いていた H の紙コーディングをしていたため，その後すぐにACする．
- nakano が I を頑張って書いていた．Iには全く関わっていないので，裏でAを紙コーディングする．
- 紙コーディングが終わって書く．ちょっとバグったけどすぐ直してAC．
- この時点で10位ぐらい？初アジアにしてはいいんではということで少し安心する．
- Eの概要を聞いて真面目に考える．3次元空間上の点を，最小限の直線で全て貫くという問題．
- この間 kazuma は K問題を，nakano は I （と K）を考察していた．
- 点の数 n <= 100 なためフローが生えかけたが無理なので（それはそう）棄却する．
- こんなんNP困難やろという気持ちになる．適当に枝狩りしかないが n <= 100 はやばそうなので一旦逃げる．
- kazuma が E をちょっと考えて最小費用流でいける（僕が棄却したのと全く同じやつ）という意見をくれた．なぜが行けると勘違いして（は？？？）書いてしまう．
- ライブラリ移すパートでバグらせる．なんとか直してサンプルチェック．合わない．当たり前や．
- これ無理やんけとなったので，あとに回す．
- Kをちょっと聞いたところ，10^8 のオーダーでエラトステネスっぽいことをするらしい．まあ無理だよね
- I はバグっているらしいし，ここらへんかなり辛くなってくる．解ける問題が無い．（この時僕の頭にC問題の文字はなかった
- kazuma がエスパーする．「10^8 じゃなくて 10^7 で通るんでは？ｗ」とか言って投げる．
- 僕はさすがに無理だと思っていたが AC する．流石に草．
- もはや書いてある制約が何も信じられない．そしてここで僕がエスパーする．
- 僕「Eは n <= 100 じゃなくて n <= 10 とかやろｗ」
- kazuma は流石にありえないやろ，と言って嫌そうな顔をしていたが，僕の独断により n <= 20 ぐらいの bitDP 解をちゃっと書く．投げる．AC．
- もう顔中草まみれや．
- とりあえず nakano の I を祈る．めっちゃバグっていたが AC した．さすがプロ．
- Iが通った時点で9完，残り15分ぐらいだったので，もう書けないかなとなって感想戦をしていた．
- 本番の問題よりPracticeの方が難しくない？みたいなことを話していた気がする（これは嘘で，不正ACをしているため
- なんか終了5分前ぐらいで謎の封筒を渡されたり，写真を取られまくったりする．順位表が凍結されている意味とは…
- 終了．終わった直後は満足していた．
終わった後に気がついたんですが，問題文が書いてある前に注意書きみたいなページがあって，そこにジャッジが投げうる結果がすべて丁寧に書かれていた．こういうのはPracticeで書いてくれたほうがうれしいですね．
本番の問題概要
自分で読んだのは結局ABだけなので雑にまとめます．本文は公式ページから読めるけどね．
- A問題．完全二分木をトーナメント表みたいな形式で出力する．表の深さ N <= 13．
- 再帰でいい感じに書いた．出力が多いので fast IO を使うと安心っぽい．
- B問題．友人関係と敵対関係，および推移律的なルール群が与えられるので，各クエリで与えられた2人の関係を答える．関係の数は 50個以下．
- 冷静に考えると2部グラフ判定するだけ．UFで適当に．サイズが 10^5 でも解ける．想定はクエリごとにDFSで探索とかかな．
- C問題．グリッド状のタイルを，あるルールに従って色塗りしていく．各時刻で新たに塗られるマスを出力していく．タイルの幅と高さはそれぞれ 10^5 ，テストケースの数は 10^5個
- 制約がヤバイ問題その1．実装はやるだけですが若干めんどくさいか．Clarを投げるのは最低限必要で，あとはStandingsをみて解ける問題か確認するのが大切．実際うちのチーム以外の上位陣は通しているしね．
- D問題．文字列が与えられるので，各文字を 8bit 整数とみて01ビット列に直す．その後はそれに合わせて合成数と素数を出力するだけ．入力サイズはめっちゃ小さい．
- E問題．3次元上にある点をできるだけ少ない点で貫くときの，最小の直線の数を求める．点の数 n <= 100
- 制約がやばい問題2．多分枝刈りが想定だが，エスパー力も大切（いいえ）．assert(n <= 26) してREせず通ったため，書かれている制約の最大値が本当に入力に存在するとは限らないらしい．
- F問題．2つの商品があって，それぞれコストと利益が「問題分に」与えられているので，あるコスト以下で利益を最大化する．
- 入力サイズが小さいので全通り試すと通ります．問題分が無駄に長かった．
- G問題．数列に含まれる単調非減少列の中で，総和が最大のものを求める． N <= 10^5
- 典型すぎる．セグツリで高速化するDPで．
- H問題．シード値と b が与えられ，それらから数列 a_n を作っていく．i < j で a_i = a_j となるタイミングを検出せよ．ただし，a_{i+1} = (a_i を b 進数で表したときの各桁の平方和を10進数で表したもの) とする．b <= 17．
- bが小さいので愚直に1つずつ計算していくだけですぐ衝突する．
- I問題．一直線上に N 地点 Hyperloop がある．各 Hyperloop 間の距離は d_i である．i 番目の Hyperloop では，ある時間（任意に選べる．0でも良い）の間加速度 a_i で加速できる（加速中はその場にとどまっているみたいな感じです）．このとき，初期地点から最終地点まで行くためにかかる最短の時間を求めよ．テストケース T <= 90, N <= 10^3, a_i <= 10^4, d_i <= 10^4
- まともに難しい問題1．O(N^2) のDPで解いたらしい．O(N^2)のDPにする前は，嘘貪欲とか，頑張って場合分けするとかやっていてバグったらしい．このセットの中だと一番解きがいがある問題っぽい？
- J問題．文字列 $S = S_0S_1 \ldots S_{N-1}$ のハッシュを $H(S) = \sum b^{n-i-1} \times D(S_i) \mod m $ によって定める．ただし $D(a) = 0, D(b) = 1, \ldots, D(z) = 25$である．ここで，h, b, m, n が与えられる．長さ n の文字列で，ハッシュ値が h となるものは何通りあるか求めよ．
- まともに難しい問題2．本番はどのチームも解いていない．噂によれば FFT とダブリングで解く？みたいなことを聞いた気がする．
- K問題．[l, r] に含まれる自然数で，約数の総和が 3 で割り切れるものの個数を求める．1 <= l <= r <= 10^8，テストケースの数は20個．
- 制約がヤバイ問題その3．制約を信じるなら線形で前処理して各テストケースO(1)しかないがわからない．エラトステネスににた感じの処理でオーダーがO(nloglogn)ぐらいには落とせたらしいが，それでもやばいね．
- L問題．正五角形に同じサイズの正方形を（問題文の図に書いてある詰め方で）8個詰めるとき，詰め込める最大の正方形の大きさを求める，みたいな問題．
- 本番では避けていた（というかほとんど読んでない．Standingsみても手を付けているチームは少なかった）．二分探索で頑張るか，手計算で頑張るか．めんどくさそう．
結果
A,B,D,E,F,G,H,I,Kの9完遅解きで4位でした．ちなみにI問題のFA＆唯一のAC．150ドルGET．日本人のスポンサー（？）の方と一緒に写真を撮った．
1位も9完だったので，僕がCを書いていれば1位だったと思うとチームのみんなには申し訳ないと思っていた．
D の誤読がなければ確実に3位には入れたため，結果を見たときは嬉しさと同時に悔しさが残る…．まあ結果論だし，今の結果に納得はしています．
旅程まとめ
7日（前々日）
- 飛行機は8日朝だが，家から間に合わないことに気がつく．
- 空港近くの友人宅に泊めてもらう．夜ふかしした．
8日（前日）
- 7時ぐらいに空港着．
- 受付でWAが生える．向こうのミスっぽいが焦る．
- なんかいい感じにいけるらしいのでセーフ．幸先悪いなあ．（こういうことがあるので早めに空港には行きましょう
- 出国時に荷物検査で引っかかる．筆箱にカッターナイフがあるのを忘れていた．
- とりあえず北京につく．乗り継ぎが8時間ぐらいあった．（乗り継ぎが長いとつらいので，飛行機のチケットは早めに取りましょうね．
- ミャンマーには結局24時ぐらいについた．ICPCの人たちが出迎えてくれた．
- タクシーを捕まえてくれたんだけど，早速車の治安が悪い．空港前がすでにカオス．
- ホテル着．さすがにすぐに寝る．
- 結局この日は友人宅での朝ごはんと，機内食 x 2 しか食べていない．
9日（Practice当日）
- 6時半おき．早すぎるからもっと遅くしてほしい．
- ホテルにバスが迎えに来てくれる．
- 相変わらず車の治安がアレ．10秒に一回はクラクションがなる．
- 大学着．大学内に普通に犬が徘徊していて笑う．
- Practiceを適当にやる（内容は上に書きました）
- なんか向こうが観光の手配もしてくれるらしい．シュエダゴン・パゴダに案内される．
- でかい．修行僧がタブレットでなんかしていて，すごいなあとなる（語彙力が無い
- 外の露店の揚げ物を買って食べる(2000キャットぐらい．日本円換算はだいたい10分の1すれば良いです．つまり200円．）美味しいが油が強かった．（胸焼けした
- 果物とかはお腹をこわす可能性があるらしいので，怖い人はやめておくのがよいです．
- ホテルに帰る．近くに外国人向けの店があったのでそこで晩御飯（14000キャット？）．さすがに美味しかった．
- チームで若干明日の戦略を考えて，早めに寝る．
10日（コンテスト本番）
- 6時15分起き．なんでこんなに早いんだ．
- 同じホテルの他の人々がこない．競プロerは万国共通で集合が下手らしい（要出典）．20分ぐらい遅れる．
- 2件目のホテルでも人々が集合時間にこない．頼むよ〜．
- 予定より大幅に遅れて大学につくとコーヒーとパンが配られる．おいしいパンだった．
- コンテスト開始時間がガバガバになっているのに何のアナウンスもない．大丈夫か？
- 待っていたら唐突に大声でカウントダウンが始まる．カウントダウン開始が何の前触れもなく3秒前に行われるってどうなんだ．
- コンテストの内容は上に書いた．
- コンテスト終了後は大学でお昼ご飯が配られる．まあまあ美味しかった．
- その後は観光に連れて行ってくれる．Taukkyan War Cemetery という共同墓地とショッピングモール．
- 太平洋戦争時の連合国軍戦没者の共同墓地っぽい？
- 墓地なのに沢山の人がにこやかに写真を取っていて少し驚く．
- ショッピングモールで人権を得る（SIMを買う）
- ショッピングモール付近は車の治安がやばすぎて，もはや僕達を回収してくれるバスがどこにいるのかわからない．
- 結局出発が30分ぐらい遅れる．しかも一部の人の回収に失敗していて草．そりゃそうなるわ．
- 閉会式の会場につく．めっちゃいいホテル．
- 席が余っていなくて，VIP席に案内されてしまう．しかも主催者テーブルっぽい．
- 偉い人の話を聞いてリザルトを見る．結構盛り上がっていた．
- その後は突然POPなミュージックとともに前で踊りが始まる．VIP席（舞台に近い）にいたせいか巻き込まれて踊ることになった．
- ビュッフェ形式のはずなんだけど，VIP席に座っているのでホテルの人が料理を運んできてくれる．最高に運がいい．
- 当然料理は美味しかった．
- 主催者の人とちょっと話をする．日本の東京は苦手らしい（人が多いため）．わかるなあ．
- あとは適当に写真を取ったりしてホテルに帰る．早起きする必要がないので適当にすごす．
11日
- 今日は何もないので飛行機の時間までブラブラすることに．
- ホテルまでICPCの人たちが迎え（タクシー）に来てくれるらしいので，チェックアウトした後またホテルに戻る必要があった．
- 13時ぐらいにチェックアウト．荷物を預けてダウンタウンの方へ．
- もちろんタクシーを捕まえる．8000キャットで乗せてくれた．
- 前日に，お土産を買う店をコーチが聞いてくれたらしいが，月曜日が定休日らしい．運が悪い．
- 中心部に近づくと，車の量が激しくなってきた．
- 日本人もよく行くという，Monsoon という店でご飯を食べる．チキンカレー(6800キャット) とお酒(5000キャット)を食べた．美味しい．
- その後は適当にぶらつく．
- しかし暑すぎて辛くなってきたため，適当なカフェに入ってスムージー(2500キャット)を頼んで良い時間まで粘る
- その後はスーパーを見つけてお土産を買って帰る．大体 3000 キャットぐらい使った．
- 変なオジサンに「オンナノコどう？」って聞かれた．（いら）ないです．
- 晩御飯は一風堂を見つけてしまったので吸引される．美味しい．
- 一部日本語で接客していた．「イラッシャイマセ」「麺カタメ」「カエダマ」など．
- タクシーを捕まえてホテルまで送ってもらう．1つ目のタクシーはなぜか理由も話さず断られてしまったらしいが，2つ目のタクシーは5000キャットで乗せてくれた．
- 飛行機にのって爆睡する（機内食を逃す
AOJ 0537 Bingo
解説
言い換えると
$1 \leq a_1 < a_2 < \ldots < a_n \leq M $
$a_1 + a_2 + \ldots + a_n = S$
をみたす $a_n$ の作り方を求める問題で，O(NMS) の解法はすぐわかると思いますが，実は O(NS) で解けます．
分割数のイメージでやるとよいです．DPでやることには変わりません．
dp[i][j] := i 個の異なる数（M以下の数）で，総和を j にする組み合わせ
とすると，遷移は
dp[i][j] = dp[i - 1][j - i] + dp[i][j - i] - dp[i - 1][j - M - 1]
となります．
第1項は，すでに出来ている i - 1個のそれぞれに 1 を加算し，i 番目に 1 を付け加えるという操作を表します．
第２項は，すでに出来ている i 個の数のそれぞれに 1 を加算してできるという意味を表します．
最後の項は，1を加算したことで M を超えるような場合の数を取り除くためのものです．dp[i][j] で M を超えるとしたら，遷移の仕方からその値は M + 1 で，かつその1つだけです．そのような場合の数は，他の i - 1 個の総和が j - M - 1 で，かつ M を超えるものが無い場合なので，dp[i - 1][j - M - 1] に対応します．
以上で O(NS) で解けました．
ソースコード
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; using vi = vector<int>; using ll = long long; constexpr int mod = 1e9 + 7; int main() { int N, M, S; while(cin >> N >> M >> S, N) { vector<vector<int>> dp(N * N + 1, vector<int>(S + 1)); dp[0][0] = 1; for(int i = 1; i <= N * N; ++i) { for(int j = 0; j <= S; ++j) { if(i <= j) { dp[i][j] += dp[i][j - i] + dp[i - 1][j - i]; } if(j - M - 1 >= 0) { dp[i][j] -= dp[i - 1][j - M - 1]; } dp[i][j] = (dp[i][j] + mod) % mod; } } cout << dp[N * N][S] << endl; } }
感想
制約を N <= 100, S <= 10^5, M <= 10^5 にするだけで解けなくなる人が出てきそう．
AOJ 1281 The Morning after Halloween
解法
この問題はやるだけなんですが，TLEとMLEをうまく回避するのが大切な問題です．定数倍遅くなりそうな部分はできるだけ排除していく必要があります．
基本BFSをやっていくだけなのですが，最短距離を short で持つようにするとMLEが防げます．
遷移する部分は，とりあえず3つ文字があると仮定した 5^3 のループ（動かない＋4方向に動く）を書いて，適宜つじつまを合わせる実装が楽だと思います．
移動先が壁かどうかの判定を，面倒だからと一番深いループの位置でやるとTLEするので，各文字の遷移先を決めるループごとに枝刈りしないといけません．
あとは変なことを書かなければぎりぎり通ると思います（白目）．
ソースコード
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; constexpr int dx[5] = {0, 0, 1, 0, -1}; constexpr int dy[5] = {0, 1, 0, -1, 0}; short d[256][256][256]; void init() { for(int i = 0; i < 256; ++i) { for(int j = 0; j < 256; ++j) { for(int k = 0; k < 256; ++k) { d[i][j][k] = 10000; } } } } bool move_check(int prev1, int to1, int prev2, int to2) { return to1 != to2 && (prev1 != to2 || prev2 != to1); } int main() { int w, h, n; while(cin >> w >> h >> n, n) { init(); vector<string> c(h); vector<pii> cs1, cs2; cin.ignore(1000, '\n'); for(int i = 0; i < h; ++i) { getline(cin, c[i]); for(int j = 0; j < w; ++j) { if('a' <= c[i][j] && c[i][j] <= 'z') { cs1.emplace_back(c[i][j], i * w + j); } if('A' <= c[i][j] && c[i][j] <= 'Z') { cs2.emplace_back(c[i][j], i * w + j); } } } sort(begin(cs1), end(cs1)); sort(begin(cs2), end(cs2)); array<int, 3> s = {255, 255, 255}, g = {255, 255, 255}; for(int i = 0; i < n; ++i) { s[i] = cs1[i].second; g[i] = cs2[i].second; } queue<pair<array<int, 3>, short>> que; d[s[0]][s[1]][s[2]] = 0; que.emplace(s, 0); int res = 0; while(!que.empty()) { auto now = que.front().first; auto cost = que.front().second; que.pop(); if(now == g) { res = cost; break; } for(int i = 0; i < 5; ++i) { int ny0 = now[0] / w + dy[i], nx0 = (now[0] % w) + dx[i]; if(c[ny0][nx0] == '#') { continue; } for(int j = 0; j < 5; ++j) { int ny1 = now[1] / w + dy[j], nx1 = (now[1] % w) + dx[j]; if(n >= 2 && c[ny1][nx1] == '#') { continue; } for(int k = 0; k < 5; ++k) { int ny2 = now[2] / w + dy[k], nx2 = (now[2] % w) + dx[k]; if(n == 3 && c[ny2][nx2] == '#') { continue; } array<int, 3> nxt = {ny0 * w + nx0, (n >= 2 ? ny1 * w + nx1 : 255), (n == 3 ? ny2 * w + nx2 : 255)}; bool move_ok = true; for(int l = 0; n != 1 && l < n; ++l) { move_ok &= move_check(now[l], nxt[l], now[(l + 1) % n], nxt[(l + 1) % n]); } if(move_ok && d[nxt[0]][nxt[1]][nxt[2]] == 10000) { d[nxt[0]][nxt[1]][nxt[2]] = cost + 1; que.emplace(nxt, cost + 1); } } } } } cout << res << endl; } }
感想
まあ，最初サボりすぎてTLE食らったんですけどね．実装はきれいに書けたほうだと思う．（速度が早いとは言ってない）
ちなみに 5.50 s / 8.00 s です．あぶねえな．
ケースによるけど，n が小さいならループを回さないようにしたほうが早くはなると思う．でも全部 n == 3 だと意味ないからそういうふうには書かなかった．
A* とか 両側探索だと多少早いのかな？
AOJ 1238 True Liars
解法
人をノードと見て，x y a を辺と考えると良い．ある人を仮に divine あるいは delivish と定めると，その人と関係のある人間の性質が一意に定まる．
よって，関係のあるグループについて2通りを試して，その結果で dp をすればよい．
・dp[i][j][k] := i 番目のグループまで見て，divine が j 人であり，delivish が k 人である時の，直前のグループの状態
とする．直前のグループの状態は，代表の id と，その人の性質，そしてそのグループの分配の仕方を表す．
同じ dp[i][j][k] に到達する状態が複数あった場合，以降その状態とそこから遷移できるすべての状態を ambiguous に設定してしまう．
最後に dp.back()[p1][p2] が有効なら復元していく．
ソースコード
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; struct edge { int to; bool yes; }; using edges = vector<edge>; using graph = vector<edges>; // (divine, devilish) pii dfs(graph const& g, int v, bool divine, vector<bool>& checked) { auto res = make_pair((int)divine, (int)!divine); checked[v] = true; for(auto& e : g[v]) { if(checked[e.to]) { continue; } bool next_state = (divine && e.yes || !divine && !e.yes); auto t = dfs(g, e.to, next_state, checked); res.first += t.first; res.second += t.second; } return res; } void determine(graph const& g, int v, bool divine, vector<int>& res) { res[v] = divine; for(auto& e : g[v]) { if(res[e.to] != -1) { continue; } bool next_state = (divine && e.yes || !divine && !e.yes); determine(g, e.to, next_state, res); } } struct data { int person_id; bool divine; pii each_num; // (divine, devilish) data() : person_id(-1), divine(false), each_num(make_pair(0, 0)) {} }; int main() { int n, p1, p2; while(cin >> n >> p1 >> p2, n || p1 || p2) { graph g(p1 + p2); if(n == 0) { if(p2 == 0) { for(int i = 1; i <= p1 + p2; ++i) { cout << i << endl; } } else if(p1 != 0) { cout << "no" << endl; continue; } cout << "end" << endl; continue; } for(int i = 0; i < n; ++i) { int x, y; string a; cin >> x >> y >> a; g[x - 1].push_back(edge{y - 1, a == "yes"}); g[y - 1].push_back(edge{x - 1, a == "yes"}); } vector<vector<vector<data>>> dp(1, vector<vector<data>>(p1 + 1, vector<data>(p2 + 1))); dp[0][0][0].person_id = 0; vector<bool> checked(p1 + p2); for(int i = 0; i < p1 + p2; ++i) { auto now = dp.back(); vector<vector<data>> nxt(p1 + 1, vector<data>(p2 + 1)); if(!checked[i]) { for(int b = 0; b <= 1; ++b) { data d; d.person_id = i; d.divine = b; auto checked2 = checked; d.each_num = dfs(g, i, b, checked); if(b == 0) { checked = checked2; // restore } for(int j = 0; j <= p1; ++j) { for(int k = 0; k <= p2; ++k) { if(now[j][k].person_id == -1) { continue; } int nj = j + d.each_num.first, nk = k + d.each_num.second; if(nj > p1 || nk > p2 || nxt[nj][nk].person_id == -2) { continue; } if(nxt[nj][nk].person_id >= 0 || now[j][k].person_id == -2) { // ambiguous nxt[nj][nk].person_id = -2; continue; } nxt[nj][nk] = d; } } } dp.push_back(move(nxt)); } } auto now = dp.back()[p1][p2]; if(now.person_id < 0) { cout << "no" << endl; } else { vector<int> res(p1 + p2, -1); int P1 = p1, P2 = p2; for(int i = dp.size() - 1; i > 0; --i) { auto d = dp[i][P1][P2]; determine(g, d.person_id, d.divine, res); P1 -= d.each_num.first; P2 -= d.each_num.second; } for(int i = 0; i < p1 + p2; ++i) { if(res[i] == 1) { cout << i + 1 << endl; } } cout << "end" << endl; } } }
感想
まあすぐわかると思うんですが，実装方針が良くないです．特に，dp[i][j][k] としているのが悪くて，j の値がわかれば k の値は自動的に決まるため，片方を保つ必要はありません．実装方針どころか，計算量が変わるので非常にまずいです．（今回は十分間に合いますけどね．）
また，ambiguous な状態の表現は，そうなる遷移の数を dp の値として持つことで自然に表現できるため，変な負の値を割り当てずにそうすべきだったかな．
あとは data 構造体で持つのではなく，複数の配列に分けて持ったほうがきれいかもしれない．これは好みかな？
AOJ 2731 Shifting a Matrix
解説
シフト操作 F について，F[i][j] := i 行目 j 列目の要素がどこに移るか と表現すれば，あとはこれらを結合するだけです．操作 F, G に対し，これらをこの順に結合した操作 H は H[i][j] = F[G[i][j].first][G[i][j].second] と計算できます．
操作回数が大きいので，行列のシフト操作は繰り返し二乗法っぽく計算します．
変に解説するよりコードを読んでもらったほうが早いと思います．
ソースコード
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; int N; vector<vector<pii>> make_initial() { vector<vector<pii>> res(N, vector<pii>(N)); for(int i = 0; i < N; ++i) { for(int j = 0; j < N; ++j) { res[i][j] = make_pair(i, j); } } return res; } vector<vector<pii>> eval(vector<vector<pii>> const& A, vector<vector<pii>> const& x) { auto res = A; for(int i = 0; i < N; ++i) { for(int j = 0; j < N; ++j) { res[i][j] = A[x[i][j].first][x[i][j].second]; } } return res; } vector<vector<pii>> sequence(string const& s, int& p); vector<vector<pii>> repetition(string const& s, int& p); vector<vector<pii>> operation(string const& s, int& p); int number(string const& s, int& p); vector<vector<pii>> sequence(string const& s, int& p) { auto res = make_initial(); while(p < s.size() && (s[p] == '(' || isalpha(s[p]))) { vector<vector<pii>> f; if(s[p] == '(') { f = repetition(s, p); } else if(isalpha(s[p])) { f = operation(s, p); } else { cout << "error pos: " << p << endl; assert(false); // error } res = eval(res, f); } return res; } vector<vector<pii>> repetition(string const& s, int& p) { auto x = sequence(s, ++p); ++p; assert(isdigit(s[p])); int n = number(s, p); auto res = make_initial(); while(n > 0) { if(n & 1) { res = eval(res, x); } x = eval(x, x); n >>= 1; } return res; } vector<vector<pii>> operation(string const& s, int& p) { auto res = make_initial(); char op = s[p++]; int i = number(s, p) - 1; if(op == 'L') { for(int j = 0; j < N; ++j) { res[i][j].second = (j + 1) % N; } } else if(op == 'R') { for(int j = 0; j < N; ++j) { res[i][j].second = (j - 1 + N) % N; } } else if(op == 'U') { for(int j = 0; j < N; ++j) { res[j][i].first = (j + 1) % N; } } else if(op == 'D') { for(int j = 0; j < N; ++j) { res[j][i].first = (j - 1 + N) % N; } } else { assert(false); } return res; } int number(string const& s, int& p) { int res = 0; while(isdigit(s[p])) { res *= 10; res += (s[p++] - '0'); } return res; } int main() { int L; string S; cin >> N >> L >> S; int p = 0; auto ans = sequence(S, p); for(int i = 0; i < N; ++i) { for(int j = 0; j < N; ++j) { cout << (ans[i][j].first * N + ans[i][j].second + 1) << " \n"[j + 1 == N]; } } }
AOJ 1361 Deadlock Detection
解法
求めるものは unavoidable になる境界なので二分探索できそうです．
ある時刻からデットロックを避ける最良の方法は，当然 terminate できるプロセスを順に殺していくことです．
愚直にやると殺せるプロセスを探索するのに O(p^2r) かかりそうですが，あらかじめリソースごとに必要な数でソートしておくと O(prlog(p)) でできるようになります．
計算量はトータル O( (t + prlogp)logt) になります．
ソースコード
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; int main() { int p, r, t; cin >> p >> r >> t; vector<int> l(r); vector<vector<int>> n(p, vector<int>(r)); vector<int> P(t), R(t); for(int i = 0; i < r; ++i) { cin >> l[i]; } for(int i = 0; i < p; ++i) { for(int j = 0; j < r; ++j) { cin >> n[i][j]; } } for(int i = 0; i < t; ++i) { cin >> P[i] >> R[i]; P[i]--; R[i]--; } int lb = 0, ub = t + 1; while(ub - lb > 1) { int m = (lb + ub) / 2; vector<int> available = l; vector<vector<pii>> need_r(r, vector<pii>(p)); vector<vector<int>> used_r(p, vector<int>(r)); vector<int> pos(r), cnt(p); queue<int> term_process; for(int i = 0; i < r; ++i) { for(int j = 0; j < p; ++j) { need_r[i][j] = make_pair(n[j][i], j); } } for(int i = 0; i < m; ++i) { available[R[i]]--; need_r[R[i]][P[i]].first--; used_r[P[i]][R[i]]++; } for(int i = 0; i < r; ++i) { sort(begin(need_r[i]), end(need_r[i])); } for(int i = 0; i < r; ++i) { while(pos[i] < p && (need_r[i][pos[i]].first == 0 || available[i] >= need_r[i][pos[i]].first)) { int process_id = need_r[i][pos[i]].second; if(++cnt[process_id] == r) { term_process.push(process_id); } pos[i]++; } } while(!term_process.empty()) { int idx = term_process.front(); term_process.pop(); for(int i = 0; i < r; ++i) { available[i] += used_r[idx][i]; while(pos[i] < p && available[i] >= need_r[i][pos[i]].first) { int process_id = need_r[i][pos[i]].second; if(++cnt[process_id] == r) { term_process.push(process_id); } pos[i]++; } } } if(count(begin(cnt), end(cnt), r) == p) { lb = m; } else { ub = m; } } if(ub == t + 1) { cout << -1 << endl; } else { cout << ub << endl; } }
感想
やるだけなんですがバグってしまった．
AOJ 1362 Do Geese See God?
問題概要
文字列 S を部分列（部分文字列ではない）に持つような最小の長さの回文の集合の中で，辞書順 k 番目のものを求めよ．
・制約
1 <= |S| <= 2000
1 <= k <= 10^18
解法
区間DPをやります．作れる文字列の数 + 辞書順最小構築が必要なので，DPかなあという推測は立つと思います．
まず，問題を2つの部分に分けます．
- 最小の文字列の長さを求める
- 作ることのできる回文のパターン数
最小の文字列の長さは，以下の dp で求められます．
len[i][j] := S[i, j] を部分列にもつような回文の最小長さ
右端と左端が一致していない場合，最小の回文を構成するのであれば，そのどちらかを挿入することになります．一致していれば，明らかに挿入する必要はありません．これを元に漸化式を立てます．
作ることのできる回文のパターン数も，以下の dp で求められます．
dp[i][j] := S[i, j] を部分列にもつような最小長さの回文の種類数
この計算には len[i][j] を用います．S[i] と S[j] が等しい場合，最小長さにするので dp[i + 1][j - 1] が答えです．S[i] と S[j] が異なる場合，S[i] と S[j] のどちらかを挿入することになりますが，len[i + 1][j] と len[i][j - 1] の値の大小によって，どちらを挿入するべきか判定できます．（もちろん小さくなる方を挿入する．）
挿入するほうが決まれば，そのときの dp[i + 1][j] または dp[i][j - 1] の値を加算します．
dp[0][n - 1] < K なら答えはありません．
最後に構築パートですが，これはいつものやつなので雑に書きます．
S[l] == S[r] ならその文字を使うことが確定します．
S[l] != S[r] なら，短くなるほうを選びます．どちらをえらんでも同じ長さを達成できるなら小さい方を使いたいですが，K を超えないギリギリに向かうように選ぶ必要もあります．
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr int INF = 1e9; constexpr ll INFLL = 1e18; ll add(ll& a, ll b) { return a = min(a + b, INFLL * 2); } int main() { string S; ll K; cin >> S >> K; int const n = S.size(); vector<vector<int>> len(n, vector<int>(n, INF)); for(int i = n - 1; i >= 0; --i) { len[i][i] = 1; for(int j = i + 1; j < n; ++j) { if(S[i] == S[j]) { len[i][j] = (i + 1 == j ? 2 : len[i + 1][j - 1] + 2); } len[i][j] = min(len[i][j], min(len[i + 1][j], len[i][j - 1]) + 2); } } vector<vector<ll>> dp(n, vector<ll>(n)); for(int i = n - 1; i >= 0; --i) { dp[i][i] = 1; for(int j = i + 1; j < n; ++j) { if(S[i] == S[j]) { add(dp[i][j], (i + 1 == j ? 1 : dp[i + 1][j - 1])); } else { int min_len = min(len[i + 1][j], len[i][j - 1]); if(len[i + 1][j] == min_len) { add(dp[i][j], dp[i + 1][j]); } if(len[i][j - 1] == min_len) { add(dp[i][j], dp[i][j - 1]); } } } } if(dp[0][n - 1] < K) { cout << "NONE" << endl; return 0; } ll t = 1; string l_ans; int l = 0, r = n - 1; while(l < r) { if(S[l] == S[r]) { l_ans += S[l++]; r--; } else { if(len[l + 1][r] < len[l][r - 1]) { l_ans += S[l++]; } else if(len[l + 1][r] > len[l][r - 1]) { l_ans += S[r--]; } else { ll t2 = t + (S[l] < S[r] ? dp[l + 1][r] : dp[l][r - 1]); if(t2 > K && S[l] < S[r] || t2 <= K && S[l] > S[r]) { l_ans += S[l++]; } else { l_ans += S[r--]; } if(t2 <= K) { t = t2; } } } } auto r_ans = l_ans; reverse(begin(r_ans), end(r_ans)); if(l == r) { l_ans += S[l]; } cout << l_ans + r_ans << endl; }
感想
こういう問題は苦手．
