naoya_t@hatenablog

いわゆるチラシノウラであります

AtCoder Grand Contest 019

AtCoder Grand Contest 019 - AtCoder Grand Contest 019 | AtCoder
touristがwriterの回。2時間半。

ooo--- 206位 1700(5)
5回WA出して諦めかけたCをなんとか通した
rating: 1155→1465
f:id:n4_t:20170826235156p:plain
パフォーマンスが2325だった

A - Ice Tea Store (300/300)

http://agc019.contest.atcoder.jp/tasks/agc019_a
1Lの最安値と2Lの最安値を求めておいて
(2L最安値 x N/2) + (1L最安値 x N%2)
→AC (08:32)
https://agc019.contest.atcoder.jp/submissions/1539592

B - Reverse and Compare (500/500)

http://agc019.contest.atcoder.jp/tasks/agc019_b
区間は全部でN(N-1)/2箇所あるしこれを全部調べるだけの時間はない
何か一般化する方法でもあるんだろうか

ひっくり返す区間を[]で囲むとして
[a]att = aatt
[aa]tt = aatt
[aat]t = taat
[aatt] = ttaa
a[a]tt = aatt
a[at]t = atat
a[att] = atta
aa[t]t = aatt
aa[tt] = aatt
aat[t] = aatt

とりあえず、区間の両サイドが同じ場合、区間の両端を1つずつ縮めたものと同じ結果になるから「考えなくていい」例えば aaatta という文字列があったとき
[aaatta] = a[aatt]a
みたいな

とすると、N(N-1)/2 個ある区間のうち、両端が違う文字のケースがいくつあるかを求めればいいのでは。
とはいえ当然二重ループしてたら間に合わない。

a〜zの出現回数を調べてcnt['a']とする(これはO(n)ですな)。
例えば文字aについて、[a...x] (xはa以外の任意の文字) のパターン数は
cnt['a'] x (N - cnt['a'])
これをa〜zまで足し合わせて
Σ cnt[c_i] x (N - cnt[c_i])
これは同じやつを2度ずつ数えてるはずだから2で割って
あと、素の文字列が入ってないはずだから1を足して
1 + 1/2 Σ cnt[c_i] x (N - cnt[c_i])
→AC (28:41)
https://agc019.contest.atcoder.jp/submissions/1540699

C - Fountain Walk (900/900)

http://agc019.contest.atcoder.jp/tasks/agc019_c
2度以上見たくないって言ってるのにサンプルケースで噴水2個通ってるやつがある。訳がまちがってる?そうじゃないみたい。ああ、同じ通り(東西・南北)には高々1つしか噴水がないってことか。
で。
噴水を迂回するのって常に遠回りになるから、噴水に出くわす回数が多くなってくるとコの字に遠回りしたほうがよくなったりする?→いや、噴水の交差点で右折なり左折なりする場合、むしろショートカットになるから積極的に曲がっていきたい。
スタートからゴールまでの間にどれだけ多くの噴水交差点で曲がれるか、を競うゲームか。
とするとこれは最長増加部分列。(長方形の外側の噴水は全部無視してよい)
→WA(1) https://agc019.contest.atcoder.jp/submissions/1542691
Runtime Errorが1つ→最長増加部分列の長さを求めるdp配列の長さが1つ足りなかったので直した
→WA(2) https://agc019.contest.atcoder.jp/submissions/1543074
7割方のテストケースはACみたいなんだけど。何だろう。

最初と最後の行の噴水を通過する場合、どちらか一方は直進になるのか
最初の噴水が長方形の下の辺、最後の噴水が上の辺にあるケース?
→WA(3) https://agc019.contest.atcoder.jp/submissions/1543478
AC増えた気がするけどまだまだWAある
左の辺と右の辺に噴水、ってのもあるか
→WA(4) https://agc019.contest.atcoder.jp/submissions/1543660
いやAC減ってるし。通らないかもしれない噴水まで考慮に入れてしまったか。
通る場合だけにするには…最初と最後を除いたものの最長増加部分列を求めてそれに+2したやつに等しければ?
→WA(5) https://agc019.contest.atcoder.jp/submissions/1544035
standing見たらみんなこれ飛ばしてDに行ってるじゃん…orz
一旦諦めて、D,Eを読んだ

また戻ってきて
いやそもそも、最初と最後の噴水が一番端の通りにあったとしても、十分な距離があるならそこを曲がり角にするコースだって取れる
というか
(通る噴水の数)が(南北の通りの数)または(東西の通りの数)に等しい場合に、どうしても最初か最後が曲がり角にできない
鳩の巣原理ってやつね
→AC (135:58)
https://agc019.contest.atcoder.jp/submissions/1544852

D - Shift and Flip (0/1000)

http://agc019.contest.atcoder.jp/tasks/agc019_d
;
読んだ

E - Shuffle and Swap (0/1700)

http://agc019.contest.atcoder.jp/tasks/agc019_e
読んだ

F - Yes or No (0/2000)

http://agc019.contest.atcoder.jp/tasks/agc019_f
開いてない