seriruの技術屋ブログ

競技プログラミングやゲーム開発など技術に関することを発信します

2020/07/06 ~ 2020/07/12 までの1週間を振り返る

最近は気づいたら1週間が経っています。
今週もあまり目立った進捗がありませんでしたが、簡単に2020年7月第2週にやったことを振り返ります。

研究

週初めに行った実験データの分析と使用したプログラムの再確認をしていました。

実験中に使っているロボットのビュワーがgnuplot製なのですが、何回もreplotを繰り返しているとランダムでクラッシュするという問題にぶち当たり、その解決に少し苦戦。

最終的にgnuplotのバグレポートを発見し、そこに書かれていた解決方法を試すことで問題を解決できました。

https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=834396

複数論理コアでgnuplotを動かすとクラッシュするってどういうこと...?

OSS Contribution

AtCoder Problemsに自分で建てたissueのPRを出し、無事取り込まれました。

github.com

AtCoder ProblemsはフロントエンドがReact+TypeScriptで書かれていますが、自分はReactの経験が殆どなかったため最初は戸惑いました。結果的に1時間ほどでissueに関係する部分を見つけ、修正・テストを行うことができました。

サイトアップデート後、好意的なコメントをTwitterでしてくれているのを発見してかなり嬉しい気持ちになりました。今後自分でも対応できるようなissueがあればまたやってもいいかも。

競技プログラミング

f:id:ryo_seriru:20200713001626p:plain

新規AC +12
Rating 1091 ➡ 1072

毎日1 UniqueACを目指して取り組んだのですが、とりあえずストリークを稼ぐために簡単な問題でお茶を濁すことも多かったので、実際に自分のレベル+αの問題を解いたのは5問くらいだった気がします。

また、今後は広く闇雲に過去問に手をつけるのではなく、問題の分野を絞って解くようにしてみようと思います。最近のABCは早解きができなければ水パフォは殆ど出せないように感じます。といっても、早解きができていざE問題にとりかかろうとしても、現在の知識では手も足も出ないか、もう少し...！というところで止まってしまうことが殆どです。この現状を打破し健闘するために、この分野の問題ならE、Fで出ても解ける！という自分の得意分野みたいなものをゆっくり成長させていこうと思います。

今週は重複組み合わせや二項係数などを用いる数え上げをやってみる感じで。

ゲーム

最近は昔のようにゲームをやる時間が増えているので最近プレイしたゲームを紹介していきたいと思います。

Apex Legend

最近ハマってるバトロワゲーム。FPSはリスポーンありのゲームしかやってこなかったのでバトロワのような1回死んだら終わりというゲームスタイルは合わないと思っていましたが、Apexに限っては打ち合いも楽しめ、更に待ちもそこまで強くないのでくだらない死に方をしないという点から非常に楽しくプレイできています。

現在のランクはプラチナ4ですが、今シーズンはダイヤまで行きたいところ。

www.ea.com

No man's sky

www.jp.playstation.com

友達に誘われて買いました。まだ4時間ほどしかやっていませんが、結構楽しめています。惑星から宇宙へシームレスに移動できるのはかなり楽しいし、NPCが独自の言語を持っているため、自力で言語を覚えなければいけないという設定も面白いです。飽きるまでプレイしてみようかなーと思っています。

Titanfall2

セールで安かったのと、キャンペーンの評判がかなりいいので購入。ApexLegendの過去のお話なので知っている武器がかなり出てきてそれだけでも楽しい。また、Titanは思った以上に覚えることが少なく、軽快に動かすことができます。

こちらも2時間ほどしかプレイしていないのでまだまだストーリーは見えないのですが、今後が楽しみ。

www.ea.com

来週やること

  • ゼロから作るDeepLearning実装 今週やろうと思っていたけどやれなかった。今週こそやりたい。

生活習慣を整えないと1日ぼーっとしていることが多くなることがわかったので、早寝早起きが急務...

2020/06/28 ~ 2020/07/05 までの1週間を振り返る

今週から１週間ごとに振り返りの日記を書いていこうと思います。 半年は継続させたい。

研究

