予鈴

アウトプットとメモ書きの中間みたいな記事がたくさん出ます。

D - equeue

問題

N要素のdequeue Dが与えられる.push_back,push_front,pop_back,pop_frontを合計 K回行うことができる。
取り出した要素の和を最大化せよ。
atcoder.jp

解法

・push,popを貪欲に決めるのは難しいそう。例えば負の要素は取りたくないが、あえて取ることで後ろの正の要素を取れる。
・重要な考察として、正の要素を再度pushする必要はない。負の要素はpushすることで、和を大きくすることができるがこれは最後に行えば良い。
・これより、負の要素はコストを2払うことで、単に捨てる動作とすることができる
・DPで解ける。 dp[l][r][cost]として、 lは次に見る左の要素、rは次に見る右の要素
dp[l][r][cost] = max \left\{ \begin{array}{l} \begin{array}{lll} dp[l - 1][r][cost + 1] + v[l - 1] \end{array}\\ \begin{array}{lll} dp[l][r + 1][cost + 1] + v[r + 1] \end{array} \end{array}\right.
・追加する要素 v[l] < 0の場合は、コストを二つ使ってそのまま推移させればよい。
・ l == r の部分がうまく推移できなかったので、最後の部分で計算した。このあたりもっと良い方法がありそう

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define INF (sizeof(int) == 4 ? (int)1e9:(int)1e18)
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
signed main(){
    int n,k; cin >> n >> k;
    vector<int>v(n);
    for(auto & e : v) cin >> e;
    auto dp = vectors(n,n,k,-INF);
    if(k == 1 or n == 1){
        cout << max({v.front(),v.back(),0LL}) << endl;
        return 0;
    }
    dp[1][n - 1][k -  1] = v.front();
    dp[0][n - 2][k -  1] = v.back();
    if(v.front() < 0 and k >= 2){
        dp[1][n - 1][k - 2] = 0LL;
    } else if(v.back() < 0 and k >= 2){
        dp[0][n - 2][k - 2] = 0LL;
    }
    auto valid = [&](int l,int r){ return (l <= r and 0 <= l and  r <= n-1);};
    for(int l = 0; l < n; ++l){
        for(int r = n - 1; r >= 0; --r){
            for(int cst = 1; cst < k; ++cst){
                if( dp[l][r][cst] == -INF) continue;
                int now = dp[l][r][cst];
                if( valid(l + 1,r) )
                    cmax(dp[l + 1][r][cst - 1],now + v[l]);
                if( valid(l,r - 1) )
                    cmax(dp[l][r - 1][cst - 1],now + v[r]);
                if(v[l] < 0 and  valid(l + 1,r) and cst >= 2)
                    cmax(dp[l + 1][r][cst - 2],now);
                if(v[r] < 0 and valid(l,r - 1) and cst >=2)
                    cmax(dp[l][r - 1][cst - 2],now);
            }
        }
    }
    int ans = 0;
    for(int l = 0; l < n; ++l){
        for(int r = 0; r < n; ++r){
            for(int cst = 0; cst < k; ++cst){
                cmax(ans,dp[l][r][cst]);
                if(l == r){
                    cmax(ans,dp[l][r][cst] + (cst != 0 and v[l] > 0 ? v[l] : 0));
                }
            }
        }
    }
    cout << ans << endl;
}

Codeforces Round #579 (Div. 3) E. Boxers

問題文

n個の数字が与えられる。各数字に対して+1,-1を行う事ができる。uniqueな数字の数を最大化せよ。

考えていたこと

・AtCoderでやった問題だ！と思ったけど違った
・a_{i}は、a_{i} - 1またはa_{i} + 1の数を増やすことができる。a_{i}の数が3以上ならばどちらも増やせる。2だとどちらに増やせばいいかわからない。
・max(右詰め、左詰め)を試したがWA.

解法

・1のときは動かさないと思っていたのがだめだった。全部動かす。
・a_{i}をa_{i} + 1, a_{1} - 1に変化させたいとき、a_{i} + 1, a_{1} - 1ができるだけ0になっていれば良いので(推移できてuniqueな数字が増える)、できるだけ0を作る。
つまり、できるだけ右に詰めて、左に詰めて試す。
・Editorialの解法と全く違うけど、これ合ってるのかな…?

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define all(in) in.begin(), in.end()
signed main(){
    int n; cin >> n;
    vector<int>p(n);
    for(auto & e : p) cin >>e;
    vector<int>v(150002,0LL);
    for(auto e : p) v[e]++;
    for(int i = 1; i < v.size(); ++i){
        if(v[i] == 0)continue;
        if(i != 1 and v[i - 1] == 0)
            v[i - 1]++, v[i]--;
    }
    for(int i = v.size() - 2; i >= 1; --i){
        if(v[i] == 0) continue;
        if(v[i + 1] == 0)
            v[i + 1]++,v[i]--;
    }
    cout << accumulate(all(v),0LL,[](int a, int b){return a += ( b > 0);})
    << endl;
}

NAIST受験記

2020年度の情報科学区分の受験記です。

数多くの受験記に助けられたので、誰かの役に立つように記そうと思います。結果は合格でした。

 

試験内容

試験科目と配点は以下のようになっています。

以下で扱う試験範囲・内容は2019年8月時点のものです。ご注意ください。

 

書類審査50点、英語30点、数学30点、面接90点 (小論文を含む) となっており、200点満点の合計点で評価されます。

 書類審査

説明会に参加した際に、成績悪いと減点されるかもね〜みたいなことを聞いたような気がします。参考までに自分の成績は下の上 or 中の下でした。成績だけがものすごく影響する感じではないかもしれません…

英語

プレッシャーに弱いので、何度も失敗できるように1年ぐらい前から公開テストを数回受けました。使用した参考書は金のフレーズです。

リスニング、リーディングともに、英文の意味を完全に捉えることができるまで練習しました。

提出スコアは755です。600後半ぐらいあれば大丈夫らしいのですが、願書提出前までは何度もチャレンジできるので、積極的に受けることをおすすめします。個人的な意見ですが、公開テストはハマれば点が伸びます。

数学

基本的な問題が出題されると言われていますが、真面目に数学に取り組んでいなかったので1から勉強しました。参考書は指定の教科書二冊+代数の問題集です。

個人的にストラングの線形代数は教科書としては非常に良かったのですが、問題演習があまり好きではなかった（答えが部分的にしかない)ので、別で1冊買いました。

