読者です 読者をやめる 読者になる 読者になる

出来るだけ寝ていたい

1日最低12時間睡眠、寝たら負け

久々

久々にゲームセンターでボルテやってきた。

KAC解禁ロード前半戦を終えた感じ。
次行った時はブラスターやって解禁ロード後半戦を終わらせたいと思ってる。

結果としてはかなり良かった。

一番苦労したのはかめりあのソフラン曲(名前忘れた)。
あれ多分10回近く落ちた。
癖着いたのが辛かった。

ぺのれりの曲は1回落ちただけだった。

個人的には変速曲がかなり苦手なのでぺのれり<かめりあって感じの難易度。

まぁ何にせよこれでブラスターさえやればillnessが解禁できると思うと嬉しい。
何故ならこれだけストレートに全曲解禁できるのが多分生まれて初めてだから。

まぁまぁ、ボルテはやり過ぎは駄目だけどたまにプログラミングの合間にちょこっとだけやりにいくと一番成果出るからこれからも地味に頑張っていきたい。

近いうちの目標は後光或帝滅斗です。

個数制限付き部分和問題

蟻本の初級編にあるDPの練習用問題。

漸化式は同じ立て方なので、

dp[i+1][j]=i番目まででjを作る際に余る最大のi番目の個数

とする。
DPテーブルを自分で書いてもらうと分かるように、ループの方向がj→j+a[i]の方向しか向いていないので配列の再利用が可能。
よってdp[j]という1次元配列でDPが可能である。

ひとまずやっている事は蟻本と変わらない。
しかし、自分はdp漸化式をソースコードとして書く際に右辺にiとjが来るように書いている(蟻本の場合は左辺)。

従って蟻本とは少し変わったプログラムを書いた。その時の記録である。

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a); i<(b); i++)
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define sort(v,n) sort(v,v+n);
#define vsort(v) sort(v.begin(),v.end());
#define ll long long
#define pb(a) push_back(a)
#define fi first
#define se second
#define inf 999999999
using namespace std;
typedef pair<int,int> p;
typedef pair<ll,ll> lp;
bool is_uruu(int y) {
        return y % 4 == 0 && (y % 100 != 0 || y % 400 == 0);
}
const ll MOD=1e9+7;
const double PI=acos(-1.0);
//----------------------------------------------------------------------------------------------------------------------------------//

int n;
int a[100],m[100];
int k;
int dp[100001];
int main(){
        cin>>n;
        for(int i=0; i<n; i++) {
                cin>>a[i];
        }
        for(int i=0; i<n; i++) {
                cin>>m[i];
        }
        cin>>k;
        memset(dp,-1,sizeof(dp));
        dp[0]=0;
        for(int i=0; i<n; i++) {
                for(int j=0; j<=k; j++) {
                        if(dp[j]>=0) dp[j]=m[i];
                }
                for(int j=0; j<=k; j++) {
                        if(dp[j]>0 && j+a[i]<=k) {
                                dp[j+a[i]]=dp[j]-1;
                        }else if(dp[j]<0) {
                                dp[j]=-1;
                        }
                }
                for(int j=0; j<=k; j++) {
                        cout<<dp[j]<<" ";
                }
                cout<<endl;
        }
        if(dp[k]>-1) {
                cout<<"Yes"<<endl;
        }else{
                cout<<"No"<<endl;
        }
}

漸化式の書き方も色々あるそうなので、最終的にはどんな書き方でも書けるようにしたい。

P≠NP問題

まあ、通常情報系の勉強をしに大学に行っている人間は誰でも知ってはいるであろう(知らない人は大学やめた方が良いかもしれない)この有名なミレニアム懸賞問題

私の場合、この問題自体は中学の頃に適当にパソコンで「ミレニアム懸賞問題」と検索したところ偶然にもそのリストの中に「P≠NP」という全く何を言っているか教える気もない様な面をした問題があるなぁなんて感じてスルーしたのが初対面だったかと。

高校の時は妄想でPは確率、Nは整数かな!なんて思って放ったらかしにしました。駄目な子ですね。せめてもう少し調べれば良かった…。