検証で使うロボットを他研究室からお借りして動かしてデータを取った。
自分で設定した環境マップどおりに動いてくれたのでかなり嬉しかった。

同時にgnuplotの使い方を学び直して、データ取得 → 前処理 → グラフに出力の流れを自動化。

下図はsysstatで取得したCPU稼働率をx軸 時刻, y軸 CPU使用率でプロットしたもの。

f:id:ryo_seriru:20200705235041p:plain

結構綺麗に出力できて満足。慣れればかなり自由度の高いグラフを作れることもわかった。
動くスクリプトを生成できたので修論でも苦労しないで済みそう。

ゼロから作るDeep Learning -Pythonで学ぶディープラーニングの理論と実装-

授業で画像処理系の論文を1つ選んで発表する必要があったので、授業の担当教員が公開していたおすすめ論文リストから Let there be Color!: Automatic Colorization of Grayscale Images という論文を選んで読んでみたところ内容がさっぱり理解できずに撃沈。

この際なので深層学習を表面だけでも理解したいと思い、「深層学習 入門書」で出てきた中で評価が高い本を選んでしっかり読んでみようとなった。

www.amazon.co.jp

感想

Python の基礎的な文法から始まり、パーセプトロン、ニューラルネットワーク、誤差逆伝播法を説明した後、最終的にCNNと深層学習まで一気に学習するという内容で非常に密だった。

Loss関数ってなんだよってくらいこの分野は素人だったが、本文中の説明がこれでもかというほど初学者に配慮して書かれており、図と本文を何回も見比べることで少しずつ内容が頭に入ってくるので、飽きずに最後まで読みきることができた。

各章の最後には Python の実装コードが載っており、これも本当に役立った。やっぱり疑似コードがあると理解のスピードが違う。

最終的にこの本を読んだおかげで、前述の論文も3日かかったがなんとか発表できるくらいには読み込むことができた。これがなかったら手詰まりだったと思うので助かった。授業が終わったら発表したプレゼンも公開したい。

競プロ

f:id:ryo_seriru:20200706005159p:plain

80回以上コンテストに出場していながらいまだに水色になれていません。 正直このグラフかなり恥ずかしいのでがんばって1200を超えたいところ。

レートが上がらない原因は集中力と自頭の悪さなのかなーと落ち込んで半年以上離れていたのですが、Twitterでどんどんレートを上げていく競プロerを見たり、懇親会での暖色の方をお話してみてかなりモチベーションが戻ってきたので、就職までもう少し頑張ってみたいと思います。

Twitterとかで悩んでたらヒントとか頂けると助かる。。。

来週までやりたいこと

  • 研究 実験とデータの取得・分析。

  • AtCoder Problemsへのコントリビューション ウィンドウ半分の幅でサイトを開いたときにユーザ検索タブがToggleボタンに消えてしまうのが結構不便だなーと思って、それに対するissueを建ててみた。
    好意的なコメントを頂いたので今積み上がっているタスクが終わり次第PRを投げたい!!

github.com

  • ゼロから作る Deep Learning のC++実装 優先度低め。手書き文字認識を一から実装してみたい。

  • 毎日1UniqueAC

就職までやりたいこと

来週はもう少し目に見える進捗を出したい。

AtCoder Beginner Contest 167 E Colorful Blocks

問題

atcoder.jp

問題概要

N 個のブロックがあり、これを M 色のペンキで塗り分ける。隣り合う同色のブロックが K 組以内の場合の塗り分け方の総数を mod\ 998244353 で求めよ。

解説

左端を除くブロックのうち隣と同じ色で塗られているブロックの数が丁度 k 個の場合を考える。

この場合の色の塗り方は以下を考慮して計算できる。

1) 左隣と同じ色を持つブロックを k 個選ぶ => _{N-1}C_{k}

2) 1)で選択したブロックを除く N-1-k のブロックを左隣と違う色で塗る => (M-1) ^{ N-1-k }

3) 左端のブロックは M 色から1つ選択して塗る => M

よってこの場合の色の塗り方は _{N-1}C_{k} * (M-1) ^ {N-1-k} * M

後は k = 0 から k = K までの塗り方の和を上の式に当てはめて計算すれば良い。

提出

atcoder.jp

