Codeforces 425 div2 C Strange Radiation

 

Problem - 832C - Codeforces

 

直線上にn人がそれぞれ左か右を向いて立っており、時刻 t=0でそれぞれv[i]で進む。ある整数地点に加速爆弾を置くことができ、時刻t=0で爆発した爆風が左右に速度s( > v)で進み、爆風と向き・位置が一致した人は、速さが s だけ加算される。地点 0, 10^6に誰かが辿り着くまでの最小時間を求める。

 

「ある時間 t 以上ならば(適切な位置に爆弾を置くことで)可能、t 未満なら不可能」

という条件なので時間 t で二分探索。

時間 t を固定すると、例えば正の方向を向いているある人に対し、範囲 [x1 , x2] で爆弾を置けば t 以内に 10^6 に辿り着ける、という範囲が計算できる。

爆弾の位置をX,爆風をs, 人の位置をx, 人の速度をvとして

X + sT = x+ vT

Tが爆風と人が一致する時間になるので、求める条件は

x + vT   +    (v+s)(t-T) >=10^6

これをXについて解けばO(1)で計算できるので、右を向いている人全員に対しこの範囲を計算します。

次に左を向いている人にも同じように計算し、その範囲が右を向いている人の範囲のどれかと被っていたら、その t で達成可能ということがわかります。

範囲計算は、「爆弾がなくても達成可能 (どこに置いてもいいので [0,1000000]が範囲)」や「どこに爆弾をおいても達成不可能(imos法で打ち消しあって欲しいので [1,0]を返す)」などに気をつけます。

右を向いている人全員の範囲を計算するのにimos法と累積和を用いました。

例えば右を向いている人の範囲が [2,5] , [3,6]だとすると、

0 , 0, 1, 0, 0, 0,-1, 0, 0, .... ←[2,5]の範囲をusedに記憶

0 , 0, 1, 1, 0, 0,-1,-1, 0, .... ←[3,6]の範囲を記憶

0 , 0, 1, 2, 2, 2, 1, 0, 0, .... ←imos法により、地点がいずれかの範囲内であれば0より大きい

0 , 0, 1, 3, 5, 7, 8, 8, 8, .... ←累積和により、[ x, y ] に範囲が含まれているかどうかを sum[y] - sum[x -1] >0 で調べられる

 

#include <bits/stdc++.h>
#define REP(i,n) for(LL i=0;i<(LL)(n);i++)
#define ALL(x) (x).begin(),(x).end()
#define LL long long

using namespace std;

//右を向いている人の範囲計算
pair<LL,LL> minX(LL s,long double t,LL x,LL v){
if((x+v*t)>=1000000)return make_pair(0,1000000);
if((x+(v+s)*t)<1000000)return make_pair(1,0);
long double res=(0.0 + (s-v)*1000000 + x*v -(0.0 + s*s -v*v)*t +s -1)/s;
return make_pair(max(0LL,(LL)res),x);
}

//左を向いている人の範囲計算
pair<LL,LL> maxX(LL s,long double t,LL x,LL v){
if((x-v*t)<=0)return make_pair(0,1000000);
if((x-(s+v)*t)>0)return make_pair(1,0);
long double res=(0.0 + x*v +(0.0 + s*s -v*v)*t)/s;
return make_pair(x,min((LL)res,1000000LL));
}



int main(){

LL n;
LL s;
cin>>n>>s;
LL x[n],v[n],t[n];
REP(i,n)cin>>x[i]>>v[i]>>t[i];

long double left =0;
long double right=1000000;
long double center;

long double err=1e-10;


LL used[1000002];
bool isRight=false;

while(true){
isRight=false;
center=(left+right)/2;
fill_n(used,1000001,0);
REP(i,n) {
if (t[i] == 2) {
pair<LL, LL> pa = minX(s, center, x[i], v[i]);
used[pa.first]++;
used[pa.second + 1]--;
}
}
REP(i,1000001)used[i+1]+=used[i];//imos法
REP(i,1000001)used[i+1]+=used[i];//累積和
REP(i,n){
if(t[i]==1){
pair<LL,LL> pa = maxX(s,center,x[i],v[i]);
if(pa.first==0){
if(used[pa.second]>0)isRight=true;
}else{
if(used[pa.second]-used[pa.first-1]>0)isRight=true;
}
}
}
if(isRight)right=center;
else left=center;

if(abs((left+right)/2 -center)< err)break;
}

cout<<fixed<<setprecision(20)<<right<<endl;

return 0;
}

