こんばんは、しほみんです。
この前、atcoder主催のAGC40に参加してきました。その結果と考え方についてまた話していきます。
AGCとは...
Atcoder Grand Consestのこと。ABCに比べて上級者向けの問題で難しい。お題は全部で6題。配点は様々で時間はおおよそ150 - 180分。初心者ならA問題がいかに早く解けるかが重要だと思う。
正直自分は本当にアルゴリズム素人なのに問題研究もろくにせずコンテストに参加しているのでなかなかスコアが伸びません。時間がプログラミングに避ける状況がないので致し方ないですが少しずつできるようになったらいいなと思います。
今回は結局A問題しか解くことができず、挙句とてもしょぼいことを忘れていて時間がかかってしまいました。そのためスコアも伸びず今回は久々にレートが下がってしまいました...
まあ自分のよう反省も込めて今回は話していこうかなと思います。
ここからはAGCのネタバレなのでまだ解いてない方は注意してください。
A問題（配点300点）
"<"と">"が並んだ文字列を読む。n番目にある">"はan>an+1を示し、"<"はan<an+1を示す。このとき、できる数列の中でその総和が一番小さい場合を求めます。ただし、anはすべて整数である。
例えば、<<<<>の場合、条件を満たすのは{0,1,2,3,4,0}が一番最小の数列なので10となります。
いくつか考察をしていけば答え出てきます。まず、最小の数列なので<か>が連続で続く場合は1,2,3...と順列になります。
なので大雑把には<か>が連続続いた数だけそれまでの1から連続する数の和が出せばいいことが分かります。
次に境界条件を考えます。
><の並びの場合
><の場合最小の数列は{1, 0, 1}となります。なぜなら最小の入る数が0だからです。
>>>>><<<<<の場合、>が5個続いた後、<が5個続くと
{5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5}となり、1から5までの和を2倍して30となります。
<>の並びの場合
この場合は最大の数は一意的には決まりません。<が続く数と>が続く数によります。
<<<>>のときは{0,1,2,3,1,0}となり、7です。
一方、<<>>>のときも{0,1,3,2,1,0)となり、7です。
それぞれどう出すかを考えると、(<が続く数)-1までの和と(>が続く数)-1までの和と
((<が続く数)と(<が続く数)のうち大きい数)を足せばいいです。
つまりこの場合、<<>>>でも<<<>>でも2までの和、1までの和、最大の3を足して3を求めればいいです。この場合、7となります。
<><><>と続くと...
{0, 1, 0, 1, 0, 1, 0}が最小で3となります。
この場合、<や>の続く数の和は全部0です。一方、<>の最大の場合は1なので1を加えます。3カ所あるので3です。><の場合は1ずつあるので2を加えたいのですがこれだと<>の最大値を過剰に数えてしまいます。よってこっちの場合も、><のとき、続くところの数を数えればいいですが、1ずつ引いて考えていけばいいとわかります。><のみの場合足す数はないです。
これらの考察を踏まえると
<でも>でもの続く数が数えて、1から続く数-1までの和をもとめつつ、<>のときはどちらが一番続くかを選んで最大の数を足せばいいとわかります。
<<<>>>>><<<<<>>>の場合、
それぞれ、3,5,5,3個続き、<>のところは2カ所あり、それぞれ、最大は5です。
よって(2までの和)+(4までの和)+(4までの和)+(2までの和)+5+5 = 3+10+10+3+5+5=36
となります。実際そのはずです。
ではこれを効率的に求めるにはどうしたらいいかですが、
<<<<>>>><<<>><<...と続いていく中で、<が続く数、>が続く数をどんどん数えていって、組み分けしておいて決めます。最初の記号を見ると、<>と><の条件変化の場所がわるかので連続して続く数を知ってしまえば解けます。
例えば<<<<>>><<<<>><<<の場合、{4, 3, 4, 2, 3}と分ける。
<が最初なので<>は1,2番目の数と3,4番目の数と5,6番目の数を比較して最大を出す。（6番目の数はありませんが0と入れておくようにします。）
上記の最大の数を足して、あとはそれぞれの数は1からの和を足すでよい。
ここまでの考察はすんなりいったのですが、自分は<や>のみの条件を完全に忘れていました....<や>の場合は比較できないので別途答えを出します。
<は{0,1},>は{1,0}なので両方1です。
ここまでくると例外条件があるのでこれは必ず考える必要があります。
これに気が付かないで時間を1時間ぐらい無駄にしました。
包括的なアルゴリズムも考えるだけでなく、例外もきちんと考えて答えを出せるようにするのがプログラムの基本になります（エラー処理とかももちろん必要です）。
今回はそれをかみしめた結果になりました。
すでに一回やらかしているので今度は絶対にやらかさないようにします...
自分が書いたコードも上げておきますので別途役に立ててください...
ではでは。