この提出では以下の記事で紹介されたライブラリを参考にしました。

augusuto04.hatenablog.com

drken1215.hatenablog.com

AtCoder Beginner Contest 031 C 数列ゲーム

芝浦競プロ検討会の復習 (https://not-522.appspot.com/contest/6468297472081920)

問題概要

長さ N の数列 S がある。高橋君と青木君はそのうち2つの整数を選んで丸をつけ、その間にある整数以外は削除する。残った数列を T と置き、 T の奇数要素の総和を高橋君の得点、偶数要素の総和を青木君の得点とする。青木君が高橋君の丸の付け方を知っているとき、高橋君が得られる得点として考えられる最大値を求めよ。

考察

今回は数列の大きさの制約が 2 \lt N \lt 50 と小さいので、高橋君の丸の付け方を全て試すことができ、高橋君が取得できる得点を全探索することによって答えを求めることができます。

次に高橋君が a_{i} に丸を付けたときの点数の求め方を考えます。これも数列の大きさの制約が小さいため、青木君の丸の付け方を全て試すことで、高橋君が a_{i} に丸を付けたときの青木君の得点の最大値を求めることができます。問題文から青木君は高橋君が丸をつけた後に自分の得点が最大になるように丸をつけられます。この条件から、青木君の得点が最大になる場合の高橋君の得点が a_{i} に丸を付けたときの点数になります。

高橋君の丸の付け方とその時の高橋君の点数の求め方の計算量は O(N^{3}) で収まるため、この問題を解くことができました。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <map>
#include <unordered_map>
#include <set>
using namespace std;

typedef long long ll;

#define INF 10e17
#define rep(i,n) for(long long i=0; i<n; i++)
#define repr(i,n,m) for(long long i=m; i<n; i++)
#define END cout << endl
#define MOD 1000000007
#define pb push_back
#define sorti(x) sort(x.begin(), x.end())
#define sortd(x) sort(x.begin(), x.end(), std::greater<long long>())
#define debug(x) std::cerr << (x) << std::endl;
#define roll(x) for (auto&& itr : x) { debug(itr); }

template <class T> inline void chmax(T &ans, T t) { if (t > ans) ans = t;}
template <class T> inline void chmin(T &ans, T t) { if (t < ans) ans = t;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];

    int ans = -10000;

    rep(i, n) {
        pair<int, int> aokiMax = make_pair(-10000, 100);
        int tMax = -10000;
        rep(j, n) {
            if (i == j) continue;

            auto mark = i;
            int takahashi = 0;
            int aoki = 0;

            if (j > mark) {
                for (int k = mark, cnt = 1; k <= j; ++k, ++cnt) {
                    if (cnt % 2 == 0)
                        aoki += a[k];
                    else
                        takahashi += a[k];
                }
            } else {
                for (int k = j, cnt = 1; k <= mark; ++k, ++cnt) {
                    if (cnt % 2 == 0)
                        aoki += a[k];
                    else
                        takahashi += a[k];
                }
            }

            if (aoki > aokiMax.first) {
                aokiMax = make_pair(aoki, j);
                tMax = takahashi;
            }
        }
        chmax(ans, tMax);
    }

    cout << ans << endl;
}

提出コード atcoder.jp

ネーグルアルゴリズムとsetsockopt

研究でTCPを使ってリアルタイムな処理を行おうとして詰まったので残しておきます。

servとrecv側で必ず等間隔のラグがある？

ある日研究で小さいパケット(20 ~ 50byteくらい大きさ)を, 短時間に何回も送信するような実験をすることになりました。
実験の前提としてリアルタイムかつデータに抜けがあってはならないという条件があったため, CAT6のLANケーブルをPC間に直刺しして, 通信部分は以下に示したようなコードを書いて実験に臨みました。(エラー処理とかは取り除いています。)

クライアント

#define SIZE 26

// TCP通信を指定

char data[SIZE];
for (int i = 0; i < 26; ++i) {
    data[i] = 'a' + i;
}

send(sock, data, SIZE, 0);

サーバ

#define SIZE 26

// TCP通信を指定

char data[SIZE];
recv(sock, data, SIZE, 0);

