2019-03-04

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にするのやめて

2019-03-01

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

2019-03-01

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]$

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

2019-02-04

NStextFieldをNSMenuに埋め込みたい。

この記事は備忘録です。

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

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

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

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

stackoverflow.com

*1:2019/2月現在

2019-01-19

数式(?)を逆ポーランド記法に変換して計算する。

面白そうだな〜と思っていたので、実装しました。
要するに電卓です。
10+4*(10/2+7)/2+2+(3+(2+2))　←こういうのを計算してくれます。負数と小数点には対応してません。
楽しかったので自己満足記事です。verifyはしてないので、使用は自己責任でお願いします。
バグがあれば教えてください。


#include <iostream>
#include <string>
#include <vector>
#include <stack>

using namespace std;

bool isOp(string c){return c == "+" or c == "*" or c == "-" or c == "/" or c == ")" or c == "("; }
bool isOp(char c){return c == '+' or c == '*' or c == '-' or c == '/';}
bool isNum(char c){return '0' <= c and c <= '9';}
bool isNum(string s){return !(isOp(s));}

auto  parser(string s){
    string num = "";
    vector<string>token;
    for(auto c : s){
        if(isNum(c)){
            num.push_back(c);
        } else {
            if(not num.empty()){
                token.push_back(num);
                num.clear();
            }
            token.push_back(string() + c);
        }
    }
    if(not num.empty()) token.push_back(num);
    return token;
}
auto OperandPriority(string lower,string higher){
    return ((lower == "+" or lower == "-") and (higher == "*" or higher == "/")) ;
}
auto constructRPN(vector<string>token){
    //逆ポーランド記法の文字列配列を生成。
    stack<string>st;
    vector<string> buffer;
    for(auto str : token){
        if(isNum(str)){
            buffer.push_back(str);
        } else {
            if(str  == ")"){
                while(st.top() != "("){
                    buffer.push_back (st.top());
                    st.pop();
                }
                assert(st.top() == "(");
                st.pop();
            } else if(str == "(" or st.empty()){
                st.push(str);
            } else if(OperandPriority(st.top(),str)){
                st.push(str);
            } else {
                while(not st.empty() and st.top() != "(" and !OperandPriority(st.top(),str)){
                    buffer.push_back(st.top());
                    st.pop();
                }
                st.push(str);
            }
        }
    }
    while(not st.empty())buffer.push_back(st.top()),st.pop();
    return buffer;
}
int execute(vector<string> l){
    stack<int>num;
    for(auto s: l){
        if(isNum(s)){
            num.push(stoi(s));
        } else {
            int res = 0;
            int val1 = num.top();num.pop();
            int val2 = num.top();num.pop();
            char c = s.front();
            switch (c) {
                case '+':
                    res =  val1 + val2;
                    break;
                case '*':
                    res =  val2 * val1;
                    break;
                case '-':
                    res =  val2 - val1;
                    break;
                default:
                    res =  val2 / val1;
                    break;
            }
            num.push(res);
        }
    }
    return num.top();
}
int main() {
    string s; cin >> s;
    auto token = parser(s);
    auto Literal =  constructRPN(token);
    for(auto s: Literal)cout << s; cout << endl;
    cout << execute(Literal) << endl;
}

参考

fmypage.qcweb.jp
7ujm.net

2018-12-30

D - Number of Amidakuji

問題

atcoder.jp

考えていたこと

・ $dp$ まではすぐにたどりつけたが、「正しいあみだくじ」の本数を求める方法がわからず。
・ $(i,j)$ から $(i,j+1),(i+1,j+1),(i-1,j+1)$ に推移できる。

解法

・ $(i,j)$ 番目にいるときの、あり得るあみだくじの場合の数を計算する。
・当たり前だけど、あみだくじの状態が決まれば推移先は一つに決まる。(条件が厳しくなっている。)
・なんちゃってdynamic_bitsetを作りました。

