Hello Barcelona Day2

Day1の内容はJAG合宿Day3と全く同じだったようです。なので記事はDay2からにしようと思います。

beta.atcoder.jp

A - Alice and Maze

問題

 n頂点 m辺の無向グラフが与えられる。各頂点に報酬、各辺にコストが設定されている。 頂点を訪れるたび、その報酬が貰え、辺を通るには、そのコストを支払わなければならない。 スタートは頂点1でゴールは頂点 nとする。Aliceはスタート時点で k円持っており、お金を最大化した後 ゴールから出たい。スタートとゴールの頂点を含め、同じ頂点や辺は複数回通ってもよい。 そもそもゴールにたどり着けない場合は-2, いくらでもお金を増やせる場合は-1, 有限のお金まで増やせる場合は、その金額を出力せよ。

制約

  • 4秒
  • 10テストケース
  •  2 \le n \le 1000
  •  2 \le m \le 100000
  • 初期のお金、報酬、コストはそれぞれ1円以上 10^7円以下

解法

問題は無向グラフで与えられているが、進む方向によって実質かかる費用は異なるので、辺数を2倍にした有向グラフで考える。 ベルマンフォードをやるだけだが、更新時に、現在の所持金が辺のコスト以上かどうかをチェックし、その場合のみ更新するようにする。

さらに無限大に発散するループが存在する場合、 n(頂点数)回目のループで更新された頂点を列挙し、これらのうち1つ以上がゴールから到達可能な場合、 いくらでも所持金を多くしてゴールに到達可能であることがわかる。

計算量はベルマンフォードは本質で O(nm) かなりギリギリ(テストケースを考慮すると 10^9オーダーだし)だけど想定解だった。 最初、無限ループ検出のときに、 n回目のループだけではなく、 nから 2n回目までのループで更新された頂点を全列挙していたが、この場合TLEした。 @oginginがそれ n回目だけでよくね?と言ってくれてプロだった。

B - Buggy Stack Machine

問題

PUSH, POP, ADD, EMPTYの命令(ADDは、上2つPOPし、それらをADDしたものをPUSHする命令)があるスタックがあるが、上からk個の数の2進数での1の位を並べたものが  b_1b_2\ldots b_kとなった瞬間、これらk個の数がすべて消えてしまう、というバグを持っている。 クエリが与えられるので、それぞれのPOPクエリに対して、POPされる値を答えよ。しかし、それまでに不可能な操作(たとえば空のスタックに対するPOPや、要素が1以下のスタックに対するADD)が呼ばれた場合には、ERRORを答えよ。

制約

  • 5秒
  • 50テストケース
  • クエリの数は100000以下
  •  1 \le k \le 10000
  • 入力文字列は60 mebibytes以下

解法

@kenshinが最初これを担当していて、bitsetを使って1の位を覚えておくのは間に合う?と聞いてきた。見積もってみるとかなりギリギリだったけど、まあいけそうかなと言って実装する。 C++の標準のbitsetでは、大きさが異なるbitset同士を比較できないのでかなり困った。大きい方のbitsetに合わせてコンストラクトし直して比較するとTLEするので(定数倍で10倍かかる)、 頑張って比較を実装する。@kenshinが終了間際にWAで苦しんでいたのでソースコードを読んでみると、if (s.size() - (9999 - j) >= 0)というヤバそうな部分を見つける。intにキャストしたらACした。残り4分だった。

感想

さすがに想定解じゃなかった。他チームでもbitsetで書いたところが多かったみたいだが、ほとんどがTLEしてたらしい。 想定解はKMP法だったが、チームメイトは誰もKMP法を実装したことがなかったのでかなり厳しかった。

C - Constellation

読んでない。@oginginが知らない間に通してた。

D - Domination

読んでない。 @kenshinが知らない間に通してた。

E - Elevator

問題

202階のビルがあってエレベーターに n人が1階から乗る。それぞれの人には行きたい階があるが、ちょうどその階に止まらなくても、1階分だけなら階段を使って下に降りることができる。 エレベーターは1階を除いて最小でいくつの階に止まるか。

制約

  • 1秒
  • 100テストケース
  •  1 \le n \le 10000

解法

貪欲にやるだけ。202階が謎制約すぎる。

G - Good Substring

問題

ある文字列がgoodであるとは、そのいかなる部分文字列も長さ2以上の回文を含まないことである。文字列と、クエリ( i番目の文字を cに変えるというもの)が与えられるので、各クエリ後の 最長のgoodな部分文字列の長さを答えよ。

制約

  • 2秒
  • 1テストケース
  • 文字列の長さ、クエリの数ともに 10^5以下

解法

ある文字列が部分文字列に回文を含む必要十分条件はaaもしくはaba型の部分文字列を含むこと(お な じ み)なので、クエリのたびに、この位置を更新し、これらの位置の間隔で最長のものを答えればいい。 問題を言われてhoge秒で解法がわかったが、コンテスト中に読んでなかったので通せなかった。本当にもったいない