戦いたい選手をキューで詰めていってマッチングしたら戦わせる。対戦(i,j)をグラフとしてDFSという方法がeditorialに載っているが、pythonでそれを表現したらTLEした。 (pythonでグラフ構造を効率よく表現する方法を知らなさすぎる) この方法で普通に解けたと思ったけどwhileループ中で抜けた場合の初期化処理をしていなくてWAした。

from unittest.mock import patch

testcases = """3
2 3
3 1
1 2
""".split('\n')

def solve():
    N = int(input())
    tournament = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N)]
    map_que_tournament = {i:[] for i in range(N)} # player iがjと戦いたがってる
    competition_num = -1
    que_player = list(range(N)) #それぞれ戦えるプレイヤーをqueueにつめていく
    
    while que_player:
        day_process_flag = False
        new_queue = [] # 次のステップ更新用のqueue
        # print(que_player)
        for player in que_player:
            if tournament[player]:
                # トーナメントの対戦希望表から抜き出す
                match_player = tournament[player].pop(0)
                # ぶじマッチング相手が見つかったら
                if map_que_tournament[match_player] and player == map_que_tournament[match_player][0]:
                    # print(player, match_player)
                    day_process_flag = True
                    new_queue.append(match_player)
                    new_queue.append(player)
                    map_que_tournament[match_player].pop()
                else:
                    map_que_tournament[player].append(match_player)

        # 戦える人がいた場合に一日進める
        if day_process_flag:
            if competition_num < 0:
                competition_num = 1
            else: competition_num += 1

        que_player = new_queue
        
    # 途中でやめた場合
    for t in tournament:
        if t:
            competition_num = -1
            break

    print(competition_num)

with patch('builtins.input', side_effect=testcases):
    solve()

TLEしたグラフDFSしたpythonコード Nを最大にすると8秒くらい最初の読み込みでかかってしまう

def solve():
    fix_index = lambda x,y: (x,y) if x < y else (y,x)
    N = int(input())
    tournament_graph = {} # N^2
    tournament_graph_dom = {} # N^2
    search_vertex = {}
    max_path = -1
    
    for i in range(N):
        vertex_pre = None
        for j in map(int, input().split()):
            j = j-1
            vertex = fix_index(i,j)
            if vertex not in tournament_graph: # vertex not in tournament_graph
                tournament_graph[vertex] = []
                tournament_graph_dom[vertex] = []
                search_vertex[vertex] = True
            if vertex_pre:
                tournament_graph[vertex_pre].append(vertex)
                tournament_graph_dom[vertex].append(vertex_pre)
                
            vertex_pre = vertex
    
    vertices = []
    for vertex in tournament_graph_dom:
        # 点が存在して、入ってくる辺が無いもの
        if search_vertex[vertex] and (not tournament_graph_dom[vertex]):
            vertices.append(vertex)
            search_vertex[vertex] = False
    
    while tournament_graph:
        # ここで探索する
        new_vertives = []
        if vertices:
            # print(vertices)
            if max_path < 0: max_path = 0
            for v in vertices:
                while tournament_graph[v]: 
                    cod = tournament_graph[v].pop(0)
                    tournament_graph_dom[cod].pop(0)
                    # つぎ検索する箇所を選定
                    if search_vertex[cod] and (not tournament_graph_dom[cod]):
                        new_vertives.append(cod)
                        search_vertex[cod] = False
                    
            max_path += 1
        else:
            # DAG ならばdom(v) = \emptysetとなるvが存在しない
            break
            
        vertices = new_vertives
    
    print(max_path)
    
solve()

2019-09-14

英語を学ばないと死ぬ

こんにちは、いりすです。

最近は英語の勉強をしています。

NHKの英会話ラジオを聞き、シャドーイングをしています。

英語を学ぶ理由は、海外のデータサイエンティストと英語でミーティングをしているからです。

私はデータ分析も行うエンジニア（AIエンジニアやデータサイエンティストとはちょっと違うキャリアだと思う）をしているのですが、

データ分析市場は日本より海外の方が利益を産んでいると感じるし（kaggleの主催企業を見ていると実感するが、ここはマーケティングレポートなどを示したい）、それまでデータ分析をしてきた経験を海外支社のデータサイエンティストと協力して新たな取り組みができないかということでミーティングが始まりました。

自分がエンジニアとして成長できる機会なので絶対に逃したくないです。