大学に入る前に友達と本屋に行って「専門外の知識の概要や面白さをある種の教養として知っておきたいね。どんな本が良いのだろう。こう、数式が沢山ある定量的で参考書の様な本よりか定性的な感覚で大まかに理解できる本は中々見つからないね。」と喋っていたらBLUE BACKSなる良い本たちを紹介してくれた。
ざっと本棚に積まれたBLUE BACKSを眺めると確かに一般大衆向け。
「なるほど。自分の友人には博識な人が山ほどいるが彼らはこういう本を片っ端から読んだのか。流石だなぁ。」なんて思いながら見つめていた。
すると友人が一冊手に取って僕に見せてくれた。題名は『「P≠NP」問題』と書いてある。
見たことのある問題だけど何で僕に見せた?と思っていると彼は「これは君に絶対に必要な類の話題。だって情報系の人間だろ?それに君は数学も大好きなんだから。」と言われ驚いた。
こいつがまさか僕の専門内なのか……??
渋々見てみると本当にコンピュータの事が書いてあった。第一印象とはまるで違った。
友人は「専門内の内容なら知っておけ。他の情報系の人間に馬鹿にされるぞ。自分の専門内の事かどうかもわからない人間は大学に来なくていい。」と言い「確かにそれは嫌だな。ごもっとも」と思い買った。(危ない危ない。ギリギリ大学入学前だからセーフ)

いざ読む。新書は読みにくいが専門書よりマシ。
優しく書かれていたがどうもピンと来ない。
あーわかってないなぁ。と思い諦める。
これは一年後に読もう。そして今はこの様な問題がこれから自分が学ぶ内容の中に潜んでいるという事実だけを覚えて先に進もうと約束した。

一年経ったから読んだ。
前半はえらく簡単な内容になってる。
中盤もえらく簡単な内容になってる。
後半もまあわかった。
感動したね。一年でここまで自分の脳みそは成長したと思うと。
これが専門内っていうことなのか、と。
まぁ大体大学で習った事の復習レベル。
計算量という概念に関しては自分はアルゴリズムに興味があって独学である程度勉強していたのですんなり頭には入った。問題無かった。それに計算量と言ってもO記法とΩ記法、Θ記法を知っていれば良いだけなのでこの程度なら情報系なら知ってて当然の類。
Pが何を表し、NPが何を表すのかもしっかりと把握した。(確率と整数じゃ無かった。)
決定性アルゴリズム多項式計算時間と非決定性アルゴリズム多項式計算時間を表すのだけどまぁ特別解説できるほどの能力は持ち合わせていないので省略。
それにこれくらいの事はどうやら情報系は知っているらしいので今更いいか。

問題の意味がわかって初めて、この問題は本当にクレイジーなのだなと。数学科の人間にはお前はまだこの問題がどれ程難解なのか分かりきってない死ねと言われるだろうがあくまで感覚なので許して下さい。

まあ無事この本も読めたし、また集中してアルゴリズムの勉強を再開できるなぁ。

復習?bfs

今日は幅優先探索の勉強をしたよ。

今の今までdfsに重きを置いていたから、よくよく考えたらbfsの実装は今回が初めてだったかもしれない。

いつも通り蟻本の問題を解いた。前回のdfsの勉強と違ってかなりすんなり出来た。といっても3時間くらいかかったのかな。ミスがシンプルだったから良かった。

幅優先探索再帰的に実装するんじゃなくて、queueを使って次状態を保存していくやり方。
再帰的に実装しないからか関数の引数はvoidだった。(これについてはまだよくわかってないので断言出来ない。もっと経験を積みますね。)

あと余談だけど実装で初めて排他的論理和を使ったかもしれない。まあ、本当にどうでもいいのだけれど。

//poj
/*  .  ∧_∧
    ( ´・ω・)
    //\ ̄ ̄旦\
   // ※ \___\
   \\  ※  ※  ※ ヽ
     \ヽ-___--___ヽ*/

