海賊王

http://abc023.contest.atcoder.jp/assignments
今日はここのA~Cを解きます。何で全部王なんでしょうね。ワンピースにでも触発されたのでしょうか。
インクルードはいつもの通りの部分は省略します。

問題A

加算王、強そう(小並感)

まあこれは言わずもがな。

問題B

パッと見、面倒そうですが、場合分けするだけです。
文字数は順番*2+1個あるので、そこから順番を逆算できます。3の倍数でa,b,cのどれから始まるかが変わるので、そこで場合分け。後はabcabc…です。
注意点としては、Nが偶数だと自動的に間違いということを書いておく必要が有ります(書かないと、以下の(N-1)/2が正しく出ない)

問題C

飛車置いて、ちょうどK個の飴がとれるといいですね、という問題。単純に全マス全探索するとオーダーがn^2なので死にそうです。そこで横の列と縦の列の飴の個数の和がKとなる場合を考えます。しかし、この時例外が存在します。それは飴が置いてあるマスを起点とした場合は一個ずれてしまう(縦+横-1のように重複分を引くのが正しい)ので、まず最初に飴が置いてある部分のみを考えて、その後全走査になります。

これでうまくいくかと思いきや、縦と横の和がKとなるのに(縦の列全て)×(横の列全て)で考えると時間切れになります。そこで発想を変えて、縦or横の列がiになる列は何個あるか、というのを配列に加えます。すると、K=i+(K-i)(i=0~K)のように縦or横の列の和を動かすことで、O(K)で解くことができます。

細かいことはコードの中に書きました。

今回もCはなかなか厄介でしたね。

民族的な

http://abc024.contest.atcoder.jp/assignments
今回はこれのA~Cですね。

インクルード等の前準備は下記の通り

問題A

これは大人料金の合計+子供料金の合計で、人数超えてたら割引ってことですね。今更説明はいらないと思うのでコードだけサクッと。

問題B

これは自動ドアがどれだけ開いているかという問題ですね。開いている途中に人が来ると時間がその分延長されます。
方針としては
1.一番最初にドアが開く時間を前の時刻(tbef)として記録
2.次の人が来るたびに、その時間と前に来た人の時間差をとる
3.取った差がドアの開閉時間より短ければ、次の人が来るまで扉はずっと空いているので合計時間にt-tbefを加える
4.取った差がドアの開閉時間より長ければ、ドアは一旦閉じるので合計時間にTを加える
5.tbef=tとして時間を更新する
6.2~5を最後まで繰り返す。最後の人が通過後はそこからTだけ開くので最後にTを加える
という感じです。初期と最後に微妙な引っ掛けがあるので注意しましょう。

問題C

民族大移動と銘打っていますが、結局都市を数直線上で考えて、目的地が元から右ならひたすら右に、左ならひたすら左に進んでいけばいいだけです。

ちょっと問題文分かりにくいですよね。私ははじめ巡回セールスマン的なものと思ってたら何てことはありませんでした笑

○×ゲームとか

http://abc025.contest.atcoder.jp/assignments
これのA~Cまで解いてみました。

まずは以下のインクルードが共通

問題A

要するに、NをSの長さで割った商が一つ目のアルファベット、余りが二つ目のアルファベットの順番となります。
ただし、普通にC++の配列でとった場合は配列が0から始まるので、初めに1を引いておく必要があります。

問題B

二問目はスイカ割り??設定が謎すぎるw
東・西をそれぞれ数直線の+-と考えて、Eastなら+,Westなら-で要素を加えていきます。
進む距離xがB~Aの範囲に限定されていることを表現する必要がありますが、min(max(l,A),B)などと書けば一発です。

問題C

○×ゲームみたいな何かです。隣同士の記号が一致しているか否かでどちらに得点が入るか決まります。
結局、うまい方法はなさそうで、いかに上手く総当たりを表現するかという感じみたいです。

とりあえず、3×3の二次元配列を用意して、0が未記入、1が○、2が×みたいな感じで値を表現する。
で、最適戦略が何かという話なんですが、二人の点数の総和はあらかじめ決まっているので、直大君のターンでは、自分の点が極大になる選択を、直子さんのターンでは直大君の得点が極小になるようにマスを選んでいくことになります。

で、マスを埋める各場合を再帰的に書いていく感じでしょうか。

最後はむずかしかった…
ちなみにこれ、int choice(int turn, vvi& mp)って参照渡しにしてますけど、参照にしないと5倍くらい時間かかるんですね。参照渡しにできるときはしといた方がいいですね。