しかし、私は、英語で情報収集しドキュメントを見ることはできますが、喋ることやリスニングは全くで、いざ会議に参加しても一切しゃべることはできませんでした。

ミーティングで発言、アウトプットしない人間はいる意味ある？　と感じることが多いですが、いま自分がその立場になることを実感し、そしてこのままでは成長の機会を逃してしまうのではないかと思っております。

なので、英語の勉強を頑張ってますし、今度オンラインの英会話に挑戦しようと思っております。

まさか自分が英会話に挑戦するとは思ってなかったし、「人間万事塞翁が馬」というやつですね。

自分のスキルセットがあがることは楽しいです。SLGやRPGのオタクなので。

私は強くなるので、成長を楽しみにしていてください（厚顔）

自分は高校生のときに数学を好きになって大学で研究するとは思ってもなかったし、

社会人になって数学の道は閉ざされたと思いましたが、製品開発に数学的な知識を盛り込むことは多く、また組織として認められるとは思ってもなかったです。そして、また研究できることになるとは思ってもなかったです。

意外に人生思いもよらない方向にいくし、なんとかなりますね。そして、学ぶことはとても楽しいんですよね。

2019-08-14

C96の報告と反省

C96お疲れさまでした。

今回は新たにリストバンド導入や、会場の変更などで新しいコミケになったと思います。

個人の感想としては夏コミでのサークル参加は初めてで、サークルスペースでも非常に暑く、一般参加者と同等に熱中症対策の必要性を実感しました。

ABC128 - C問題が解けない

Python 競技プログラミングアルゴリズム

最近AtCoderに挑戦中。直近ではABC128に出たけど、ナイーブに全探索するって発想が出なかったので30分考えて匙投げてしまった（圧倒的に経験値が足りない

atcoder.jp

ABC128のC問題が面白かったので紹介する。回答を見ると $\mathbb{F}_2$ 上の連立方程式で解けるということなので解こうとしてるが2つWAになってしまって解けない…

#include <iostream>
#include <algorithm>
#include <string.h>
#include <cstdio>
#include <string>
#include <vector>
#include <math.h>

using namespace std;

#define MAX_INT 11

#define sum_f2(a,b) (a+b)%2

void debug_print_matrix(int matrix[MAX_INT][MAX_INT], int M, int N){
    printf("debug_print_matrix: \r\n");
    for(int i=0; i<M ;i++){
        for(int j=0; j<N ;j++){
            printf("%d ", matrix[i][j]);
        }
        printf("\r\n");
    }
}

// matrix method
void add_c_row(int matrix[MAX_INT][MAX_INT], int p, int q, int c, int N){
    // matrix[q][:] = matrix[p][:]*c+matrix[q][:]
    for (int i=0 ; i < N; i++){
        matrix[q][i] = sum_f2(matrix[q][i], matrix[p][i]*c);
    }
}

void exchange_row(int matrix[MAX_INT][MAX_INT], int p, int q, int N){
    int temp;
    for (int i=0 ; i < N; i++){
        temp = matrix[q][i];
        matrix[q][i] = matrix[p][i];
        matrix[p][i] = temp;
    }
}

void exchange_col(int matrix[MAX_INT][MAX_INT], int p, int q, int M){
    int temp;
    for (int i=0 ; i < M; i++){
        temp = matrix[i][q];
        matrix[i][q] = matrix[i][p];
        matrix[i][p] = temp;
    }
}

int get_rank(int matrix[MAX_INT][MAX_INT], int M, int N, bool hom){
    // gauss eliminationでrankを求める
    int ret = 0;
    int matrix_temp[MAX_INT][MAX_INT];
    for (int i = 0; i < M; i++){
        for (int j = 0; j < N; j++){
            matrix_temp[i][j] = matrix[i][j];
        }
    }
    int pivot = 0;
    // if (hom) N-=1;
    for (int i = 0; i < N && pivot < M; i++){
        if (matrix_temp[pivot][i] == 0){
            // 対角成分が0ならば行を交換する。
            int ex = -1;
            for (int j = pivot; j < M; j++){
                if (matrix_temp[j][i] != 0){
                    ex = j;
                    break;
                }
            }
            if (ex == -1) {
                continue;
            }
            exchange_row(matrix_temp, pivot, ex, N);
        }
        for (int j = pivot+1; j < M; j++){
            if (matrix_temp[j][i] == 1){
                add_c_row(matrix_temp, pivot, j, 1, N);
            }
        }
        // debug_print_matrix(matrix_temp, M, N);
        ret++;
        pivot++;
        
    }
    // debug_print_matrix(matrix_temp, M, N);
    return ret;
}