解析はラングの解析入門で取り組んでいました。内容のほとんどは数学Ⅲなので代数に比べて容易に取り組めました。

小論文

専攻や分野、卒業研究に取り組む時期によって大きく異なると思いますが、以下のようなスケジュールで取り組みました。

2~3月:英語の論文に慣れる&テーマ決め

4~5月:小論文作成

6月:推敲

小論文の構成は、研究背景+目的+NAISTで取り組みたいことです。卒業研究がB4から始まったので、具体的な手法や実験の結果などは書いていません。~~~みたいな問題があるため、こういうことをするとできそう。みたいな内容で書きました。

推敲:NAISTの先輩に推敲してもらう予定でしたが、願書提出の〆切1.5週間前までに完成できなかったため、指導教員の先生にお願いしました。的確な指導をいただくことができました。

有用性・実現性に関しては少し不安が残る小論文になりましたが、自分なりにベストを尽くせた小論文になったと思います。

試験当日

服装とか当日の様子とか

集合時間の1時間前に入試会場に到着して図書館で時間を潰していました。試験時間が午後だと、移動がめちゃくちゃに暑いので(特にスーツで受ける人)、制汗剤などの防暑対策をすると落ち着いて試験に臨めるかもしれません。あと、最寄り駅からバスの本数が少ないので、確認することをおすすめします、

殆どの人がスーツで男女比は9:1ぐらいでした。

数学

問題は非常に容易でした。(1次独立であるのを示す&商の微分)

ホワイトボードで問題を解いて説明をしている際に、小さなミスを指摘されましたが、完答でした。

面接官の方は非常に優しい感じでした。

面接

教室に入ると、志望予定研究室の先生を含めて三人の先生がおられました。覚えてきた原稿を喋ってる間、ほとんどの先生が資料に目を通している感じでした。

質問の全ては小論文に関するもので、色々突っ込まれました。

・~~以外にどいういう手法があるか知ってますか？

・時間的なオーバーヘッドは単に待てばいいんじゃない？

・~~の場合はどうするんですか？無理じゃない？

できる/できないは明確に答えることを意識しました。

 その他

OC・見学会について

OCには2度行きました。一度目は大学の下見で、二度目は小論文の内容の確認です。見学会には参加していません。

OCは研究室の雰囲気や先輩の研究内容等を知ることができるので、普通に参加しても楽しいです。5月のOCは願書提出日に近いので2月のほうが余裕を持って参加できるかもしれません…

役に立つかもしれないTips

・バスはICOCAが使えます。便利でした。

・ラングの解析入門ですが、原始関数が謎の形をしていることが多くこのサイトがとても役に立ちました。

・ストラングさんの解答です。英語&日本語訳とのバージョンが違いますが、ほとんど乗っているハズです。

・代数で使った問題集↓

Amazon CAPTCHA

D - 浮気予防

問題

atcoder.jp

考えていたこと

