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

出来るだけ寝ていたい

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

準備完了

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

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

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

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

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

課題

なんだかんだでdpにも慣れてきた。簡単なdpならすぐに実装できるようになったし、やっぱり数こなすのが一番って感じがした。
今後の課題としては難易度的にはそう高くないシミュレーション問題に対しての貪欲法をより早く思いつく事が出来るようにする。→数こなす、または数学やる。
優先度付きキューやヒープになれる。→慣れてください。
グラフになれる。最短経路や経路復元などの王道を実装出来るようにする。→してください。
数学的処理になれる。→慣れてください。
STLに慣れる。特にvector。→慣れてください。
このくらいかな。春休みだし、部活以外の時間に何とかしてこなしていけたらなぁと思ってます。

dp漸化式立て方メモ

これはdp漸化式を立てるのが苦手な僕が自分の為に書いたメモです。

dp配列がなんの個数(または最大値、最小値)を表しているのか意識すること。

1つ前の状況を全列挙して漸化式を作ってみること。

ありえない場合は即削除

チャレンジ8?


package kadai1.prog1.main;
import java.util.Scanner;
public class Prog006 {
            public static final int N=8;
            public static final int free=-1;
            public static final int not_free=1;
            static int row[]=new int [N];
            static int col[]=new int [N];
            static int dpos[]=new int [2*N-1];
            static int dneg[]=new int [2*N-1];
            static boolean x[][]=new boolean [N][N];
            public static void initialize(){
                        for(int i=0;i<N;i++){
                                    row[i]=free;
                                    col[i]=free;
                        }
                        for(int i=0;i<2*N-1;i++){
                                    dpos[i]=free;
                                    dneg[i]=free;
                        }
            }
            public static void print(){
                        for(int i=0;i<N;i++){
                                    for(int j=0;j<N;j++){
                                                if(x[i][j]){
                                                            if(row[i]!=j){
                                                                        return;
                                                            }
                                                }
                                    }
                        }
                        for(int i=0;i<N;i++){
                                    for(int j=0;j<N;j++){
                                                if(row[i]==j){
                                                            System.out.print("Q");
                                                }else{
                                                            System.out.print(".");
                                                }
                                    }
                                    System.out.println();
                        }
            }
            public static void solve(int i){
                        if(i==N){
                                    print();
                                    return;
                        }
                        for(int j=0;j<N;j++){
                                    if(col[j]==not_free || dpos[i+j]==not_free || dneg[i-j+N-1]==not_free)
                                                continue;
                                    row[i]=j;
                                    col[j]=dpos[i+j]=dneg[i-j+N-1]=not_free;
                                    solve(i+1);
                                    row[i]=col[j]=dpos[i+j]=dneg[i-j+N-1]=free;
                        }
            }
            public static void main(String[] args){
                        Scanner stdIn=new Scanner(System.in);
                        initialize();
                        for(int i=0;i<N;i++){
                                    for(int j=0;j<N;j++){
                                                x[i][j]=false;
                                    }
                        }
                        int k=stdIn.nextInt();
                        for(int i=0;i<k;i++){
                                    int r=stdIn.nextInt();
                                    int c=stdIn.nextInt();
                                    x[r][c]=true;
                        }
                        solve(0);
            }
}

c++でやった事があったから。深さ優先探索で。

チャレンジ7だったかな?

package kadai1.prog1.main;
import java.util.Scanner;
public class Prog005 {
            public static void hanoi(int n,String a,String b,String c){
                        if(n>0){
                                    hanoi(n-1,a,c,b);
                                    System.out.println("初期状態での上から"+n+"枚目の円盤を"+a+"から"+b+"に移動");
                                    hanoi(n-1,c,b,a);
                        }
            }
            public static void main(String args[]){
                        Scanner stdIn=new Scanner(System.in);
                        System.out.println("ハノイの塔の高さを自然数で入力してください。");
                        int n=stdIn.nextInt();
                        String a="a",b="b",c="c";
                        hanoi(n,a,b,c);
            }
}

ヒントそのままに書くとハノイの塔のプログラムが完成します。

チャレンジ課題5

全探索するだけ。