Atcoder Beginner Contest D埋めしたので初心者向け学習法とか色々書く

f:id:inmir:20170722161554p:plain

 

今年の3月頃から競プロを始めましたが、ようやくABCのD(だけ)が埋まりましたので復習がてら色々書いてみます。

 

f:id:inmir:20170722164411p:plain

↑ 記念の初AC

 

 【やったこと】

・序盤

競プロの存在をAtCoderで知ったので、AtCoderの問題を解いていました。

for, if文ならかける程度の初心者でしたので、上の画像くらいA,B,C問題を解いていき(Cのいくつかくらいまでならfor,if文知識で解ける)、D問題を数問みて新たに勉強が必要だな、と感じました。

 

・中盤

蟻本を読みました。五日間くらいかけて(難しい所をとばしとばしで)中級編まで読みきって、その後AtCoderの問題を解きながら、やったことのあるアルゴリズムやデータ構造を見ながらでも書いてみるといった使い方でした。なんで蟻本の問題自体は解いてないです。でも解いた方が力になります。

「そんなん蟻本にも書いてなかったし(半ギレ)」→載ってる、というのを10回くらい繰り返しました。

 

・今とか

とりあえずコンテストを増やして、今はAtCoderTopCoder, Codeforcesに参加するようになりました。やっぱり実際のコンテストに出るのが一番楽しいし、問題を解くモチベーションが上がります。あと、普通にAtCoderの難易度は他と比べても遜色ないです。のでAtCoderに参加してるなら他のにもバンバン出た方がいいと思います。TopCoderはちょっと設定が面倒ですが、解説サイトは色々ありますし、CodeforcesAtCoderと同じ感じで登録するだけです。

