2017-04-07

Kansai Camp　参加記

3月26~3月29日にかけて、KMC(京都大学マイコンクラブ)とNAIST、RiPProで行った合同合宿の参加記です。

全部書いてると長くなるので、コンテストの内容とかはおいおい書くつもりです。

1日目
2日目
3日目
最終日
まとめ

1日目

集合場所も知らず、準備も全くせずに11時頃に起きました。幸い15時*1集合だったので間に合いました…が、

迷子のフレンズです(誰か助けて)
— yebi (@sigsigma19) 2017年3月26日

集合場所で誰にも合流できずに15分ぐらい死んでました。

なんとかKMCの方と合流できたあと、民宿に移動　→　自己紹介　という流れに。

自己紹介で合宿参加者のAtcoderの平均レートが1600とかいう異次元の数値*2であることが判明し、人権を喪失しました。

その流れでコドフォ(2時間ぐらい)→(めっちゃ豪華な)晩御飯→ABC

久々のコドフォだったので、(途中コンテスト以外の問題を解いてた)　色々忘れてました。

ちなみに、ABCは全完した人からお風呂に入れるみたいなノリがありました。*3

2日目

朝風呂を無事ACして始まりました。　朝ごはんがめっちゃ美味しかったです。

その後は　コドフォ→お昼→ARC →ARC →晩御飯→復習→コドフォ

という流れでした。

まぁコンテストは最下位かそれぐらいでした。悲しかった。

ただ、解いた問題で自分が知ってるアルゴリズムの問題はその日のうちに通せたのが唯一の進捗です。

休憩にcodefightsとかやってました。

最後のコドフォでは無限にWAを生産してました。

C問題のWA生成担当してました。
— yebi (@sigsigma19) 2017年3月27日

コドフォのサンプル弱すぎでは？？

この日が一番コードを書いた気がします。

3日目

朝風呂ACしました。朝ごはんに２日連続で卵かけご飯が出たのが印象的でした。

この日は ARC（でチームを決める）　→　コドフォ（チーム戦）

みたいな流れです。

ARCの順位は…(察し)。典型DPを再帰で書いてTLEしたり、嘘解法を頑張って実装したりして悲しい事になりました。反省してます。

コドフォは４時間セットで、T.M先輩としょラーさん、KMCの方と４人でチームを組みました。

しょラーさんが解けそうな問題を僕に投げてくれて、２問ぐらい通しました。

ちなみにjudgeの時、WAしたら土下座しようと思ってました。

他の問題はさっぱりで、なんとか解こうとしたものの敗北。

4時間コンテストは流石に辛かったです。

晩御飯を食べた後はひたすら復習をしてました。（主にARC）

KMCの同年代のNさん*4に

yebityon.hatenablog.com

こういう解き方や、コンテストの別解だけではなく、セグメントツリーのライブラリや使い方など、本当に色々教えてもらいました。

とても勉強になりました、ありがとうございます。

余談ですが、けものフレンズの最終回を見ました。ハッピーエンドで終わった（？）ようで良かったです。

最終日

最終日は、競プロか周辺を散策するか迷って結局周辺を散歩しました。

近くの山を散歩したり、足湯に入って新歓の話やプログラミングの話をしてました。

合宿の様子です。
ご査収ください pic.twitter.com/oO3rRhxkNH
— yebi (@sigsigma19) 2017年3月29日

足湯がめっちゃ気持ちよかったです。

まとめ

正直なところ、初日は合宿のレベルが高くて、自分は場違いでは？と思うこともありましたが、参加してよかったと思っています。

実装力もアルゴリズム力も無い僕ですが、周囲の方々のレベルが高い&競プロだけをする環境の中で、色々と感じることもあったし、何より競プロに真剣に取り組めたのではないかな、と思います。

合宿期間は健康とは決して言えない生活だったんですが、温泉パワーとご飯*5で乗り切れたのも、合宿ならではだと思いました。

合宿を企画してくださったKMCの皆さん、ありがとうございました。

*1:競プロerに優しい時間

*2:当社比

*3:もちろんできなかったのであとでasiさんに手伝ってもらってDを通しました。

*4:イニシャルです。

*5:三食ほんとに美味しかった

2017-03-31

典型ナップサックを1次元配列で解く。

※一番PV数が多いので、ちょっと直しました(2020/5/24)