#include <iostream>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <sstream>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <complex>
#include <vector>
#include <cstdio>
#include <cmath>
#define rep(i,a,b) for(int i=(a); i<(b); i++)
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define sort(v,n) sort(v,v+n);
#define vsort(v) sort(v.begin(),v.end());
#define vvsort(v) sort(v.begin(),v.end(),greater<int>());
#define ll long long
#define pb(a) push_back(a)
#define fi first
#define se second
#define inf 999999999
using namespace std;
typedef pair<int,int> P;
typedef pair<ll,ll> lP;
typedef priority_queue<int> PQ;
typedef priority_queue<int,vector<int>,greater<int> > RPQ;
bool is_uruu(int y) {
        return y % 4 == 0 && (y % 100 != 0 || y % 400 == 0);
}
template<class T>inline string toString(T x){
        ostringstream sout; sout<<x; return sout.str();
}
const ll MOD=1e9+7;
const double PI=acos(-1.0);
//-------------------------------------------------------------------------------------------------------------------------------------------//
int ny,mx;
char a[101][101];
int d[101][101];
int gx,gy;
int bfs(){
        for(int i=0; i<ny; i++) {
                for(int j=0; j<mx; j++) {
                        d[i][j]=inf;
                }
        }
        queue <P> q;
        for(int i=0; i<ny; i++) {
                for(int j=0; j<mx; j++) {
                        if(a[i][j]=='S') {
                                q.push(P(i,j));
                                d[i][j]=0;
                        }
                }
        }
        while(!q.empty()) {
                //cout<<"-------------------------------------------------"<<endl;
                int nowy=q.front().fi;
                int nowx=q.front().se;
                //cout<<nowy<<" "<<nowx<<endl;
                //cout<<d[nowy][nowx]<<endl;
                q.pop();
                if(a[nowy][nowx]=='G') {
                        gy=nowy;
                        gx=nowx;
                        break;
                }
                a[nowy][nowx]='#';
                for(int dy=-1; dy<=1; dy++) {
                        for(int dx=-1; dx<=1; dx++) {
                                if((dy^dx)!=0 && (dy^dx)!=-2 && (a[nowy+dy][nowx+dx]=='.'|| a[nowy+dy][nowx+dx]=='G') && d[nowy+dy][nowx+dx]==inf) {
                                        //cout<<"nowy+dy="<<nowy+dy<<" nowx+dx="<<nowx+dx<<endl;
                                        d[nowy+dy][nowx+dx]=d[nowy][nowx]+1;
                                        q.push(P(nowy+dy,nowx+dx));
                                }
                        }
                }
        }
        return d[gy][gx];
}

int main(){
        cin>>ny>>mx;
        for(int i=0; i<ny; i++) {
                for(int j=0; j<mx; j++) {
                        cin>>a[i][j];
                }
        }
        cout<<bfs()<<endl;
}

こんな感じ。
次からは貪欲法の勉強になります。

復習dfs ver2

前回同様、深さ優先探索の復習をしていました。今回も予想だにしなかったところでWAを招いてしまいました。2日でdfsの知識不足となる点が二箇所も分かったから嬉しい限りですがね。
今回解いていた問題はPKUのlake countingという問題。簡潔に言うと池の数数えてねっていう問題です。
最初は方針で悩んで、悩み続けて、方針を解説読んで把握しました。
んで、実装。
何も見ずに出来ると思ってやった。やれた。試しにテストケースに当てはめる。
あれれ、、違う。。
なんでだ??と思いデバッグ
違ってるところは分かった。けど、どう直す??
しばらく考えて思いついたのが、「あ!もしかして深さ優先探索は探索していく方向も考えなきゃいけないのか?!8方向を適当な順で書いたらいけないのかな!」と思い方向の順を考え始める。
(しかし、全ては僕がこんな罠にかかってしまった事が原因だった…)
何も知らずに僕は探索する方向を変えて実行。
奇跡的にテストケースの1つが通った。
あー、やっぱりそうだったかー。なんて考えた僕は愚かだった。そして無知だった。
よーし、PKUのオンラインジャッジに提出するぞー!と意気込み提出。

結果は WA

何故??え、なんでだ??これが答えじゃないの?もしかして問題違う??などと戸惑う俺。
試しに自分で作ったテストケースを入力する。
すると全く違う答えが出力された。
まだ、何か違うらしい。
そしてまたまた方向の順番を考える俺。
試しに解説の順番と同じにして実行。
答えは違った。。
今まで順番を気にしてきた俺だが、どうやらそれは関係ないらしい。。
じゃあ一体何が違うんだ。。

ここで、仕方がないから試しに解説のコードを丸写ししてみる。
実行する。テストケース通る。PKUに提出。

結果は AC

