予鈴

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

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;
    
}

A. Technogoblet of Fire の日本語訳

問題文が理解不能すぎたので訳しました。間違ってたらコメントください。
というか訳しても意味がよくわからないけど
codeforces.com

m coderトーナメントがもうすぐ開催されます。　m校の学校が参加し、各校につき1人の選手だけが参加することができます。

すべての参加者の合計はn人です。トーナメントの前に、すべての学生は名前と自分の学校をTechnogoblet of Fireに入れました。
Technogobletは各学校で最も強い学生を選びます。

Arkadyは特定のk人の生徒がTechnogobletによって選ばれることを望んでいるハッカーです。
残念ながら、全員が自分の学校で最強であるわけではありません。
しかし、Arkadyは、新しい学校名を作り上げて、生徒の学校名を、作り上げた学校名に置き換えることができます。
あなたはそれぞれの作り上げた学校名を繰り返し使用することはできません。
Technogobletは作り上げた学校の名学校で最も強い生徒を選びます。

あなたは各生徒の力と所属している学校を知っています。
K人の生徒が選ばれるために必要な最小の学校数を計算してください。

設定が謎すぎるし、Technogobletがなにかわからないし、何より k Chosen Ones*1 がわからなさすぎる。

*1:特定の人って意味らしい。変にcapitalにするのやめて

E-Union

Problem

atcoder.jp

Solution

・愚直解は、 iに対し、各0...a_i個使ってシュミレーションが考えられるが、計算量的に間に合わない。
・配列dpを次のように定義する
dp[i][j] := 数字 i を j 個使ったときの場合の数
・更新は
dp[i][x + y] = dp[i-1][x] + dp[i][2*y]

・更新した値をもう一度更新しないように、後ろから更新していかないと行けない。
・特に、 y == 0の場合は更新しないこと。
i番目の数字をいくつ使用しても、i-1番目までの計算結果は繰り返し利用できるので、そのあたりに着目するとDPに到達できるかも…？

#include<bits/stdc++.h>
using ll  = long long;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
auto dp = vector<vector<int>>(500,vector<int>(3000,0LL));
signed main(){
    int t;
    cin >> t;
    vector<int>v(t);
    for(auto& e : v) cin >> e;
    rep(i,v.size()){ fill(dp[i].begin(),dp[i].begin() + v[i] + 1,1LL);}
    int mod = 1000000007;
    rep(i,dp.size() - 1){
        dp[i][0] = 1;
        if(i == 0)continue;
        for(int j = dp[i].size(); j >= 0;--j){
            if(dp[i][j] == 0 )continue;
            for(int k = dp[i-1].size() - 1; k >= 1; --k){
                if( k % 2 or j + k/2 >= dp[i].size())continue;
                if(dp[i-1][k] == 0)continue;
                dp[i][k/2 + j] += dp[i][j] * dp[i-1][k];
                dp[i][k/2 + j] %= mod;
            }
        }
    }
    int ans = 0;
    for(int i = 0;  i < dp.size(); ++i){
        ans += dp[i][1];
        ans %= mod;
    }
    cout << ans << endl;
}

E-Union

Problem

atcoder.jp

Solution

・愚直解は、 iに対し、各0...a_i個使ってシュミレーションが考えられるが、計算量的に間に合わない。
・配列dpを次のように定義する
dp[i][j] := 数字 i を j 個使ったときの場合の数
・更新は
dp[i][x + y] = dp[i][x] + dp[i-1][2*y]

・更新した値をもう一度更新しないように、後ろから更新していかないと行けない。
・特に、 y == 0の場合は更新しないこと。
i番目の数字をいくつ使用しても、i-1番目までの計算結果は繰り返し利用できるので、そのあたりに着目するとDPに到達できるかも…？

#include<bits/stdc++.h>
using ll  = long long;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
auto dp = vector<vector<int>>(500,vector<int>(3000,0LL));
signed main(){
    int t;
    cin >> t;
    vector<int>v(t);
    for(auto& e : v) cin >> e;
    rep(i,v.size()){ fill(dp[i].begin(),dp[i].begin() + v[i] + 1,1LL);}
    int mod = 1000000007;
    rep(i,dp.size() - 1){
        dp[i][0] = 1;
        if(i == 0)continue;
        for(int j = dp[i].size(); j >= 0;--j){
            if(dp[i][j] == 0 )continue;
            for(int k = dp[i-1].size() - 1; k >= 1; --k){
                if( k % 2 or j + k/2 >= dp[i].size())continue;
                if(dp[i-1][k] == 0)continue;
                dp[i][k/2 + j] += dp[i][j] * dp[i-1][k];
                dp[i][k/2 + j] %= mod;
            }
        }
    }
    int ans = 0;
    for(int i = 0;  i < dp.size(); ++i){
        ans += dp[i][1];
        ans %= mod;
    }
    cout << ans << endl;
}

NStextFieldをNSMenuに埋め込みたい。

この記事は備忘録です。

NStextFieldをNSmenuに埋め込んで、上のstatus barから入力受け取れたらいいんだけどな〜って思ってたんですが、どうやらバグ*1でできないらしいです。

具体的には、一度focusが離れると入力を受付なくなるらしい…

 

なにか良い解決策があれはご教示ください。

 

類似の質問がstack overflowにいくつかありました。

stackoverflow.com

stackoverflow.com

stackoverflow.com

*1:2019/2月現在