例題として、 B - 書き換え（Rewrite）を使います。
まずはこのコードを見てください。　

#include<bits/stdc++.h>
using namespace std;
int main(){
    int N,M;
    cin >> N >> M;
    vector<int>V(N),T(N);
    for(int i = 0; i < N; ++i){
        cin >> V[i] >> T[i];
    }
    vector<int>dp(M + 1,0);
    for(int i = 0; i < N; i++)
        for(int t = M; t >= 0;t--){
            if(t + T[i] <= M)
                dp[t + T[i]] = max(dp[t + T[i]], dp[t] + V[i]);
        }
    cout << *max_element(dp.begin(), dp.end()) << endl;
    
}

シンプルですね。時間計算量は $O(NM)$ ですが、空間計算量は $O(M)$ で少しお得です。

まずは2次元で考える。

二次元DPで考えると、
$dp[i][j] :=$ $i$ 個目の書類を見ている時に, $j$ 時間使ったときの最大値
$dp[i + 1][j + T[i]]=max (dp[i + 1][j + T[i]],dp[i][j]+V[i])$ 　という漸化式になります。

さて、この問題を1次元配列で解くことを考えます。
$dp[i] :=$ 時間 $i$ のときの最大の価値
つまり、どの書類を見ているか、という情報を捨てます。

以下が工夫するポイントです。

後ろ向きに更新する

時間 $t$ を後ろからなめて、次のように更新します。

for(int t = M; t >= 0; --t)

$dp[t + T[i]] = max(dp[t + T[i]],dp[t] + v[i])$
嬉しいポイントは、値の更新がすでに見た $t$ に対して行われます。つまり、 $i$ 番目の書類を重複して更新されることがありません。

荷物を取らない推移ないけど？

必要無いからです。2次元DPの際は, $i$ 番目の書類まで見た結果を $i + 1$ 番目にも反映させる必要があるますが、この場合はありません。

2017-03-30

RUPC 2017 参加記

０日目

基本的に事務的な準備をしてました。

問題文や解法の議論に全く参加できなかったので、来年はそういう積極的に参加したい。

