ABC027
今回は時間ギリギリで四完。個人的にはA<B<D<Cぐらいの難易度だったきがする。どちらにしろABCにしては難しい。
ABC027へのリンクはこちら http://abc027.contest.atcoder.jp
ぶっちゃけスライド(abc027)が有るので解説はいらないと思うけど備忘録的な意味を込めて。
A.
長方形なので向かい合う辺の長さは等しく、三つの中で等しい組を見つければ残ったものが答えになる。
B.
微妙に時間を食ってしまったB. まず、人口の総数%島の数!=0ならば、島の人口を等しくすることができない。次に順番に島ごとに見ていって、平均値に等しくなければとなりの島に人口を移すと考える。このとき途中で島の人数がマイナスになってしまうことがあるが結果的に問題はない。
C.
Nimゲームっぽい。勝利条件をさぐらなければいけないわけだが、MINMAXとかで1〜100までを試すと法則が普通に見えてくるので答えになってしまうっぽい。僕はそれをやらなかった(気づけなかった)。
Nを二進数にして表記する。桁数を考えてみるとNを超えないで最後の手を打つ番がわかる。(精確にいうとNと二進数で同じ桁を言う方)。よって偶奇で場合分けをする。桁数をmとする。最後の桁を言う方は、N以下になっていてほしい。逆にいうと最後の桁を言わない方は前の段階で大きくしてしまえばいいとわかる。さらに逆にいうと、最後の桁を言う方は大きくされる前に小さくしたい。何がいいたいかというと最適な行動は固定されてる。最後の桁を言う方は全部2倍すればいいし、言わない方は全部2倍+1すればいい。
例：N=100100(2) この場合最後の桁を言うのは先手。先手はなるべく小さくしたい。後手はなるべく大きくしたい。よって10->101->1010->10101->101010となり先手がまける。これをシミュレートすればいい。(もっというと101の段階でもう勝利は決まっている)
D.
個人的には結構簡単だと思った。ポイントは+の段階でこれまでの正負方向の移動の数を気にするのではなく、式をMについてくくりだすように、あるMの命令以降にある+,-の数に注目してもいいことに気づけるかだと思う。
ここで幸福値を最大化したいので+,-の和がプラスの奴は全部正の方向に動くようにしたいが条件文に原点に戻っていなくてはならないとあるので、和が大きいものから順に割り振っていく。
ここまでの操作で最大のオーダーはソートのO(MlogM)である。よって十分間に合う。
命令以降にある+,-の数の数え方だが、O(n^2)にしないように。（この場合はおそらく通るけど）
CodeForces #Pi Div.2
今回は2完でCを解くことができなかった。特にDは解法のアイデアが浮かんでいたが本番では実装できず残念。焦りすぎず、コンテストに慣れる、生活リズムをデチューンする必要が感じる。(1672->1601)Div.1が遠ざかる。
A.
Aにしては多少難しい？とりあえずソートをして各要素ごとに最大値、最小値をチェック。
最大値： 要素の一番端っこの要素
最小値： 要素の隣の要素
O(nlogn)
B.
いる人数の配列をとる。ログイン、ログアウトを記録していく。データ構造はsetを使っとく。明記されてないIDがログアウトしたときはそれ以前の人数を1足す。
C.
b*k^0,b*k^1,b*k^2がポイント。真ん中を基準にして考えるとb/k,b,b*kとなるので、それ以前にb/kが何回あって、それ以降にb*kが何回あるかわかればよい。
bは負の値もとるのでmapをつかってやるのがよい。それ以降のcountとそれ以前のcountをしらべるのは典型的なので省略。
D.
領域を分割すると考えてやるとわかりやすい。shotsがされるたび領域が分割されていく。入れることができる船の数がkより小さくなればそこが答え。
|............|............|
|....|.......|............|
ここでshotsされて分割される領域以外に入る船の数はかわらないので分割されたときの差分を考えてやればいい。shotsされた点はsetで保持しておく。shotsがどの領域
にあるかはupper_boundでしらべればいい。
門番として0,n+1をsetにinsertすると楽。
SRM#664Div.2
今回は色々駄目でレートが減少。Easyすらミスで死んでるのはつらい。冷静にやれば全部通せそうなのもつらい。
Easy:
受け取った数字を文字列にして一要素ずつ比較する。違ってる個数が1個以下なら"happy"
Med:
愚直解が解。a+b+cがわかっているのでdpで十分。再帰は局面の数を見積もればオーダーがわかるので大丈夫そうというのがわかる。dpはその数の組をチェックしたらtrueにしてたどった数の組がわかるために使う。
あとはsortしたりとかあるけど普通にやるだけ。
Hard:
マージソートが再帰なんだから解も再帰やろ(暴論)。もととなる配列があって、それはふたつの結合からできている。そのときに何回比較してるかわかればいい。あとはそれを再帰的にやればいい。
イメージ的にマージソートまんまかもしれない。
r[1, 2, 3, 4] + l[5, 8, 6, 7]
mer[1, 5, 8, 2, 3, 6, 4, 7]
＊同じ配列内で順序が入れ替わることはない。
＊結合前はsize/2以下のものの配列とsize/2より大きいものの配列
＊比較はどちらかの残った要素がゼロになるまでおこる
SRM#663Div.2
今回は灰色脱却を目標に参戦。結果緑一歩手前までレート上昇。easy,med早解きできたのでよかった。Hardがとければ一気にレートが上がるらしいが道は険しい。
Easy: 色を塗り替えてチェス盤のようにするという問題。チェスでいう白、黒の部分は独立してかんがえればよく、それぞれで出てくる色をカウント、多い色で塗る。ただし、同じ色になってしまう時があるので二番目の色でぬった場合との最小の塗り替える枚数を考える。
Med: これはinitialから変更していくのだと2^nになるので無理とわかる。わりと定石の考え方でtargetから逆の操作をしていってinitialになればいい。whileループの条件式でミスってセグフォして時間をくってしまった。もう少し早くできてれば順位ももっとあがったと思う。
Hard: ぱっと見た感じ桁DPだろうと予想が立つ。しかし難しく実装ならず。実際回答をみたけどよくわからない。
Codeforces #313 Div.2
今回は自分的に簡単だと思った。3完できてよかったけど、Dが考え方はあってたが実装できず悔しい。このまま行けば目標のDiv.1にいけそうなのでこの調子でがんばりたい。(1566->1672)
A. 考えてみれば1があるかどうかが問題になってることがわかる。
B. 長方形の内部に入れられるかの問題。8種？のパターンがあるので、これを全部精確にif文にするのどっかでミスしそうだったのでswap(x,y)をして2^3パターンを全部試した。
C. 想定解は、でかい三角形から小さい三角形3つをひくものらしい。僕は上辺の1列目の三角形の個数を数えて、横の辺の長さによって、一つ下の列の三角形の個数がどうかわるかを調べた。0(n)なのでちょっと遅いけど、通るので問題はなし。
D. 読んでみると再帰で愚直に実装が思いつくけどO(n^2)っぽい？（ここに関しては最悪パターンを思いつくのが難しいので愚直解でも落とせなかったりする。平均n^1.5とかぐらいになって、早い言語だと通ってしまうっぽい）
推移律を用いて等価変形を行っていけば良いのがわかって、特殊？ソートをすればいい。そこまでは思いついていたが実装ができなかった。場数が足りない。
E. 既知感のある問題。R,Cが小さければdpでおしまいだけど、R,Cが大きいのでTLE.解法として思い浮かぶのは包除定理だけど2^nで無理っぽい？で思考停止してしまった。
実際の解法はというと、黒のマスを左上からのマンハッタン距離でソート。その後DP[i]=(i-1までの黒マスを通らないでiの黒マスにたどり着き方)とすれば、O(n)で解ける。
たどり着き方はmod1e9+7なのでオイラーの小定理をつかえばいいかな。
競プロonC++のテンプレ
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<functional>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define INF 1<<30
#define MP make_pair
#define mp make_pair
#define pb push_back
#define PB push_back
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define ll long long
#define ull unsigned long long
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
}