蟻本は継続して読んでいます。最近あった「そんなん蟻本(略」はgrundy数でした。

 

【オススメ勉強法】

全くの初心者だった自分の経験から、もう一度競技プログラミングを始めるならこういう感じで学んだらいいんじゃないかという順です。教材はAtCoderとします。

 

ABC の A~Cくらいまで

⑴標準入力、出力が出来るようになる

⑵データ型(int, char, bool)、配列、for文、if文が書けるようになる

STLを使えるようにする(+計算時間を考える O(N) )

 C++ なら string , vector , set , map , priority_queue ...

 Javaなら String, ArrayList, LinkedList , HashSet , HashMap ...

などなど

 

 

1,2,3の順でABCのA,B,Cに対応している感じがします。本当か?

特に、競プロをしだすとアルゴリズムやデータ構造の方に目が行きがちになると思いますが、特に初心者のうちはしっかりとSTLの知識をつけた方がいいと思います。というかやっておかないと色々話になりませんでした...。

最初の内はおおまかにどんなことが出来るか、ということを勉強するといいと思います。慣れてきたら、コンテナクラスのランダムアクセス、追加・削除、検索といった計算時間も知っておくようにしましょう。ArrayListとLinkedListの違いくらい知っておきましょう(3時間くらいTLEに悩まされました)。

ちなみにC++STLを勉強するならこの辺がオススメです。(C++ 標準ライブラリ の項目)

C言語/C++ プログラミング 入門

 

ABC D

(1)アルゴリズム・データ構造をサッと勉強する

(2)問題を解く、分からなかったら復習する

(4)ライブラリを作る

 

問題を解きます。問題を解きましょう。後は問題を解くだけです。

問題を解きますが、特に初心者のうちはよく言われることですが、20分くらい考えて解けなかったら解説を見た方がいいと思います。

最初のアルゴリズムとデータ構造の勉強は、結構サッとやった方がいい気がします。真面目に実装とかやると滅入ります。ただ、何も知らずに問題を解こうとすると、全点対間最短距離問題(コードで精々2,3行)に1時間以上悩んだ挙句解説見て勝手にキレます。なのでサッと。

ちなみに、体感的にABC-D問題解くにあたって優先順位の高いデータ構造・アルゴリズム、テクニックは下の感じ。上の方が高い。

・DP

・累積和、imos法

・UnionFind木

・bit 関係 (選ぶ・選ばないの2択を全探索するときなど)

・mod 関係(フェルマーの小定理

・二分探索

 

DPは本当に色んなところで使いますので、最初に典型問題解くといいかも。

Typical DP Contest - Typical DP Contest | AtCoder

(本当にAtCoderさんは教材として優秀...)

それと、一回使ってライブラリにできそうなもの(segtree , dikstra , nCm mod p etc...)は一回やったら作っとくといいと思います。他の人のを借りてもいいけど、自分で実装した方が使いやすいし勉強になりますし、構造や処理をカプセル化する能力もつきます。

 

【現状】

f:id:inmir:20170722235319p:plain

割とザコいですがこんな感じです。ただDをたくさん解いてみて、後半になるほど実装力とか知識とか増えてきた実感があるので、最近右肩上がりを達成できるんじゃないかと思ってます。いつまで続くのか......

次はARCのA,Bかな...今年中にTopCoderのイエローを目指してます(言うは易し)。

Codeforces Round #424 Div.2 A,B,C,D

所感

考察力足りない...

本番A,Bを20分くらいで通して後は唸ってました。

 

Problem - A - Codeforces

与えられた数列が単調増加、同値、単調減少の順になっているかを判定する。

愚直にやったのであんまり綺麗なコードじゃありません...。

単調増加のbreak判定で同値かどうかだけ気をつければいいですかね。

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
#define LL long long

using namespace std;

int main(){
int N;
cin>>N;

int cnt=0;
int before=0;
int next;

bool isPossible=true;
bool same=false;
while(cnt<N){
cin>>next;
cnt++;
if(next<=before){
if(next==before)same=true;
break;
}
before=next;
}

before=next;
if(same){
while(cnt<N){
cin>>next;
cnt++;
if(next>before)isPossible=false;
if(next<before)break;
before=next;
}
}

before=next;
while(cnt<N){
cin>>next;
cnt++;
if(next>=before)isPossible=false;
before=next;
}

if(isPossible){
cout<<"YES"<<endl;
}else{
cout<<"NO"<<endl;
}

return 0;
}

 

Problem - B - Codeforces

大文字・小文字両方のアルファベットを対応するものに変換する。

charの知識があれば一瞬だと思います。大文字も変換しないといけないので

変換元のローマ字 -'a' +'A' で大文字にしています。

char型が整数を表しており、連続するアルファベットは数値も連続していることを利用していますね。ちなみにアルファベット以外(数字)はそのまま出力するので

最初に compile[i] = i (変換しない)を代入しています。

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
#define LL long long

using namespace std;

int main(){

char compile[256];
REP(i,256){
compile[i]=i;
}

string from,to,input;
string output="";
cin>>from>>to>>input;

REP(i,26){
compile[from[i]]=to[i];
compile[from[i]-'a'+'A']=to[i]-'a'+'A';
}

REP(i,input.size()){
output+=compile[input[i]];
}
cout<<output<<endl;

return 0;
}

 

Problem - C - Codeforces

未知のある得点に対し、与えられた数列の順に得点が加算されていく。得点の過程の集合(最初の得点は含まない、また加算された順番通りとは限らない)が与えられるので、最初の得点としてありうる個数を求める。

終わった後にシャワー浴びてたら解けました(よくある)。

最初の得点に対する変化をsetで持っておきます。

例えば、得点の変化が (-5 , -5 , 10 , 12 , 13) なら、最初の数を x とすると、得点は

(x -5, x -10, x, x +12, x +25) と変化するので、(-5, -10, 0, 12, 25)というようなsetを作ります。覚えている得点は最初の得点を含まないので、覚えている内の一つの得点(コードではremember[0]としています)が、最初の得点からの変化が -5なら、-10なら...と列挙していきます。他の点数がset内に含まれていれば有りうる、そうでなければ有り得ません。例えば 7, 2,24 という値を覚えていたとして、7 が最初の得点からの変化が -5 (最初の得点が12 ) だとすると、2は最初の得点からの変化が -10 , 24は +12 なので、先ほどのset内に含まれるので有り得ます。二重ループとset.countでO(nk log k)。

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
#define LL long long

using namespace std;

int main(){

int k,n;
cin>>k>>n;
set<int> point;
int sum=0;
REP(i,k){
int p;
cin>>p;
sum+=p;
point.insert(sum);
}

vector<int> remember;
REP(i,n){
int p;
cin>>p;
remember.push_back(p);
}

int cnt=0;
for(auto p : point){
bool isPossible=true;
REP(i,n-1){
if(point.count(remember[i+1]-(remember[0]-p))==0)isPossible=false;
}
if(isPossible)cnt++;
}

cout<<cnt<<endl;
return 0;
}

 

Problem - D - Codeforces

直線上にn人がa[i]の場所いて、k個の鍵( k >=n )がb[j]の場所にある。n人全員がいずれかの鍵を持って(あるb[j]に辿り着いて) pの位置にあるオフィスに着くときの最短時間を求める。

まず最初に、鍵がn個ちょうどだけあったときのことを考えます。このとき、オフィスから見て左右両方の一番外側の人、鍵を考えると、一番外側の人が一番外側の鍵を持って行くのが最短であるとわかります。順番に外側から考えると、結局端の人から順に、端の方から鍵を持って行くのが最短であると分かります。

次に、k個の鍵についてn個の鍵を選びます。ここで、選んだ鍵がとびとびだとします。もし空白が一番外側にいる人より外側にあるならば、より内側にあるものを選んだ方が近いことが分かります。また、内側にあるならば、オフィスに向けて空白を埋めるように取る鍵をシフトしても、オフィスに行く途中で拾うので、問題ないことが分かります。

以上の考察により、k個の中から連続するn個について、n人で順番に持って行った時間の最小値が答えになります。

こういう特殊なデータ構造とかアルゴリズムとかを使わない考察系の問題をスラッと解けるようになりたい...

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
#define LL long long

using namespace std;

int main(){

int n,k;
LL p;
cin>>n>>k>>p;
LL a[n];
REP(i,n)cin>>a[i];
LL b[k];
REP(i,k)cin>>b[i];

sort(a,a+n);
sort(b,b+k);

LL ans=2*1000000000;
REP(i,k-n+1){
LL time=0;
REP(j,n)time=max(time, abs(a[j]-b[j+i])+abs(b[j+i]-p));
ans = min(ans,time);
}

cout<<ans<<endl;

return 0;
}

TopCoder SRM #716 div2 (Easy,Middium)

所感

Easyの方を、最初律儀に全順列試そうとしていました。アホです。

何とか提出して(110点くらいだった)Middiumも方針立てたのですが、問題文中の

ab<=bc<=ca を見逃していました。ソートして場合分けしてたら時間切れ。悔しい。

 

Easy
https://community.topcoder.com/stat?c=problem_statement&pm=14628

与えられたxについて、xの各桁の数字を並び替えることで、元のxの倍数であるような数字を作ることが出来るかを判定する。

 

DFS(深さ優先探索)で順列作ろうと2,30分くら奮闘してました。アホです。

並び替えて作った数字はxの倍数なので、xの倍数からxのアナグラムを探せばいい。

因みにvector は全ての要素が等しいかどうかの比較演算が出来る...今回知りました。

#include <bits/stdc++.h>
typedef long long ll;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
using namespace std;

class Permutiple {

public
:
string isPossible(int x) {

vector<int> xnum;
int x_=x;
while(x_>0) {
xnum.push_back(x_%10);
x_/=10;
}
sort(ALL(xnum));

bool can = false;
REP(i,8) {
//2x<=multix<=9x
int multix=x*(i+2);
vector<int> mxnum;
while(multix>0){
mxnum.push_back(multix%10);
multix/=10;
}
sort(ALL(mxnum));
if(mxnum==xnum){
can=true;
break;
}
}

if (can) {
return "Possible";
} else {
return "Impossible";
}
}
};

 

Middum

https://community.topcoder.com/stat?c=problem_statement&pm=14624

文字列A,B,Cは、'1'か'0'のみで構成されている。二つの文字列の最長共通部分列の長さがそれぞれab, bc, caであるようなA,B,Cの例を示す。

 

面倒なのでどれか一つを"11111..."みたいにしたいなって思いました。例えばAを"111..."とすれば、Bを"11..(ab個)", Cを"11..(ac個)"とすればab,acについて達成できます。BCの最長共通部分列の長さはbcであるので、0で調節(B,Cに bc-ab個の0を加える)。コードではBが"11111..."となっています。

#include <bits/stdc++.h>
typedef long long ll;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
using namespace std;

class ConstructLCSEasy {
public:
string construct(int ab, int bc, int ca) {
string A,B,C;
A="";B="";C="";
REP(i,50){
B+="1";
}
REP(i,ab){
A+="1";
}
REP(i,bc){
C+="1";
}
REP(i,ca-ab){
A+="0";
C+="0";
}

return A+" "+B+" "+C;
}

AtCoder ARC #076(C,D,E)

所感

1完のみで惨敗です。D,Eは本番中途中までいっていたので解説を読んで解き直してみました。

 

C: Reconciled? - AtCoder Regular Contest 076 | AtCoder

犬N匹と猿M匹を、犬と猿が隣り合わないように並べる時の並べ方の総数。

 

差が

・2以上なら0

・1なら種類の場所が一意に決まるのでN!M!

・0なら先頭が犬か猿かの2種類あるのでN!M!*2

で余りを出しながら計算。

 

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;
long long INF = 1000000007;

int main() {
long long N,M;
cin>>N>>M;
if(abs(N-M)>1){
cout<<0<<endl;
}else{
long long ans=1;
REP(i,N){
ans*=(i+1);
ans%=INF;
}
REP(i,M){
ans*=(i+1);
ans%=INF;
}
if(N==M){
ans*=2;
ans%=INF;
}
cout<<ans<<endl;
}

return 0;
}

 

D: Built? - AtCoder Regular Contest 076 | AtCoder

街(x1,y1)と(x2,y2)を結ぶコストがmin(|x1-x2|,|y1-y2|)である時の、全ての街を繋ぐ最低コスト。

 

最初に最小全域木かな?と思いましたが、辺を張るのにN^2かかるじゃん...と思って延々と別の解法を考えてしまいました。

解説にもありますが、(i,j,k)について x_i<=x_j<=x_k の時、i-k間を結ぶくらいなら i-j, j-k間を繋ぐよねっていう話。なので、x,yについてソートして隣同士の街の辺だけ張る。これだとO(N log N)なので後は最小全域木クラスカル法で解きました。構造体のソートはもうちょっといい方法があると思います...

 

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
using namespace std;

struct Edge{
int u,v,cost;
};
struct Node{
int x,y,id;
};

bool compx(Node& x,Node& y){ return x.x<y.x ;}
bool compy(Node& x,Node& y){ return x.y<y.y; }
bool compc(Edge& x,Edge& y){ return x.cost<y.cost;}

//////////////////UnionFind木の実装/////////////////
int pare[100000];
int trank[100000];

int find(int u){
if(u==pare[u]){ return u
; }
return pare[u]=find(pare[u]);
}

void unite(int u,int v){
u=find(u)
; v=find(v);
if(u==v){ return; }
if(trank[u]<trank[v]){
pare[u]=v
;
}else{
pare[v]=u
;
if(trank[u]==trank[v]){
trank[u]++
;
}
}
return;
}
//////////////////UnionFind木実装終わり//////////////////

int main() {
int N;
cin>>N;
vector<Edge> edge;
vector<Node> node;
REP(i,N){
int x,y;
cin>>x>>y;
Node n;
n.x=x; n.y=y; n.id=i;
node.push_back(n);
pare[i]=i;
trank[i]=0;
}


//x,yについて隣同士の辺を貼る
sort(node.begin(),node.end(),compx);
REP(i,N-1){
Edge e;
e.u=node[i].id;
e.v=node[i+1].id;
e.cost=node[i+1].x-node[i].x;
edge.push_back(e);
}

sort(node.begin()
,node.end(),compy);
REP(i,N-1){
Edge e;
e.u=node[i].id;
e.v=node[i+1].id;
e.cost=node[i+1].y-node[i].y;
edge.push_back(e);
}

//クラスカル法、コストの小さい辺から見て行って、
//閉路を作らなければ(無駄な辺を張らない)辺を張る。UnionFind木
sort(ALL(edge),compc);
long long ans =0;
REP(i,edge.size()){
Edge e =edge[i];
if(find(e.u)!=find(e.v)){
ans+=e.
cost;
unite(e.u,e.v);
}
}
cout
<<ans<<endl;

return 0;
}

 

E: Connected? - AtCoder Regular Contest 076 | AtCoder

R*Cマスの格子点で、井戸-家接続パズル。

解説みた後にも一番苦しめられた(知識が浅かっただけ)。

5分くらい考えて、ある組み合わせ(x1,y1),(x2,y2)について、両点が周上にある時だけを考えれば良さそうだなと思った。しかし、これらの点についての条件判定が思いつかなかった(ある点の組み合わせについて、他の全ての点の組み合わせが衝突しないかどうか判定しようとしてた)。

解説を読んで、stackとか使えばめっちゃ楽じゃんと納得。なるほど。

しかし幾度も提出してもRE...これは点の組み合わせを保存するのに、周上の格子点上の配列(2*(R+C))を用意してたので(四角形の左上を0として、時計回りで進んだ時の距離)、メモリが足りなかったらしい。4byte*4*10^8=1.6GB。mapとかunordered_mapも試してみたけど、(R+C)が10^8あるので間に合わない(検索がO(1)を超える)。pairを使って距離順でソートして解決した。

2時間くらい格闘してた...。

 

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;
int R,C,N;

/////長方形の辺上の点を始点からの距離に直す関数//////
int length(int x,int y){
if(y==0){ return x; }
if(x==0){ return 2*(R+C)-y; }
if(x==R){ return R+y; }
return 2*R+C-x;
}
//////////////////////////////////////////////

bool comp(pair<int,int>& p1,pair<int,int>& p2){
return p1.first - p2.first;
}

int main() {
cin>>R>>C>>N;
vector<pair<int,int>> border;

REP(i,N){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
if ((x1%R==0||y1%C==0)&&(x2%R==0||y2%C==0)){
//pair(始点からの距離、id)
border.push_back(pair<int,int>(length(x1,y1),i+1));
border.push_back(pair<int,int>(length(x2,y2),i+1));
}
}

sort(border.begin(),border.end());
stack<int> pos;
pos.push(-1);

//次の点とスタックのidが等しければ両方削除、違うならばスタックに重ねる
REP(i,border.size()) {
if(pos.top()!=border[i].second){
pos.push(border[i].second);
}else{
pos.pop();
}
}

if(pos.size()==1){
cout<<"YES"<<endl;
}else{
cout<<"NO"<<endl;
}
return 0;
}