さて、明日のコンテストは立命勢の日ですが今年はなんと阪大勢とのコラボです!!☺️そしていつもよりコンテストが1時間長いです...!!果たして何問コンテストなのでしょうか〜！(知ってる顔
— AORイカちゃん (@aorikachaaan) 2017年3月21日

1日目

立命セットだったので、基本的にイスに座ってFAを記録したり、風船係をしてました。懇親会では、会津合宿のときにチームを組んだ somennagasiさんや学生ではない競プロerさんと、新歓の話やプログラミングの話をした。*1

食事が美味しくてびっくりした。

余談ですが、会場に向かっている間に、gccを吹き飛ばす*2という事件がありました。

大変なことになりました。 pic.twitter.com/CPGT1xNXhT
— yebi (@sigsigma19) 2017年3月22日

２日目

NCA***さんとmkanさんで、チームGumikanstarで参加しました。

NCA***さんがC、mkanさんがA,僕がB問題を担当しました。

Bがさっと解けそう*3だったので、mkanさんの考察を手伝っている間にNCA***さんがC問題を通す(プロ)。

なんとかB問題を2WAしながら通したものの、その後は全くチームの役に立てずに死亡。

結果はB,C,Eの３完でした。

念のために0.001刻みでループを回しました。#RUPC2017
— yebi (@sigsigma19) 2017年3月23日

Aが本当に辛かったです。

コンテスト後の懇親会ではいろんな大学の競プロerさんとお話することができて、とても楽しかったです。

３日目

Yang33さんとGachoさんとチーム名Gachofriendsで参加しました。

Yang33さんがA問題、僕がB問題、GachoさんがC問題を担当しました。

A問題をYang33がすごいスピードでAC、僕の考察が行き詰まっていたので手伝ってもらいました。

解法はわかったものの、僕の実装力がなさすぎてYang33さんと一緒に実装することに。

コード量が爆発しそう&&バグが発生したので、C,Dを通したGachoさんと合流し３人で解いて無事AC。

結果はA~Dの４完でした。完全に戦犯で悲しい。

まとめ

前回の会津合宿のときよりは、少し成長したかな？と思った反面、実装力、考察力不足を痛感する合宿でした。

これからも精進していきます。

次の合宿では人狼がしたいと思いました。

*1:実際に仕事でプログラミングをしている方の話を聞いたことが殆どなかったので、とても良い経験になった。

*2:雰囲気でネットに転がっているコマンドを貼るのは危険です。

*3:誤読してたので

2017-03-10

ABC C - Factors of Factorial

N!の約数の個数を数える問題。
$2 \leq i \leq N$ の数字を片っ端から素数で割っていく。
$inde$ は添字に素数を持ち、N!の素因数の数を持つ。
$inde$ の値を初めて更新するとき( $inde=0$ )は、 $(prime) ^0$ が含まれるから $ans = 1$ にしてる。

#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#include<set>
#include<complex>
#include<map>
#define vi vector<int>
#define vvi vector<vector<int> >
#define ll long long int
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define ld long double
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
#define MAX 1e4
#define MOD 1000000007
using namespace std;
typedef pair<int, int> pii;
typedef pair<double,double>pdd;
typedef pair<ll,ll>pll;
vi inde(MAX,0);
ll cal(int num, int div){
    int ans=1;
    while(true){
        if(num%div==0){num/=div; ans++;}
        else break;
    }
    if(!inde[div])inde[div]+=ans; else inde[div]+=ans-1;
    return 0;
}
int main(){
    vector<bool>Primecheck(MAX+1,true);
    vector<int>Primenumber(MAX+1,0);
    int Primecounter =0;
    for(int i = 2; i<MAX+1;i++){
        if(Primecheck[i]){
            for(int j = 2;i*j<MAX;j++)
                Primecheck[i*j] = false;
            Primenumber[Primecounter] = i;
            Primecounter++;
        }
    }
    ll num; cin>>num;
    ll ans=1;
    for(int n=(int)num; n>1; n--){
        for(int i=0; i<Primecounter;i++){
            if(Primenumber[i]>n)break;
            if(n%Primenumber[i]==0){cal(n,Primenumber[i]);}
        }
    }
    for(int i=0; i<num+1; i++){
        if(inde[i]){ans*=inde[i]; ans%=MOD;}
    }
    cout<<ans<<endl;
}

2017-03-03

ABC C-Brute-force Attack

制約が $1 \leq N \leq 8$ だったのでnext_permutationだと思ったけど違った。

再起できれいに書けてAC。辞書順ってところに時間を取られすぎてしまった…

#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#include<set>
#include<complex>
#include<map>
#define vi vector<int>
#define vvi vector<vector<int> >
#define ll long long int
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define ld long double
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
#define MAX 9999999
using namespace std;
typedef pair<int, int> pii;
typedef pair<double,double>pdd;
typedef pair<ll,ll>pll;
string key="abc"; int lim;
void solve(string s){
    if(s.size()==lim){cout<<s<<endl;; return ;}
    rep(i,3){string temp=s; temp+=key[i]; solve(temp);}
    return;
}
int main(){
    cin>>lim;
    string s;
    solve(s);

}

2017-02-16

ARCのB :回文分割

個人的にすごく苦しんだ。~~(同期はプログラミング始めて二ヶ月でACしてる)~~
偶奇に分けて、奇数なら2で割った値を $sum$ に足す。
$sum$ を2で割ると"偶数のペア"の数がわかるから、奇数にいくつ肉付けできるかがわかる。
（イメージは、奇数は(1+偶数)になっているから、'偶数'をすべて $sum$ に足す。 $sum / ki_size$ で再分配するペアに数がわかる。）
最後の $+1$ は余り

#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#include<set>
#include<complex>
#include<map>
#define vi vector<int>
#define vvi vector<vector<int> >
#define ll long long int
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define ld long double
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
#define MAX 9999999
using namespace std;
typedef pair<int, int> pii;
int main(){
    string s;cin>>s;
    vi v(26,0);rep(i,s.size())v[s[i]-'a']++;
    int sum=0,ki_size=0;
    rep(i,26){
        if(v[i]==0)continue;
        if(!(v[i]%2))sum+=v[i];
        else {
            sum+=(2*(v[i]/2));
            ki_size++;
        }
    }
    sum=sum/2;
    if(ki_size)cout<<2*(sum/ki_size)+1<<endl;
    else cout<<s.size()<<endl;
}

2017-01-04

ブログ始めました。

2017年になったので、ブログをはじめました。

競プロとか英語とかの備忘録になる予定です。

予鈴

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