PCK2018予選 参加記

JOI本もSuperConも書くぞって言って後回しにしてたら忘れたので早いところ書いてしまおう.
ぼく(@Sugar_Dragon5)と弊部会長の二人でチーム「こんぺいとう」として参加.

事前準備

  • 相方に「出ようぜ」ってお願いする
  • 「隣でスマブラしててもいいなら出るよ」と言われたので申し込む(もちろんさせるつもりはない
  • 3日前くらいに初めて二人でバチャをするがボーダー寸前でバグらせて予選落ち.なえる
  • 前日にライブラリを印刷

当日

  • 朝起きる
  • 飯食べる
  • 電車に乗る
  • 1限を聞き流す
  • 2限を真面目に聞く
  • 3,4限は真面目に聞くも何言ってるかよくわかんなくてつらい
  • 飯は時間がないのでコンビニ
  • 辛いラーメン買ったら辛くて辛い
  • 部室のデスクトップPCで出る予定だったが開始3分前くらいにPCが不調に
  • 急遽僕のPCで出ることに
  • 準備してたら始まったのでそのまま1問目を解く
  • 慎重に確認してから提出してAC
  • 問題を印刷
  • 相方に続きを解いてもらいながら5問目くらいを読む
  • 何もわからん
  • 相方が2問目3問目をAC
  • 5問目何もわからんので相方を手伝う
  • 4問目相方が読んでる途中に見えるので書く
  • WA
  • なにかに気づいて出し直す
  • WA(大戦犯)
  • 片方固定とかアホくさくなったので愚直に100回くらい回す
  • AC
  • 気を取り直して5問目へ
  • やるをやればできそうだがスマートな解法がないか模索
  • 相方が愚直でいいっていうので実装したら確かに実装めっちゃ軽かった
  • AC
  • 相方から6問目の概要を聞く
  • ちょっと難しそうなので真面目に考察する
  • どうせswapするところだけ確認したいので,sortedとの差が何個あるか数えておけば良さそう
  • 書いたら通る
  • 7問目を読む
  • 読み終わったので実装を始める(6よりやるだけ
  • バグる
  • 直ったので提出
  • 通る
  • 8問目の概要とそれっぽい貪欲らしきものを聞く
  • あー後ろからpriority_queueねってなる
  • 書く
  • WA
  • オーバーフローやんけ(unsignedなら通りますよって何なんだこちとら桁数しか数えとらんわ
  • AC
  • 9問目の概要を聞く
  • 幾何やったことないので飛ばす
  • 10問目を聞く
  • どーせ木dp
  • これ全方位木dpってやつだろ書いたことないわ
  • 11問目を聞く
  • よくわからないので幾何をする決意をした
  • 9問目のお絵かきをすると1点固定傾き全探索をmapでえいが思いつく
  • 誤差こえ~~
  • 分数かくか~~ってなる
  • pairをgcdで割る関数書くだけでいいので楽ちん
  • 書けたので投げる
  • AC
  • この時点でなんか順位表のめちゃくちゃいい位置に居た
  • 4のペナが痛いな~~って話をしながら次を考える
  • 10は多分知らないやつなので11を頑張ることにする
  • そのへんに落ちてる丸いものを回してみると相方がなんか思いついた
  • 遅延セグ木でえいえいってすると良さそうな気がする
  • 具体的に何すればいいかよくわからんから詰めていくが集中が切れてきてて頭がまわらない
  • 気づいたら順位表が凍結された.6位タイ
  • 半ばお祈りフェーズに入る
  • とりあえずセグ木を写して,相方に考察を続けてもらう
  • セグ木ライブラリ,コピペ用だから写すのだるい(短いやつ作っとこう)
  • これ間に合わないなって確信してギブアップ
  • 持ち込み資料であるところの邪神ちゃんドロップキックを読んでいたらコンテスト終了

結果

9完3WAで凍結時点6位タイ(時間考慮で8位)
某氏のツイートによると判明しているだけでも2チームに抜かれているので,あと1チーム抜かれてたら負け
4問目の2ペナがあまりにも大きかった.反省
ただ青と緑のペアにしては善戦できたんじゃないでしょうか

AtCoder Beginner Contest 109 参加記

宣言されてたとおりの簡単回

A問題 ABC333

問題

A - ABC333

解法

やる

B問題 Shiritori

問題

B - Shiritori

解法

やる.被りがあるかどうか調べるのに無思考でsetを書いたが二次元forを回したほうが僕のタイピング速度だと明らかに実装早いので反省(まあ誤差だが
追記:setのコンストラクタにvectorイテレータ渡すやつ使うともっとシンプルにかける。

C問題 Skip

問題

C - Skip

解法

距離の約数じゃなきゃいけないのでgcd

D問題 Make Them Even

解法

操作列を求められてる時点で最大値はめっちゃ簡単に求まりそうで,実際いい感じにやると奇数は1つ以下にできそうだとわかる.
どうすればいいかを考えるととりあえずその場しのぎで偶数にしていく感じの操作が思いつき,実際これを書くとうまくできてるのでおわり

結果

f:id:SugarDragon5:20180908225708p:plain
15分14秒全完12位.タイムも順位も自己ベストだし,初めての1ページ目なので嬉しい.
Dを最初に解く遊びをしたが,Dが解けた頃には皆ABCは解き終わってるし,1位に至ってはすでに全完してたりするので精神的にとっても良くない.だめ

AtCoder Regular Contest 102 参加記

今回僕が解けたCとDは解法を言われるとそれはそうとなるので,ACまでの試行錯誤を書いておく

C問題 Triangular Relationship

考察

  • よくわからんけど愚直はもちろんTLE.O(N\log N)までしかだめ
  • 1つ決めると他2つが決まるとか?
  • そういう訳ではなさそう…?
  • 数えたいものの特徴は?
  • \bmod kが同じやつ同士っぽい
  • ただ何でもいいわけじゃなくて,2倍してmod k取ると0になるやつだけ
  • mod決めちゃえばそれの個数は求まるし,重複OKなので3乗するだけ
  • 実装(こんがらがってて1WAした)

むずかしかった

解法

2x\equiv 0\pmod Kとなるすべてのxについて,[1,N]に何個存在するか求めその3乗を答えに足す.

D問題 All Your Paths are Different Lengths

考察

  • とりあえず実験
  • 適当に辺を足していってもある程度作れそうだけど,頂点と辺の制約的に賢いことしないとダメそう
  • 無駄な枝分かれは意味がないので基本は1本道にしたい.
  • 多重辺
  • 2進数とか良くね????
  • 実験するとL=2^nn+1頂点と2(N-1)辺で表現できる

f:id:SugarDragon5:20180901234759j:plain

  • このままだと2の累乗しか表現できないし最大で21頂点必要になってダメそう
  • n頂点でL=2^nできないの?
  • できた

f:id:SugarDragon5:20180901235151j:plain

  • 1つ頂点が減らせた.2進数で考える+αのこの方針で20頂点に収めることは可能そうだし,もう少し考察してみよう
  • 2の累乗以外を表現できるように辺を足す方法を考える
  • とりあえず2個目のやつよくわからんし1個目のやついじろう
  • Lを2進数で見たときに1の桁に対して操作が必要
  • 辺の制約的に追加できるのは各桁1本
  • それぞれの操作で増やしたいパスの個数を満たすところはどこだ
  • 桁の回数行ったところから辺を引くと欲しい数だけ増えそう
  • 他に影響してほしくないのでゴールに直接つなごう
  • 重みはいい感じの数が出るようにしてみる
  • できた

f:id:SugarDragon5:20180902000514j:plain

  • 頂点数[\log_{2}L]+1で表現できた
  • 2^{20}未満なので20個でできそう
  • うまくいきそうなので実装する(きびしい)
  • AC

解法

[\log_{2}L]+1点の2進グラフ(画像1枚目のやつ)に適切な辺を適切な数値で足していく

結果

f:id:SugarDragon5:20180902001054p:plain
71分2完1ペナで201位
f:id:SugarDragon5:20180902001156p:plain
まあまず水色に落ちないところ(パフォ663で水)まで上がったので嬉しい.
2回連続で700を通せたのが良かった.

AtCoder Regular Contest 101 参加記

1ヶ月ぶりくらいかつ8月最後のrated,久しぶりのコンテストでめちゃくちゃ緊張してた

C問題 Candles

問題

C - Candles

解法

sortedなので全部の[x,x+m)について距離を求めていけば良い.O(N)
デバッグ出力は消しましょう(何回目だおい

D問題 Median of Medians

解法

  • 素数Nの数列の中央値は,x以上の値がN/2個ある数のうち最小のもの

→二分探索で探せる形

  • 区間の中央値がx以上であるということは,その区間に存在するx以上の要素の個数がx未満の要素の個数より少なくないということ.

x以上のものを+1,x未満のものを-1として累積和を取ると(区間のx以上の要素数)-(区間のx未満の要素数)が求まる
ここまででオーダーをO(N^2log N)に落とすことができた.(まだTLE)

  • 区間(区間のx以上の要素数)-(区間のx未満の要素数)が非負であればよいので,各終端についてそれより前でそれ以下のものを探せば良い.これはBITで可能.

ここまでやるとオーダーがO(N log^2N)になって通る.

結果

f:id:SugarDragon5:20180825231520p:plain
青コーダーになりました.まじで時間かかった.嬉しい

yukicoder No.727 仲介人moko

概要

品物を売りたい人と買いたい人がそれぞれN人いる.
売りたい人は来ると品物を1つ売り,買いたい人は売っているものからなにか1つ買う.
売買の組み合わせは何通りあるか

解法

愚直DPしか思いつかないしそのままだとOEISに出てこなくて(階乗で割ると出るらしい)辛かった.

  • 品物を買いたい人それぞれについて誰の品物を買うか決める([tex;N!]通り)
  • 売る人買う人の配置を考える(1\times 3\times 5\times ...\times (2N-1)通り) ※詳しくは下で
  • 配置にペアを当てはめる(N!通り)

なので,1\times 3\times 5\times ...\times 2N-1 \times (N!)^2とかになる.

配置について

配置の場合の数は1\times 3\times 5\times ...\times (2N-1)になるらしい.これは2N頂点の完全グラフの完全マッチングの個数らしいがよくわからないのでなぜこうなるかまとめてみる.
まずN=1は明らかに1通り.
N=2はこんな感じで
f:id:SugarDragon5:20180825000737p:plain
N=1の最初とそれに対応するどこかに挿入したものなので,a_2=a_1\times 3
N=3も,
f:id:SugarDragon5:20180825001035p:plain
みたいな感じにN=2の最初と対応する箇所に挿入したもので,a_3=a_2\times 5
こんな感じで以下のような漸化式が立って
 a_1=1,a_{n+1}=a_n\times (2n-1)
これを解けばいい.

TopCoder SRM 621 Div1 Easy RadioRange

概要

(0,0)から半径r (0\lt r\lt z)の電波を飛ばす.
n個の街があり,i個目は中心(X_i,Y_i)で半径R_iの円形である.
すべての街について電波が全く届かないか完全に届くかのどちらかであるようなzの範囲の割合を求めよ.

解法

余事象を考えると,街iに対し良くない範囲は[max(0,sqrt(X_i^2+Y_i^2)-R_i,min(sqrt(X_i^2+Y_i^2)*R_i,z)]である.
これを各街についてとってそれらをマージし,割合を求めれば良い.

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) for(int i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<int,int>;
using PP=pair<int,P>;
using Pl=pair<ll,ll>;
using PPl=pair<ll,Pl>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;
class RadioRange{
public:
    double dist(double x,double y){
        return sqrt(x*x+y*y);
    }
    double RadiusProbability(vi x,vi y,vi r,int z){
        using Pd=pair<double,double>;
        int n=x.size();
        vector<Pd> vec;
        REP(i,n){
            if(dist(x[i],y[i])-r[i]>z){
                continue;
            }
            vec.pb(Pd(max(0.0,dist(x[i],y[i])-r[i]),min(1.0*z,dist(x[i],y[i])+r[i])));
        }
        while(1){
            bool f=false;
            vector<Pd> t;
            sort(all(vec));
            int m=vec.size();
            REP(i,m){
                int r=i;
                double ma=vec[i].se;
                while(r+1<m&&vec[r+1].fi<vec[r].se){
                    r++;
                    f=true;
                    chmax(ma,vec[r].se);
                }
                t.pb(Pd(vec[i].fi,ma));
                i=r;
            }
            vec=t;
            if(!f){
                break;
            }
        }
        double res=0.0;
        REP(i,vec.size()){
            res+=vec[i].se-vec[i].fi;
        }
        return 1.0-res/z;
    }
};

TopCoder SRM620 Div1 easy Easy PairGame

概要

正の整数の組(p,q)に対して次の操作を考える.

  • (p+q,q),(p,p+q)のどちらかに置き換える.

この操作を何回か繰り返した結果(a,b)にも(c,d)にもすることができる(x,y)のうちx+yの最大値を求めよ.

解法

(x,y)になるのは,x\lt yのとき(x,y-x)x\gt yのとき(x-y,y)なので(a,b),(c,d)に対して逆回しして得られるものを調べる

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) for(int i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<int,int>;
using PP=pair<int,P>;
using Pl=pair<ll,ll>;
using PPl=pair<ll,Pl>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;
class PairGame{
    set<P> f(int x,int y){
        set<P> res;
        queue<P> que;
        res.insert(P(x,y));
        que.push(P(x,y));
        while(que.size()){
            P p=que.front();que.pop();
            if(p.fi>p.se){
                p.fi-=p.se;
            }else{
                p.se-=p.fi;
            }
            if(!p.fi||!p.se){
                continue;
            }
            if(!res.count(p)){
                res.insert(p);
                que.push(p);
            }
        }
        return res;
    }
public:
    int maxSum(int a,int b,int c,int d){
        set<P> p=f(a,b);
        set<P> q=f(c,d);
        int ans=-1;
        for(auto itr:p){
            if(q.count(itr)){
                chmax(ans,itr.fi+itr.se);
            }
        }
        return ans;
    }
};