しかし上記のコードを何回実行しても必ずsendしてからrecvするまで、約0.4secほどの遅延が生じてしまいました。
これはおかしい、と思いローカルで実行して遅延はほとんど変わらず...

いろいろ調べた結果、次の記事に辿り着きました。

https://www.ibm.com/developerworks/jp/linux/library/l-hisock/index.html

TCP ソケットを使用して通信する場合、やり取りされるデータはブロック単位に分割され、通信用の TCP ペイロードに格納されます。TCP ペイロードのサイズはいくつかの要因 (パスに応じた最大パケット・サイズなど) によって決定されますが、通信が開始されるまでこれらの要因を特定することはできません。最高の性能を実現するには、それぞれのパケットにできるだけ多くの使用可能データを格納することが必要です。ペイロード内に十分なデータがない場合 (ペイロードのサイズが最大セグメント・サイズ (MSS) になります)、TCP は Nagle アルゴリズムにより、複数の小さなバッファーを自動的に連結して 1つのセグメントを作成します。これにより、アプリケーションの処理効率を上げ、小さなパケットの送信数を最小限に抑えてネットワーク全体の混雑を緩和します。

これが原因っぽい。

ネーグルアルゴリズム

Nagle(ネーグル)アルゴリズムとは、複数の小さいパケットを連結して1つの大きなセグメントにしてから送信するというものです。