int main(){
    int N,M;
    int matrix[MAX_INT][MAX_INT]={0};
    int ret = -1;

    scanf("%d %d", &N, &M);

    int k;
    int s;
    for(int i = 0; i < M; i++){
        scanf("%d", &k);
        for(int j = 0; j < k; j++){
            scanf("%d", &s);
            // printf("debug: %d\r\n", s);
            matrix[i][s-1] = 1;
        }
    }
    
    for (int i=0; i < M; i++){
        scanf("%d", &(matrix[i][N]));
    }
    // debug_print_matrix(matrix, M, N);
    // debug_print_matrix(matrix, M, N+1);
    int rank = get_rank(matrix, M, N, false);
    if (M > N){
        int homo_rank = get_rank(matrix, M, N+1, true);
        // printf("debug: rank = %d\r\n", rank);
        // printf("debug: hrank = %d\r\n", homo_rank);
        if(homo_rank != rank)
        {
            printf("0\r\n");
            return 0;
        }
    }
    int dimker = N-rank;
    ret = (dimker == 0)? 1 : pow(2, dimker);
    printf("%d\r\n", ret);
    fflush(stdout);

    return 0;
}

理論的補足をすると、任意のスカラー体における線形空間での連立方程式の解について考える。（斎藤正彦の線形代数2.5の議論は体の性質しか使ってないので $\mathbb{F}_2$ としても成立する。）

連立方程式の解は線形変換 $f(x)=Ax+b$ における $ker f$ を考えればいい。

ここで、斉次化された方程式 $f(x)=\tilde{A}\tilde{x}$ を考えたら $rank A = rank \tilde{A}$ であれば、 $x _ 0 \in ker \tilde{A}$ について $ker A = \langle x _ 0 + Base(ker A) \rangle$ である。よって、線形多様体 $V(f)$ の解の個数は

$|V(f)| = \begin{cases} 0 & (rank A = rank \tilde{A}) \\ 2 ^ { \dim ker A } & (else) \end{cases}$

ここで次元定理より $\dim dom(f) = \dim ker A + rank A$ なので $\dim ker A = \dim dom(f) - rank A = N - rank A$

2019-05-12

ロージアちゃんとジャクリンちゃんの3Dモデルをアップロードしました。

タイトルの通り。

定期的に自分のツイッターや同人誌でも利用しているロージアちゃんとジャクリンちゃんの3Dモデルを正式にアップロードしました。

- ジャクリン

https://www.blendswap.com/blends/view/93979

- ロージア

https://www.blendswap.com/blends/view/93981

自分のアカウントですが、作者にはアップロード許諾を頂き、ライセンスも同意したうえでのアップロードとなります。

ライセンスはCC-BY+AGPL3（利用したblenderのアドオンがAGPL3なので）です。

使用例ですが、自分はunityで次のようなアプリを作って遊んだりしてます。

とりあえずジャクリンのおっぱいに乳揺れを入れたけど微振動して笑った pic.twitter.com/ZF1NVo7an2
— いりす@技術書典お06 (@irisuinwl) May 8, 2019

やったージャクリンのおっぱい触れるようになったよー！！！！ pic.twitter.com/Kn8e733am9
— いりす@技術書典お06 (@irisuinwl) May 9, 2019

HTC viveのチュートリアルでロージアちゃんオブジェクト追加したら面白すぎた件 pic.twitter.com/XHU4rziV66
— いりす@技術書典お06 (@irisuinwl) May 6, 2019

技術書典の編集作業が90%終わりました...！ 3人で合同誌を頒布します！　私、いりすは初めてunityに触れAR+chatbotアプリ作成したときの記事を書きました！　他にもchatbot自作の記事やラズパイで自宅のリモコンをハックする記事などがあります！ pic.twitter.com/vcjprypCqL
— いりす@技術書典お06 (@irisuinwl) April 7, 2019

irisuinwl’s diary

サークル不思議（略）入巣次元の、数学や技術的なことを書きます。

とんかつDJあげ太郎がヤバすぎた

はじめに

アズールレーンをN倍楽しむために資料をまとめる

ABC 139 Eが解けた話

英語を学ばないと死ぬ

C96の報告と反省

目次:

ABC128 - C問題が解けない

ロージアちゃんとジャクリンちゃんの3Dモデルをアップロードしました。