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

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秒で解法がわかったが、コンテスト中に読んでなかったので通せなかった。本当にもったいない

Joeの精進記録

旧：競プロ練習記録

Hello Barcelona Day2