package kadai1.prog1.main;
import java.util.Stack;
public class Prog004 {
            public static void main(String args[]){
                        Stack st=new Stack();
                        //0=="+",1=="-",2=="*",3==くっつける//
                        for(int a=0;a<2;a++){
                                    for(int b=0;b<4;b++){
                                                for(int c=0;c<4;c++){
                                                            for(int d=0;d<4;d++){
                                                                        for(int e=0;e<4;e++){
                                                                                    for(int f=0;f<4;f++){
                                                                                                for(int g=0;g<4;g++){
                                                                                                            for(int h=0;h<4;h++){
                                                                                                                        for(int i=0;i<4;i++){
                                                                                                                                    while(!st.empty()){
                                                                                                                                                st.pop();
                                                                                                                                    }
                                                                                                                                    int sum=0;
                                                                                                                                    int u[]={0,0,0,0,0,0,0,0,0};
                                                                                                                                    st.push(123456789);
                                                                                                                                    if(b!=3){
                                                                                                                                                int v=(int)st.pop();
                                                                                                                                                st.push(v/100000000);
                                                                                                                                                st.push(v0000000);
                                                                                                                                    }
                                                                                                                                    if(c!=3){
                                                                                                                                                int v=(int)st.pop();
                                                                                                                                                st.push(v/10000000);
                                                                                                                                                st.push(v000000);
                                                                                                                                    }
                                                                                                                                    if(d!=3){
                                                                                                                                                int v=(int)st.pop();
                                                                                                                                                st.push(v/1000000);
                                                                                                                                                st.push(v00000);
                                                                                                                                    }
                                                                                                                                    if(e!=3){
                                                                                                                                                int v=(int)st.pop();
                                                                                                                                                st.push(v/100000);
                                                                                                                                                st.push(v0000);
                                                                                                                                    }
                                                                                                                                    if(f!=3){
                                                                                                                                                int v=(int)st.pop();
                                                                                                                                                st.push(v/10000);
                                                                                                                                                st.push(v000);
                                                                                                                                    }
                                                                                                                                    if(g!=3){
                                                                                                                                                int v=(int)st.pop();
                                                                                                                                                st.push(v/1000);
                                                                                                                                                st.push(v00);
                                                                                                                                    }
                                                                                                                                    if(h!=3){
                                                                                                                                                int v=(int)st.pop();
                                                                                                                                                st.push(v/100);
                                                                                                                                                st.push(v0);
                                                                                                                                    }
                                                                                                                                    if(i!=3){
                                                                                                                                                int v=(int)st.pop();
                                                                                                                                                st.push(v/10);
                                                                                                                                                st.push(v);
                                                                                                                                    }
                                                                                                                                    //-------------------------------------------------ok//
                                                                                                                                    if(i==3){
                                                                                                                                                u[8]=0;
                                                                                                                                    }else{
                                                                                                                                                u[8]=(int)st.pop();
                                                                                                                                    }
                                                                                                                                    if(h==3){
                                                                                                                                                u[7]=0;
                                                                                                                                    }else{
                                                                                                                                                u[7]=(int)st.pop();
                                                                                                                                    }
                                                                                                                                    if(g==3){
                                                                                                                                                u[6]=0;
                                                                                                                                    }else{
                                                                                                                                                u[6]=(int)st.pop();
                                                                                                                                    }
                                                                                                                                    if(f==3){
                                                                                                                                                u[5]=0;
                                                                                                                                    }else{
                                                                                                                                                u[5]=(int)st.pop();
                                                                                                                                    }
                                                                                                                                    if(e==3){
                                                                                                                                                u[4]=0;
                                                                                                                                    }else{
                                                                                                                                                u[4]=(int)st.pop();
                                                                                                                                    }
                                                                                                                                    if(d==3){
                                                                                                                                                u[3]=0;
                                                                                                                                    }else{
                                                                                                                                                u[3]=(int)st.pop();
                                                                                                                                    }
                                                                                                                                    if(c==3){
                                                                                                                                                u[2]=0;
                                                                                                                                    }else{
                                                                                                                                                u[2]=(int)st.pop();
                                                                                                                                    }
                                                                                                                                    if(b==3){
                                                                                                                                                u[1]=0;
                                                                                                                                    }else{
                                                                                                                                                u[1]=(int)st.pop();
                                                                                                                                    }
                                                                                                                                    u[0]=(int)st.pop();
                                                                                                                                    //--------------------------------------------------ok//
                                                                                                                                    if(b==2){
                                                                                                                                                u[0]=u[0]*u[1];
                                                                                                                                                u[1]=0;
                                                                                                                                    }
                                                                                                                                    if(c==2){
                                                                                                                                                for(int l=1;l>=0 ;l--){
                                                                                                                                                            if(u[l]>0){
                                                                                                                                                                        u[l]=u[l]*u[2];
                                                                                                                                                                        u[2]=0;
                                                                                                                                                                        break;
                                                                                                                                                            }
                                                                                                                                    }
                                                                                                                                    }
                                                                                                                                    if(d==2){
                                                                                                                                                for(int l=2;l>=0;l--){
                                                                                                                                                            if(u[l]!=0){
                                                                                                                                                                        u[l]=u[l]*u[3];
                                                                                                                                                                        u[3]=0;
                                                                                                                                                                        break;
                                                                                                                                                            }
                                                                                                                                                }
                                                                                                                                    }
                                                                                                                                    if(e==2){
                                                                                                                                                for(int l=3;l>=0 ;l--){
                                                                                                                                                            if(u[l]!=0){
                                                                                                                                                                        u[l]=u[l]*u[4];
                                                                                                                                                                        u[4]=0;
                                                                                                                                                                        break;
                                                                                                                                                            }
                                                                                                                                                }
                                                                                                                                    }
                                                                                                                                    if(f==2){
                                                                                                                                                for(int l=4;l>=0 ;l--){
                                                                                                                                                            if(u[l]!=0){
                                                                                                                                                                        u[l]=u[l]*u[5];
                                                                                                                                                                        u[5]=0;
                                                                                                                                                                        break;
                                                                                                                                                            }
                                                                                                                                                }
                                                                                                                                    }
                                                                                                                                    if(g==2){
                                                                                                                                                for(int l=5;l>=0 ;l--){
                                                                                                                                                            if(u[l]!=0){
                                                                                                                                                                        u[l]=u[l]*u[6];
                                                                                                                                                                        u[6]=0;
                                                                                                                                                                        break;
                                                                                                                                                            }
                                                                                                                                                }
                                                                                                                                    }
                                                                                                                                    if(h==2){
                                                                                                                                                for(int l=6;l>=0 ;l--){
                                                                                                                                                            if(u[l]!=0){
                                                                                                                                                                        u[l]=u[l]*u[7];
                                                                                                                                                                        u[7]=0;
                                                                                                                                                                        break;
                                                                                                                                                            }
                                                                                                                                                }
                                                                                                                                    }
                                                                                                                                    if(i==2){
                                                                                                                                                for(int l=7;l>=0 ;l--){
                                                                                                                                                            if(u[l]!=0){
                                                                                                                                                                        u[l]=u[l]*u[8];
                                                                                                                                                                        u[8]=0;
                                                                                                                                                                        break;
                                                                                                                                                            }
                                                                                                                                                }
                                                                                                                                    }
                                                                                                                                    //--------------------------------------------------//
                                                                                                                                    if(a==1){
                                                                                                                                                u[0]*=-1;
                                                                                                                                    }
                                                                                                                                    if(b==1){
                                                                                                                                                u[1]*=-1;
                                                                                                                                    }
                                                                                                                                    if(c==1){
                                                                                                                                                u[2]*=-1;
                                                                                                                                    }
                                                                                                                                    if(d==1){
                                                                                                                                                u[3]*=-1;
                                                                                                                                    }
                                                                                                                                    if(e==1){
                                                                                                                                                u[4]*=-1;
                                                                                                                                    }
                                                                                                                                    if(f==1){
                                                                                                                                                u[5]*=-1;
                                                                                                                                    }
                                                                                                                                    if(g==1){
                                                                                                                                                u[6]*=-1;
                                                                                                                                    }
                                                                                                                                    if(h==1){
                                                                                                                                                u[7]*=-1;
                                                                                                                                    }
                                                                                                                                    if(i==1){
                                                                                                                                                u[8]*=-1;
                                                                                                                                    }
                                                                                                                                    //--------------------------------------------------//
                                                                                                                                    for(int l=0;l<9;l++){
                                                                                                                                                sum+=u[l];
                                                                                                                                    }
                                                                                                                                                //------------------------------------------------------//
                                                                                                                                                if(sum==100){
                                                                                                                                                            if(a==1){
                                                                                                                                                                        System.out.print("-");
                                                                                                                                                            }
                                                                                                                                                            System.out.print(1);
                                                                                                                                                            if(b==0){
                                                                                                                                                                        System.out.print("+");
                                                                                                                                                            }else if(b==1){
                                                                                                                                                                        System.out.print("-");
                                                                                                                                                            }else if(b==2){
                                                                                                                                                                        System.out.print("*");
                                                                                                                                                            }
                                                                                                                                                            System.out.print(2);
                                                                                                                                                            if(c==0){
                                                                                                                                                                        System.out.print("+");
                                                                                                                                                            }else if(c==1){
                                                                                                                                                                        System.out.print("-");
                                                                                                                                                            }else if(c==2){
                                                                                                                                                                        System.out.print("*");
                                                                                                                                                            }
                                                                                                                                                            System.out.print(3);
                                                                                                                                                            if(d==0){
                                                                                                                                                                        System.out.print("+");
                                                                                                                                                            }else if(d==1){
                                                                                                                                                                        System.out.print("-");
                                                                                                                                                            }else if(d==2){
                                                                                                                                                                        System.out.print("*");
                                                                                                                                                            }
                                                                                                                                                            System.out.print(4);
                                                                                                                                                            if(e==0){
                                                                                                                                                                        System.out.print("+");
                                                                                                                                                            }else if(e==1){
                                                                                                                                                                        System.out.print("-");
                                                                                                                                                            }else if(e==2){
                                                                                                                                                                        System.out.print("*");
                                                                                                                                                            }
                                                                                                                                                            System.out.print(5);
                                                                                                                                                            if(f==0){
                                                                                                                                                                        System.out.print("+");
                                                                                                                                                            }else if(f==1){
                                                                                                                                                                        System.out.print("-");
                                                                                                                                                            }else if(f==2){
                                                                                                                                                                        System.out.print("*");
                                                                                                                                                            }
                                                                                                                                                            System.out.print(6);
                                                                                                                                                            if(g==0){
                                                                                                                                                                        System.out.print("+");
                                                                                                                                                            }else if(g==1){
                                                                                                                                                                        System.out.print("-");
                                                                                                                                                            }else if(g==2){
                                                                                                                                                                        System.out.print("*");
                                                                                                                                                            }
                                                                                                                                                            System.out.print(7);
                                                                                                                                                            if(h==0){
                                                                                                                                                                        System.out.print("+");
                                                                                                                                                            }else if(h==1){
                                                                                                                                                                        System.out.print("-");
                                                                                                                                                            }else if(h==2){
                                                                                                                                                                        System.out.print("*");
                                                                                                                                                            }
                                                                                                                                                            System.out.print(8);
                                                                                                                                                            if(i==0){
                                                                                                                                                                        System.out.print("+");
                                                                                                                                                            }else if(i==1){
                                                                                                                                                                        System.out.print("-");
                                                                                                                                                            }else if(i==2){
                                                                                                                                                                        System.out.print("*");
                                                                                                                                                            }
                                                                                                                                                            System.out.print(9);
                                                                                                                                                            System.out.println("=100");
                                                                                                                                                }
                                                                                                                        }
                                                                                                            }
                                                                                                }
                                                                                    }
                                                                        }
                                                            }
                                                }
                                    }
                        }
            }
            }

異常なほど長くなったけど気にしない。
配列、スタック位しか使ってないから誰でも書ける簡単コード。
優しい。

何種類?

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#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);
}
//---------------------------------------------------------------------------//

int main(){
        int a,b,c;
        cin>>a>>b>>c;
        int i=3;
        if(a-b==0) --i;
        if(a-c==0) --i;
        if(b-c==0) --i;
        if(i==0) cout<<1<<endl;
        else {
                cout<<i<<endl;
        }
}

三人がそれぞれ一色だけ絵の具を買う。でも三人の中で色が被ってしまう場合も。
絵の具の色が番号で表されるとき絵の具の色の種類を出力。