こちらの記事(http://hayachi617.blogspot.com/2014/06/tips_7.html)にもある通り、データをTCP/IPを使用して送信すると必ずTCPパケットとIPパケットが送信されるデータにはくっついています。しかし、短期間に小さいデータを大量に送るとTCPパケットとIPパケットによる伝送路へのオーバーヘッドはバカになりません。最悪輻輳が発生し、ネットワークが大渋滞になってしまいます。

この問題を解決するために小さなパケットはTCPの最大セグメント長になるまで連結して送信するというネーグルアルゴリズムが提案されました。

WireSharkなどで確認したわけではありませんが自分の環境ではMTU(通信機器が一度に送信できる最大のデータ量)が1500Byteだったため、最大セグメント長は1460Byteほどであったと思われます(参考 https://milestone-of-se.nesuke.com/nw-basic/grasp-nw/mtu-mss-fragment-segment/)。ネーグルアルゴリズムでは、一定時間内に最大セグメント長に達しない場合はそこまで連結したパケットを送信することになっています。そのため実験では送信するデータが最大セグメント長に達せず、設定されていた一定時間(0.4sec)で送信されていたと考えられます。

といってもこの機能は小さいパケットをそのまま送信したいときには邪魔になるだけです。従ってsetsockopt関数でネーグルアルゴリズムを無効かする必要があります。

TCP_NODELAY

setsockoptはソケットに関連付けられるオプションを設定できる関数です。ここにソケット記述子とTCP_NODELAYを指定することでネーグルアルゴリズムを無効にできます。(参考: https://www.ibm.com/support/knowledgecenter/ja/SSLTBW_2.3.0/com.ibm.zos.v2r3.hala001/setopt.html)

TCP_NODELAYを設定したコードが以下になります。

#define SIZE 26

char data[SIZE];
for (int i = 0; i < 26; ++i) {
    data[i] = 'a' + i;
}
// TCP_NODELAYを設定
int ret = setsockopt(sock, IPPROTO_TCP, TCP_NODELAY, (char*)&flag, sizeof(flag));
if (ret == -1) {
    perror("client setsockopt\n");
    exit(1);
}

send(sock, data, SIZE, 0);

これにより小さいパケットをそのままサーバに送信できるようになりました。

まとめ

  • 輻輳制御のため、小さいパケットを連結してから送信するネーグルアルゴリズムが使われている。
  • 小さいパケットをそのまま送信したいときはTCP_NODELAYを指定して、ネーグルアルゴリズムを無効にする必要がある。


何か間違いがありましたらコメントいただけると嬉しいです。

新品のWestern DigitalのHDDをWindows10に認識させるまで

新品のHDDをWindows10に認識させるまでに少し詰まってしまったので備忘録として書き残しておきます。

やること

新品のWDのHDD (WDBlue 3TB 5400rpm) を自作PCで使えるようにする。

詰まったこと

SATAケーブルと電源をつないでもWindows10には認識されなかった。

なぜ認識されなかったか

ディスクのフォーマットが済んでいなかったのと、Windowsにディスクが割り当てられなかったため。

解決方法

※ HDDは既に接続済みであるとします。

  1. コンピュータを右クリックし、管理 => 記憶域 => ディスクの管理を開く。

  2. HDDが接続されていると、未割当というディスクが追加されているはずなので、それを右クリックしてフォーマット

  3. フォーマットが終わったらWindowsに割り当て。好きなドライブのアルファベットを付けます。成功するとこんな画像のようになると思います。今回はEドライブとして割り当て。 f:id:ryo_seriru:20190920223557p:plain

  4. Windows10から認識されるようになり、アクセスできるようになりました。

f:id:ryo_seriru:20190920223717p:plain

こういうのマウントっていうんだっけ。

AudioSourceとAudioClipを使って球体射出時の効果音の実装

Unityを使って球体射出時の効果音と地面に衝突したときの効果音を実装します。

バージョン

Unity 2018.4.6f1 Personal

完成品

マウスの左クリックで球体を発射し、地面に衝突すると薬莢が落ちる効果音が再生されます。

球体を射出する処理

射出する球体のプレファブを作ります。といっても sphere オブジェクトに RIgidbody と AudioSource、衝突時に効果音を再生するスクリプトをアタッチしただけのひねりのないものです。

f:id:ryo_seriru:20190830114051p:plain

f:id:ryo_seriru:20190830114054p:plain

次に球体を射出するスクリプトを書いていきます。

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class createBall : MonoBehaviour {
  public GameObject m_BallPrefab;
  AudioSource m_AudioSource;
  public AudioClip m_Clip;

  void Start() {
    m_AudioSource = GetComponent<AudioSource>();
  }
  
  void Update() {
    if (Input.GetKeyDown(KeyCode.Mouse0)) {
      GameObject gb = Instantiate(m_BallPrefab, transform.position, transform.rotation);
      Rigidbody rb = gb.GetComponent<Rigidbody>();
      rb.AddForce(gb.transform.right * 10.0f, ForceMode.Impulse);
      m_AudioSource.PlayOneShot(m_Clip);
    }
  }
}

マウスの左クリックは Input.GetKeyDown(KeyCode.Mouse0) で取得します。

入力の取得には

  • Input.GetAxis
  • Input.GetKey

など様々なメソッドが用意されていますが、今回はただ左クリックされたことを取得できさえすればよいので GetKeyDown を使用します。

左クリックが押された後に、プレファブをインスタンス化して x軸正向 に力を与えています。 この際、ForceMode.ImpulseをAddForceの引数に与えているのでより強い力が瞬間的に与えられるようになっています。

さらに効果音の再生のために、音声クリップを1ループだけ再生する PlayOneShot メソッドを使用して指定した効果音を再生します。

地面との衝突判定と効果音の再生

地面との衝突時にも効果音を再生します。今回は Collider コンポーネントを使用して衝突を検知しました。以下にプレファブにアタッチしたスクリプトを示します。

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class ColisionDetector : MonoBehaviour {
  // 球のプレファブにアタッチ
  
  private AudioSource m_AS; // 自分のオーディオソース
  
  [SerializeField] private AudioClip m_Clip; // 再生する音源
  
  private void Start() {
    m_AS = GetComponent<AudioSource>();
  }

  public void OnCollisionEnter(Collision other) {
    if (other.gameObject.tag == "Floor") {
      PlayShellSE();
      Destroy(this.gameObject, m_Clip.length);
    }
  }

  private void PlayShellSE() {
    m_AS.PlayOneShot(m_Clip);
  }
}

OnCollisionEnter は引数に Collision コンポーネントを取り、Collider同士が衝突したときにコールバックされます。この際、相手のゲームオブジェクトが持つタグが Floor である時に効果音を再生するように設定しました。

また、音声クリップの1ループの長さは length から取得できるので、再生終了後オブジェクトを消えるようにしてみました。

ということでお疲れ様でした。