えー??一体自分のさっきまでのコードとこれ、何が違うの??ほとんど同じじゃん。真面目にわからないんだけど。。
見比べてみる。
すると、1つの違いが見えた。
解説はif文の中にdfs()が書いてある。
僕のはif文の中にreturn dfs()と書いてある。

まぁ、起こることは同じだろうけど。。と思いながらreturnを除いて実行。
テストケースが通る。
???????!!、!、!!!!!
え、これが違ったの??え、俺returnで苦しめられてたの??
更に、returnってなんだ??ということにも。
体に染み付いたggrks精神がうごめき、即wikipedia
数値を呼び出すと共に関数を終了させるもの。と書いてある。知ってた。知ってるつもりだった。関数を呼び出す時にも関数を終了させるとは思ってなかった。。return dfs()なんてやったら、そもそも深さ優先探索じゃない。。ただの再帰でしかない。。それを瞬間的に理解した。
そして、深さ優先探索を実装する時はreturn dfs()なんて死んでもやらないんだとも理解した。長かった。。理解までが本当に長かった。これだから独学は辛い。でも、一番勉強になる。
深さ優先探索を完全に理解できた。

//poj
/*  .  ∧_∧
    ( ´・ω・)
    //\ ̄ ̄旦\
   // ※ \___\
   \\  ※  ※  ※ ヽ
     \ヽ-___--___ヽ*/

#include <iostream>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <sstream>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <complex>
#include <vector>
#include <cstdio>
#include <cmath>
#define rep(i,a,b) for(int i=(a); i<(b); i++)
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define sort(v,n) sort(v,v+n);
#define vsort(v) sort(v.begin(),v.end());
#define vvsort(v) sort(v.begin(),v.end(),greater<int>());
#define ll long long
#define pb(a) push_back(a)
#define fi first
#define se second
#define inf 999999999
using namespace std;
typedef pair<int,int> p;
typedef pair<ll,ll> lp;
typedef priority_queue<int> pq;
typedef priority_queue<int,vector<int>,greater<int> > rpq;
bool is_uruu(int y) {
        return y % 4 == 0 && (y % 100 != 0 || y % 400 == 0);
}
template<class T>inline string toString(T x){
        ostringstream sout; sout<<x; return sout.str();
}
const ll MOD=1e9+7;
const double PI=acos(-1.0);
//-------------------------------------------------------------------------------------------------------------------------------------------//
char a[101][101];
int ny,mx;//x->m,y->n
int ans;
void dfs(int nowy,int nowx){
        a[nowy][nowx]='.';
        //cout<<nowy<<" "<<nowx<<endl;
        /*for(int dx=-1; dx<=1; dx++) {
                for(int dy=-1; dy<=1; dy++) {
                        int nowyy=nowy+dy;
                        int nowxx=nowx+dx;
                        if(nowyy>=0 && nowyy<ny && nowxx>=0 && nowxx<mx && a[nowyy][nowxx]=='W') dfs(nowyy,nowxx);
                }
           }*/
        if(nowx>0 && nowy>0 && a[nowy-1][nowx-1]=='W') {
                dfs(nowy-1,nowx-1);
        }
        if(nowx>0 && a[nowy][nowx-1]=='W') {
                dfs(nowy,nowx-1);
        }
        if(nowx>0 && nowy<ny-1 && a[nowy+1][nowx-1]=='W') {
                dfs(nowy+1,nowx-1);
        }
        if(nowy>0 && a[nowy-1][nowx]=='W') {
                dfs(nowy-1,nowx);
        }
        if(nowy<ny-1 && a[nowy+1][nowx]=='W') {
                dfs(nowy+1,nowx);
        }
        if(nowx<mx-1 && nowy>0 && a[nowy-1][nowx+1]=='W') {
                dfs(nowy-1,nowx+1);
        }
        if(nowx<mx-1 && a[nowy][nowx+1]=='W') {
                dfs(nowy,nowx+1);
        }
        if(nowx<mx-1 && nowy<ny-1 && a[nowy+1][nowx+1]=='W') {
                dfs(nowy+1,nowx+1);
        }
        return;
}