・ Pを問題文中での悪い虫の頂点集合、v_{0}を高橋くんとする。
・Pを含む部分グラフとv_{0}を含む部分グラフに分ける最小カットを考えればいいことがわかる。
・Pの要素をすべてsinkに置き換えて最大流を流す　→　”ログインできなくなる”という操作が再現できない。(具体的には、sample3が3になる)

正解

・やっぱり最小カット。Pとsinkをつなぐpathを仮定して最大流を流せば良い。
・よく考えると、”ログインできなくさせる”という操作はp \in Pにだけ行えば良い。
・p_{i}からsinkへのpathをカットすると、p_{i}をログインさせなくなるという操作が実現できる。
・問題をよく読むと頂点を削除することができないですねこれ…ずっとできるものだと思ってた。


解答

最小カット久々に使いました。

#include<bits/stdc++.h>
using ll  = long long;
using namespace std;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define INF (sizeof(int) == 4 ? (int)1e9:(int)1e18)
struct Edge{int to,cap,rev;};
class Dinic{//max flow
public:
    int n;
    vector<vector<Edge> >G;
    vector<int> level,iter;
    Dinic(int size): n(size),G(vector<vector<Edge>>(n)){};
    void add_Edge(int from, int to, int cap){
        Edge q={to,cap,int(G[to].size())};
        G[from].emplace_back(q);
        q={from,0,int(G[from].size()-1)};
        G[to].emplace_back(q);
    }
    void bfs(int s){
        level=vector<int>(n,-1);
        queue<int>q;
        level[s]=0;
        q.push(s);
        while(!q.empty()){
            int v=q.front();q.pop();
            for(auto &e :G[v]){
                if(e.cap>0&&level[e.to]<0){
                    level[e.to]=level[v]+1;
                    q.push(e.to);
                }
            }
        }
    }
    function<int(int,int,int)>dfs = [&](int v, int t, int f) -> int{
        if(v==t)return f;
        for(;iter[v]<G[v].size();iter[v]++){
            Edge &e=G[v][iter[v]];
            if(level[v]>=level[e.to]||e.cap<=0) continue;
            int d =dfs(e.to,t,min(f,e.cap));
            if(d>0){
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
        return 0;
    };
    int max_flow(int s,int t) {//from s to t,ford_fulkerson
        int flow=0;
        while(1){
            bfs(s);
            if(level[t]<0)return flow;
            iter=vector<int>(n);
            int f;
            while((f=dfs(s,t,INF))>0)flow+=f;
        }
    };
};
signed main(){
    int N,G,E;
    cin >> N >> G >> E;
    vector<int>p(G);
    for(auto & g : p) cin >> g;
    auto fl = Dinic(N+1);
    int sink = N;
    rep(_,E){
        int a,b; cin >> a >> b;
        fl.add_Edge(a,b,1);
        fl.add_Edge(b,a,1);
    }
    for(auto e : p)fl.add_Edge(e, sink,1);
    cout << fl.max_flow(0,sink) << endl;
}

AtCoderで水色になった話

この記事は完全にポエムです。有益なことは多分ありません。

 

AtCoderを初めて3年近くで水色になりました。　ﾔｯﾀｾﾞ

f:id:yebityon:20190421184245p:plain

水色になるまでやった*1ことは、他の方々が詳細に書いてくださってるので、失敗したことや心構え的なことを書きたいと思います。

1.コンテスト中に潜伏をしない

 某人類最強競プロerの戦略ですが、

chokudaiさんもおしゃっている通りで、少なくとも水色になるまでは潜伏戦術は取るべきではなかったです。(実体験) 

緑上位になってくると、ABCでレートを上げるにはC,Dをいかに早く通すかが肝になってくるので、最初にC,Dをときたい！という気持ちになりますが、自分の実力が十分についているなら、前から解いてもレートに反映されるはずです。

よく考えるとリスクが大きすぎます。(80分にDをsubmitしてWAとか)

 

2.解いた数  <<< 解いた問題

１日25問といた！どうだ！すごいだろ！！をやっていたのですが、実力が拮抗している問題を解くのも大事です。

何問といたか？という指標だけではダメかもしれません。 

とき直しとかおすすめです。

 

3.他人と比べすぎない

おそらくこれが最も大事でした。

競プロerの中には本当に賢い人が多く、自分が頑張って解いた問題が"いいえ"の一言で片付けられていたり、プログラミング始めたての人が、あっという間に自分のレートを抜かしていったりと、もしかして競プロに向いてないんじゃないかなと思うことが本当に多かったです。

レーティングはあくまでも自分の今の実力を表しているに過ぎません。自分がレートを伸ばしたければ精進すればいいし、満足しているなら無理に精進する必要もないと思います。

他人とのレーティングを比べて、自分を卑下しすぎるのは悪影響です。鼓舞するぐらいにしましょう。

競プロは競技だけど自分との競技です(?) 

 

*1:僕はdアニメストアに契約して、デアラと小林さんちのメイドラゴンと青豚を見ました。

D - Fennec VS. Snuke

問題文

atcoder.jp

解き直すと別の解法で解けたので書きます。

解法

ゲームには貪欲法が存在し、v_{1}からv_{N}に向かう頂点を埋めていくのが最適です。
与えられるグラフは木なので、任意の頂点 u,vに関して、 path_{u,v}がただ一つ存在します。
したがって、pathに含まれる頂点のうちどれがv_{1}に含まれるか、v_{N}に含まれるかを計算します。
後はv_{1},v_{N}にくっついている頂点を数えて数を比較すればどちらが勝つかわかります。

#include<bits/stdc++.h>
using ll  = long long;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define all(in) in.begin(), in.end()
using namespace std;
signed main(){
    int n; cin >> n;
    vector<vector<int>>edge(n);
    rep(i,n-1){
        int s,t; cin >> s >> t;
        edge[--s].push_back(--t);
        edge[t].push_back(s);
    }
    vector<bool>visit(n,false);
    vector<bool>ispath(n,false);
    function<bool(int)> dfs = [&](int v){
        visit[v] = true;
        bool flag = (v == n-1);
        for(auto nv : edge[v]){
            if(visit[nv])continue;
            if(dfs(nv))flag = true;
        }
        return ispath[v] = flag;
    };
    dfs(0);
    // all vertex was checked.
    int margin = accumulate(all(ispath),0LL) - 2;
    margin = margin / 2 + margin % 2;
    vector<int>grid(n,-1);
    function<int(int,int)>cntup = [&](int v, int atrb){
        int res = 1;
        grid[v] = atrb;
        for(auto nv : edge[v]){
            if(grid[nv] != -1)continue;
            if(ispath[nv] == false or atrb == 1) res += cntup(nv,atrb);
            else if(ispath[nv] and margin > 0 )--margin,res += cntup(nv,atrb);
        }
        return res;
    };
    int f = cntup(0,0), s = cntup(n-1,1);
    assert(f + s == n);
    cout << (f > s ? "Fennec" : "Snuke") << endl;
}

Codeforces Round #544 (Div. 3)　D. Zero Quantity Maximization

問題

解き直すと一瞬で通って悔しすぎるので、ここで供養しようと思います。
codeforces.com

解法

問題文に与えられた式を整理すると、
d = \frac{-b[i]}{a[i]}

任意の正の有理数は、ただ一つの既約分数を用いて表せるという性質を用いる。
mapのkeyを
b[i] / gcd(b[i],a[i]) + yebityon + a[i] / gcd(b[i],a[i])
のような文字列としてカウントアップしていけば良い。
ただし、
b[i] <0 \land a[i] < 0　の時はdは負になり、
b[i] >0 \land a[i] < 0　と b[i] <0 \land a[i] >0は値的には等しくなるので、注意。
b[i] == 0 \land a[i] == 0の時は任意のdに対して0になるので、別途数えてあとで足すと良い。

#include<bits/stdc++.h>
using ll  = long long;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define all(in) in.begin(), in.end()
#define MP make_pair
#define INF (sizeof(int) == 4 ? (int)1e9:(int)1e18)
#define EPS 0.0000000001
using namespace std;
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
using ld  = long double;
template<class T> T gcd(T a,  T b) {return b ? gcd(b, a % b) : a;}
template<class U> U lcm( U m, U n ){if((0LL == m )||( 0LL == n ))return 0; return ((m / gcd(m, n)) * n); }
signed main(){
    int n;
    cin >> n;
    vector<int>a(n);
    vector<int>b(n);
    for(auto& e : a) cin >> e;
    for(auto& e : b) cin >> e;
    map<string,int>mp;
    int res = 0;
    for(int i = 0; i < a.size(); i++){
        if(a[i] == 0 and b[i] == 0){
            res++;
            continue;
        }
        if(a[i] == 0)continue;
        int div = gcd(abs(a[i]),abs(b[i]));
        if((long double)b[i] * -1 / a[i]  >= 0){
            // d >= 0
            mp[to_string(abs(b[i]) / div) + "yebityon!" + to_string(abs(a[i])/div)]++;
        }else{
            // d < 0
            //分子を 負　にすることに統一
            mp[to_string(-1 * abs(b[i]) / div) + "yebityon!" + to_string(abs(a[i])/div)]++;
        }
    }
    int ans = 0;
    for(auto itr : mp){
        cmax(ans, itr.second);
    }
    cout << ans + res << endl;
    
}