#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;
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); }
int MOD = 1000000007;
class dynamic_bitset {
private:
    long long bit;
    string sbit                = "";
    unsigned long long bitsize = 0;
    
public:
    dynamic_bitset(int _bit) : bit{_bit} {
        for (int t = 1, mask = 2; bitsize == 0; t++, mask *= 2) {
            if (mask - 1 >= bit) bitsize = t;
        }
        for (int i = 0; i < bitsize; i++) {
            sbit = ((bit >> i & 1) == 1 ? "1" : "0") + sbit;
        }
    }
    dynamic_bitset(int _bit, int bitrange) : bit{_bit}, sbit{} {
        for (int t = 1, mask = 2; bitsize == 0; t++, mask *= 2) {
            if (mask - 1 >= bit) bitsize = t;
        }
        for (int i = 0; i < bitrange; i++) {
            sbit = (i < bitsize and ((bit >> i & 1) == 1) ? "1" : "0") + sbit;
        }
    }
    auto test(int _idx) {
        assert(_idx < sbit.size() && "index  out of range");
        return sbit[_idx] == '1';
    }
    void set(int _idx) {
        assert(_idx < sbit.size() && "findex out of range");
        sbit[_idx] = '1';
    }
    auto size() { return sbit.size(); }
    bool isAll() {
        return accumulate(sbit.begin(), sbit.end(), true,
                          [](bool r, char c) { return r && c == '1'; });
    }
    bool none() {
        return accumulate(sbit.begin(), sbit.end(), true,
                          [](bool r, char c) { return r && c == '0'; });
    }
    auto to_string() { return sbit; }
};
signed main(){
    int h,w,k;
    cin >> h >> w >> k;
    auto dp = vectors(300, 300,0LL);
    dp[1][1] = 1;
    for(int j = 1; j <= h; j++){
        for(int i = 1; i <= w; i++){
            for(int bit = 0; bit < (1 << (w - 1));bit++){
                auto db = dynamic_bitset(bit,w-1);
                bool isValid = true;
                rep(i,(int)db.size() - 1){
                    if(db.test(i) and db.test(i+1))
                        isValid = false;
                }
                if(!isValid)continue;
                if(i+1 <= w and db.test(i-1)){
                    dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j]) % MOD;
                } else if(i-1 >= 1 and db.test(i-2)){
                    dp[i-1][j+1] = (dp[i-1][j+1] + dp[i][j]) % MOD;
                } else {
                    dp[i][j+1]   = (dp[i][j+1]   + dp[i][j]) % MOD;
                }
            }
        }
    }
    cout << dp[k][h+1] << endl;
}

2018-12-10

D - Christmas

問題

非負整数 $N,X$ が与えられる。2つの文字 $P,B$ に対して、N番目の文字列を
$S_N := B + S_{N-1} + P +S_{N-1} + B$ とする。
下から $X$ 文字に含まれる文字 $P$ の数を求めよ。
beta.atcoder.jp

解法

・各 $n$ に対して $P$ の数と含まれるすべての文字の数を定義に従って前計算する。
・再帰関数で含まれる文字数を計算することができる。
・ $x \geq S_{n-1} + 2$ のとき、 $S_{n}$ のうち下半分の $S_{n-1}$ と中間の $P$ は完全に答えに含まれる。
・残った数、つまり $x - S_{n-1} - 2$ の場合と $x < S_{n-1} + 2$ の場合はわからないので次数を下げて投げる。
・ $i == 0$ のときはこれ以上次数を下げることができない。定義からレベル0はPのみで構成されるので、xが0より大きい場合のみ1を返す。

・これすき、今度はコンテスト中にときたい。

#include<bits/stdc++.h>
using ll  = long long;
#define int ll
using namespace std;
signed main(){
    vector<int>dp(51,1LL),dp2(51,1LL);
    int n,x; cin >> n >> x;
    for(int i = 1; i < dp.size();++i){
        dp[i] = dp[i-1] + dp[i-1] + 3;
        dp2[i] = dp2[i-1] + dp2[i-1] + 1;
    }
    function<int(int,int)>cal = [&](int i,int x) -> int{
        if(x == 0){ return 0;    }
        if(i == 0){ return x > 0;}
        return (x >= dp[i-1] + 2 ? dp2[i-1] + 1 + cal(i-1,x-dp[i-1]-2) : cal(i-1,x-1));
    };
    cout << cal(n,x) << endl;
}

予鈴

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

A. Technogoblet of Fire の日本語訳

E-Union

Problem

Solution

E-Union

Problem

Solution

NStextFieldをNSMenuに埋め込みたい。

数式(?)を逆ポーランド記法に変換して計算する。

参考

D - Number of Amidakuji

問題

考えていたこと

解法

D - Christmas

問題

解法