int main(){
        cin>>ny>>mx;
        for(int i=0; i<ny; i++) {
                for(int j=0; j<mx; j++) {
                        cin>>a[i][j];
                }
        }
        //cout<<"------------------------------------------------------"<<endl;
        ans=0;
        for(int i=0; i<ny; i++) {
                for(int j=0; j<mx; j++) {
                        if(a[i][j]=='W') {
                                dfs(i,j);
                                /*for(int k=0; k<ny; k++) {
                                        for(int l=0; l<mx; l++) {
                                                cout<<a[k][l];
                                                if(l==mx-1) cout<<endl;
                                        }
                                   }
                                   cout<<"------------------------------------------------------"<<endl;*/
                                ans++;
                        }
                }
        }
        cout<<ans<<endl;
        return 0;
}

これが今日書いたコード。これに9時間費やしただよ僕は。明日からは幅優先探索をやろうと思う。

復習dfs

基礎的な部分を補強するためにいつも使っている本のかなり前半の方を復習していた。確か、当時車校の受付前の机で勉強していた内容だったかと思う。んで見てみたらよ。方針は全く間違ってないけど、どうもテストケースが合わない。何をミスしてるのかといじってみたら思ってもなかったところが間違ってた。

int n;
int a[21];
int k;
bool dfs(int i,int mokuhyou){
//下の行のi==nをi==n-1にしてた。
        if(i==n) return mokuhyou==0;
        return dfs(i+1,mokuhyou-a[i])||dfs(i+1,mokuhyou);
}

int main(){
        cin>>n;
        for(int i=0; i<n; i++) {
                cin>>a[i];
        }
        cin>>k;
        if(dfs(0,k)) {
                cout<<"Yes"<<endl;
        }else{
                cout<<"No"<<endl;
        }
}

全く気にしてなかった所だったので当時の自分は何をしていたのかと思いながらも、復習は大事だなぁと思った。考え方としてはi==0の段階ではまだ何も配列aから取り出そうとしていない初期状態である事を意識し、i==1以降でaから取り出すor取り出さないをdfsしていく事を考える。従って、いつもの癖でiの範囲を0からn-1までとしやすいが、それは違っていてiは0からnまでの範囲で動かさなければならない。

準備完了

春休みに入って暇な時間が増えたので好きなように時間を使えるようになりました(僕は暇な時に部活をやるような真面目な人間ではないので)。

なんとかオンラインジャッジシステムを搭載したサイトで勉強をしようと去年の夏休みから頑張ってきまして、最初にやり始めたのがatcoder。これはコンテストの参加の仕方やら提出の仕方などが簡単だった、そして何より初心者に優しい問題がある点で最初に出会えたサイトとしては大当たりだった。今でも毎週参加してる。

去年の冬休みくらいにTwitterでフォローしてる人達がみんなcodeforcesの事を話していて気になったのでcodeforcesを登録する。英語orロシア語なので頑張って英語で文章を読みcodeを提出していく感じ。実際英語である事に特に支障は無い。ただ、勘違いだけは避けたいところ。

そして、今年の春休みに入ってすぐに今まで提出の仕方やcodeの書き方、その他諸々の何を取ってもやりにくいと思ってたtopcoderの登録、設定、arena設営、プラグインを完了させて無事srmにも参加できるようになった。完成した時は感動するレベル。これで競プロerとしての王道サイトの準備はほぼほぼ完了したのではないか。あとは、AOJとかPKUとかも使って練習あるのみという感じで。

悲しい事に私の周りの人間達は競プロにほぼ興味のない人間しかいないので(標準出力とかも教えてもらわないとわからないらしい)今までも、これからも1人で(正確にはTwitterでの人達と共に)頑張ってやっていきたい。競プロは数学が出来ないとある程度のところから伸びにくいらしいので、まあ自分の大学で競プロerが少ないのも納得がいく。それに、周りの環境に合わせて生きていくと自分も周りと同じになってしまうので、Twitterにいるハイレベルな人達を見ながら自分はそっちに頑張ってくらいついていければとも思う。
自分の大学から就職する気はさらさら無いのでGPAにも嫌われないよう配慮していきます。。(ロンダするのにGPAなんて関係無いと思ったそこのあなたはさぞかし賢いのでしょうな。自分の大学でGPAすら取れない人間が上に行けると思うなよ。)←これは自分なりの考えです。まあ、あまり気にしないでね。