Macbook Proのキーボードのチャタリングが直らなくてキレたのでソフトウェア的に直した話

タイトルの通りです。
つい3ヶ月ほど前に購入したMacbook Pro 2018ですが、キーボードの特定のキーが一定確率で2回押されてしまうという不具合を踏みました。
調べてみると何件か同様の症状を訴えている記事を見かけたので、よくあるハードウェアの不具合なんだなと思い無償の修理に出しました。
修理までの対応は電話を通じてとても丁寧にやっていただき、商品も配送修理に出してからわずか2日で帰ってきたのでその対応の速さにはとても感謝しています。
修理から戻ってきた時のMacはキーボードの交換をはじめ他の場所もピカピカになっていて、問題のチャタリングも無くなっていました。
やっとあの症状から解放されたとこの時は安心していました。

しかし...
修理から戻ってきて1ヶ月ほどたち、作業をしているとまた例の症状が現れたではありませんか。
もちろんまた修理に出せば無償でやってくれてすぐ返ってくるでしょう。でもなんかまた手続きをするのが面倒臭かったので、ソフトウェア的な解決手段が何かないかなと考えてみました。

調べてみると、まずKarabinerというMacにインストールできるキーボード操作ツールが引っかかってきました。これの設定ファイルにある「連続して反応する時間の最小値」みたいのを設定すればチャタリングは回避できるようでした。早速インストールしてその設定を探してみたのですがそんなものはどこにもない。
他の更新時期の新しいサイトをみたらわかったのですが、その機能は少し前のアップデートで削除されたようでした。やれやれ。

そのあとに見つけたサイトがチャタリングを抑制するプログラムを裏で走らせておくというものです。参考にしたのは以下のサイトです。

macOSのチャタリングをソフトウェアで対応する:株式会社サブスレッド

基本的にこのサイトに書かれている通り、レポジトリをgit cloneしてmakeしたファイルを実行すれば指定した間隔以下の入力を無視することができます。
半信半疑でやってみましたが、思ったよりうまくいったので驚きました。
僕はしきい値の変更を行いました。デフォルトの値(100ms)だとたまにチャタリングがすり抜けてしまうことがあったため、値を120msに変更しました。
やり方ですが、レポジトリ内のdebounce.mを開き、15行目にあった以下の部分を書き換え、再びmakeを行います。

...
#import <Foundation/Foundation.h>
#import <AppKit/NSEvent.h>

#define DEBOUNCE_DELAY 100 // ここの数値を変える
#define SYNTHETIC_KB_ID 666
..

こうしてチャタリングが解消することを確認し、これをdaemonを用いて起動時に毎回自動で立ち上がるように設定したのですが、先ほどのページ通りに行なってもうまく動きませんでした。
おそらく実行権限などの問題と思われますが、とりあえず実行ファイルのパスを/usr/local/binではなく自分でcloneしたディレクトリに設定することで無事動くようになりました。例えば、.plistファイルの中身を下のような感じに書き換えます。

    <array>
        <string>/Users/username/debounce-mac/debounce</string>
    </array>

これでとりあえずチャタリングは回避できました。あまりに高速に同じキーを押さない限り、正しいものが入力されないということはないと思います。
このまましばらく使ってみて、やっぱり使いづらさが出てくるようならもう一度無償修理にでも出そうと思います。

この記事が同一の症状が出てる人の参考になればなーと思ってます。 バタフライキーボード、色々問題点が多いらしいのでこういう不具合が減ってくれるといいのですが...

AtCoder Grand Contest 029

久しぶりのAGCでDまで時間をかけて考察したので残しておこうと思う。
本番は比較的速い時間にBを通すことができたので青パフォを得ることができた。
欲を言えばDは通せたなーと思ったが、まぁいいでしょう。

A - Irreversible operation

WとBを何回入れ替えることができるかという問題。
できるだけWを左に寄せればいいんだなーというのはすぐ気づき、ゆったりと実装してAC。
みんなの解くスピードが速すぎて順位表みてびびった。A問題のWA恐怖症なので結構念入りに確認してたのもあるかもしれない。

B - Powers of two

和が2のべき乗となるようにペアを組んだ時のペアの最大数を求める問題。
とりあえずN = 200000だからdpとかは無理そうだからソートしようってなってソートする。下から見ていったが貪欲に決めていったら決まらないことに気づく。例えば {1, 3, 15, 17}と{1, 3, 5, 15}の組み合わせだと{1,3}で組んでいい時とダメな時がある。

しばらく考えて上から貪欲に見ていくとうまくいくことに気づく。上の2つの例でもうまくいく。

それでは大きい数から見ていって、ペア候補となる数はどのようなものがあるかを考えてみる。注目する数をKとすると、ペアとなるべき数Xは
 K+X=2^t, X\leq K
この条件を考えると、 2^tの表す値はKより大きな最小の2のべき乗のみを考えればよいことがわかる。
たとえば、K=14であったら、14+X=2^4=16のみを考えればよく、14+X=2^5=32を考える必要はない。なぜなら後者を考えるとXは必ずKより大きな数になってしまうからである。
したがって、大きい順に見ていき、まだ使われていないペア候補が見つかればそれを使ってペア数をインクリメントすればよい。まだ使っていない数を見つけるために二部探索などを使っている人もいたが、mapを用いて使える残りの回数を持っておけばいいと思う。
atcoder.jp

C - Lexicographic constraints

いくつの文字数を使えば辞書順に並ぶような文字列を構成できるかという問題。コンテスト終了後に解いたが、かなり実装に手こずってしまった。

当然使える文字数が多いほど構築できる可能性は高くなるので、最小何文字を使えば可能かという二部探索の問題と捉えることができる。ここは経験があれば割と気づきやすい部分だと思うが、難しいのはこの判定を実装する部分である。  
文字列長を左から順にみていく。もし前の文字列より後の文字列の方が大きければ末尾に'a'をその差分だけ足すのが最小とわかる。この場合は問題ない。
逆に前の文字列長が後の文字列長以上である場合には整数の繰り上がりのように最小の位のアルファベットを移動させていくことになる。この最小の位の位置は小さい方の値によって決定する。したがって文字列が'aaaa'の状態で文字列長が4から2へと遷移すれば上から2文字目のaがインクリメントされ結果として生じる文字列は'ab'となる。
この実装が思ったより難しく、文字列を圧縮したりstack使ったりする方法が色々紹介されていたが僕はmapのみを使うことにした。
具体的には、文字a,b,c...を0,1,2...とし、i桁目の文字をmp[i]というキーバリューの形で保持する。
K種類の文字列を使うとき、値を更新する桁を下から見ていき、値がK-1を超えたら次の桁へ繰り上がるということを繰り返す。
そうして繰り上がりがK文字以内でできなくなればそのKでは不可能と判定できる。
ここの判定はAtCoder公式の解説動画がわかりやすいと思う。

コードはこちら。
atcoder.jp
このコードでひたすらバグに悩んだのは45行目で特定の桁から下の数値をリセットする部分。これをしていなかったので桁の繰り上がりが正しく行われていなかったようだ。数ケースだけ落ちると原因がホントわかりづらい...

D - Grid game

800点問題。なのだがさすがに800点にしては簡単だと思う。800点問題初AC。
先攻はできるだけ下に行き続け、後攻はたどり着くのが可能な範囲で最も近い行き止まりをめがけて進むのが最適だとわかるので、まずはたどり着くことのできるマスの範囲を絞る。
高橋くんが先攻で下に移動した後、後攻の青木くんが右に進むことができるかできないかで経路が変わります。青木くんは必ずしも右に行かなくてもいいのだが、まずは行ける限り右に行くとして経路を決定する。
すると以下のようになる。
f:id:yuji9511yuji:20181218221531p:plain
青木くんが最も右に移動した場合に図のような経路になるので、青線で囲った部分および経路上に関しては青木くんが自分の意志で移動できることになる(高橋くんは進む以外に選択肢がないため)。
したがって、この範囲の中から最も早くぶつかる(=最もX座標が小さい)点に行くのが青木くんにとって最善になる。
XとYが直感と逆なのでそこだけ気をつけよう。
atcoder.jp

Code Thanks Festival 2018に参加してきました

最近あまり競プロできていなかったので久しぶりの更新です.

さて,人生初のオンサイトコンテストであるCode Thanks Festivalに参加してきました!
f:id:yuji9511yuji:20181126231633j:plain
おそらくレベル的にはThanksもまだ厳しいくらいだったのですが,たまたま予選Bで相性のいい問題が早解きできたので運よく参加させていただくことができました.
参加者のレート一覧みたら下に10人もいなかったですね,最頻値が青なので順位表みただけでも少しひよってました.

会場はとても広く綺麗な場所で,お菓子とか飲み物も充実していたのでとても好印象でした.

あと,chokudaiさんが会場内をぶらぶらしていたので声をかけたら噂のAtCoderステッカーをくれました.ステッカーが徐々に増えてくると強者になった気がしますね(気のせい).会場で生ファボ爆を披露してるのも面白かったです.f:id:yuji9511yuji:20181126232503j:plain

昼にでた弁当にリクルートさんの財力を感じました.叙々苑と何かと何かの三種類があったのですがぼうっとしていたら叙々苑が一瞬で無くなっていました.みなさんこういう時は素早い.代わりに食べた牛すき弁当もめちゃくちゃ美味しかったです.多分どれも2000円近くしそう...


12時からコンテストが開始しました.
制限時間が3時間というのをみて,おそらく今の実力だと300くらいまで早解きしてあとはずっと唸ってたら終わりそうだなーと思ってたらその通りになりました.
BのWA量産の焦りは若干ありましたが,A~Dは特に問題なかったです.順位表見てほぼ全員がDまですぐ解いているあたりやっぱり選ばれた人たちしかいないんだなーと思いました.

ほとんどの時間はEを考えていましたね.制約的にN^3程度のDPだろうというところまではたどり着くものの,そこからindexをどう設定してどう遷移していくみたいな部分の考察がまだできませんでした.解説見ても簡単じゃんとはならなかったのでまだ精進が足りないですね.

パーカーは上位50人で,Eまでをある程度早く解いた人がボーダーだったのでちょっと厳しかったですね.まぁ青コーダー中位に勝てるわけもなく.

コンテストが終わったあとは懇親会でした.みんなのビンゴカード見てるとそれぞれ独自のこだわり(特に好きな言語,好きなアルゴリズムあたり)を持っていて面白かったです.

服装に個性を見出してる人も結構いましたね.kyopuro_friendsさんはどこからどう見てもサーバルちゃんでしたし,C++完全に理解している人とかいろんな人がいました.何か自分を特徴付けるもの身につけていって特定してもらうみたいなことするのも賢いですね.

もう少し界隈で知り合いが多いとオフ会みたいな感じで盛り上がったのかもしれないですけど,まだ始めたばっかりでオンサイトの経験もなかったのでこれからその辺のコネクションは作っていきたいですね.

懇親会でもchokudaiさんのAtCoder株式会社に関するいろんな裏話を聞けたので面白かったです.クソマイナー言語に対応するのにリソース割く必要性とか攻撃に対する対応のめんどくささとか,あと今後のARCの開催候補日(まだ非公表)とか教えてくれました.

いろんな人と話して美味しいものも食べ,とても満足のいく初オンサイトでした.あとは自分の競プロの腕を磨くだけですね.来年は少なくとも青色になった状態で迎えたいと思います.
最後に今回の戦利品です.交通費も支給されているしこれだけいただけるなんてオンサイト素晴らしいですね!
f:id:yuji9511yuji:20181126234101j:plain

多分1月にあるDDCCにも出場できそうなので次のオンサイトも楽しみにしています!

AtCoder Beginner Contest 113

さっさと3完したけどDの解法が生えずに終了。
だいたい解法がDPの時はいつもこんな感じなので現状では良しとしよう。

A - Discount Fare

X + Y/2をする。

B - Palace

一個ずつ比較していって平均との差が最も小さいindexおよびその差を記録しておく。
本番では誤差の影響出ないだろうとdouble型使ったけど1000倍してintで解いた方が賢いね。

C - ID

特に考えることはなく実装あるのみ。 vector< pair< int, int > >を用いてP[i]とY[i]を格納した後、県の番号の昇順、県の番号が同じなら年代の若い順に並び替える。ソートする関数はこんな感じかな。

typedef pair<ll, ll> lpair;

bool comp(lpair p1, lpair p2){
    if(p1.first == p2.first){
        return (p1.second < p2.second);
    }
    return (p1.first < p2.first);
}

vector<lpair> lp;
sort(lp.begin(), lp.end(), comp);

最後の出力のために、もともと何番目にあったかを保持しておく必要がある。方法としてはmap使う or pairの中に何番目だったかの変数をもう一個追加するのが良さそう。圧倒的にmapの方がラク

D - Number of Amidakuji

解説みたらすんなり理解できたのはよかった。ただ本番中には思いつかないと思った。

「今上から何段目、左から何列目にいて、そこまでにあり得る場合の数」を考えるとそのさきの経路はその値を元に計算できる、つまり部分問題として捉えることができる。

この場合の数がdp[i][j](上からi段目, 左からj列目)で、これを上から下に進めていくことで求める値 dp[H][K]が出てくる。dpの計算は前準備さえすればループ回してやるだけなので省略。

この問題の肝となるのが「i段目からi+1段目に移動するときのその段の線の書き方は何通りあるか」ということである。

このパターンは段によらず一定なので「各段において、列jから列kに移ることができる線の書き方は何通りあるか」というものを求めてあげれば良い。

二次元配列で持つとすればi => jの移動の総数はnum[i][j]となる。

W-1本の線が存在するかどうかはW-1ビットの数値で持ってあげるとよい。隣り合うビットが1になるものを排除するにはどうしたらいいかなーと考えていたところ、TLで「i & (i <<1)がtrueなら排除すればいい」というものを見つけた。頭良すぎでは。

あとはダメなものを排除した全パターンにおいてi => jの移動が可能なnum[i][j]をインクリメントしていけば良い。
もう少し詳しく言えば、それぞれのパターンにおいて縦線につく横線が0本ならnum[i][i] += 1をし、横線があれば、その横線によって移動する先をjとしたときnum[i][j]+=1, num[j][i] += 1をしてあげれば良い。
一番端の縦線のみ少し条件が違うので注意する。

W = 8の時(i,j)要素がこんな感じになれば正しく計算できてると思われる。

21 13 0 0 0 0 0 0
13 13 8 0 0 0 0 0
0 8 16 10 0 0 0 0
0 0 10 15 9 0 0 0
0 0 0 9 15 10 0 0
0 0 0 0 10 16 8 0
0 0 0 0 0 8 13 13
0 0 0 0 0 0 13 21

当然、2個以上離れた要素では0になっていることがわかる。

そろそろDPに慣れていかないとなぁ(毎回言ってる気がする)

C++でnCkやnPkを全列挙する関数

n!通りの順列を全列挙する関数はnext_permutationという備え付けの関数を使えばできたが、next_combinationなるものはどうやら存在しないようだった。
例えば「N個の要素からK個選んだ時の和」などを考えるとき、combinationのパターンを全列挙したくなる時が出てくる。
きっかけになったのが以下の問題。この問題だとNとKが固定されているのでこんな大げさに考えなくてもいいのだが、知っておいて損はないだろうと思った。
beta.atcoder.jp

関数の実装方法について考察している記事がいくつかあったので自分で一から作ろうかとも思ったが、実装がわかりやすく直接貼り付けていい感じに動くものが見つかったので今回はそれを使うことにした。時間があったらじっくり考えます。
参考にしたのはこのページ。
stackoverflow.com

以下がサンプルコード。NとKの値を入力するとN個からK個選ぶ組み合わせを全列挙する。

#include <bits/stdc++.h>
#define rep(i, m, n) for(int i = m; i < (n); i++)
#define print(x) cout << (x) << endl;
#define printa(x,n) for(int i = 0; i < n; i++){ cout << (x[i]) << " ";} cout << endl;
#define printa2(x,m,n) for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ cout << x[i][j] << " ";} cout << endl;}
#define printp(x,n) for(int i = 0; i < n; i++){ cout << "(" << x[i].first << ", " << x[i].second << ") "; } cout << endl;
#define INF (1e18)
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
typedef struct{
    int x;
    int y;
} P;
typedef struct{
    ll to;
    ll cost;
} edge;
typedef pair<ll, ll> lpair;
template <typename Iterator>
inline bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
   /* Credits: Thomas Draper */
   if ((first == last) || (first == k) || (last == k))
      return false;
   Iterator itr1 = first;
   Iterator itr2 = last;
   ++itr1;
   if (last == itr1)
      return false;
   itr1 = last;
   --itr1;
   itr1 = k;
   --itr2;
   while (first != itr1)
   {
      if (*--itr1 < *itr2)
      {
         Iterator j = k;
         while (!(*itr1 < *j)) ++j;
         iter_swap(itr1,j);
         ++itr1;
         ++j;
         itr2 = k;
         rotate(itr1,j,last);
         while (last != j)
         {
            ++j;
            ++itr2;
         }
         rotate(k,itr2,last);
         return true;
      }
   }
   rotate(first,k,last);
   return false;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N,K;
    cin >> N >> K;
    vector<ll> v(N);
    iota(v.begin(), v.end(), 0);
    do{
        printa(v,K);

    }while(next_combination(v.begin(),v.begin() + K,  v.end()));
}

next_combination関数がメインとなる部分。この関数を通した後、先頭K要素を取得することで今回求める組み合わせを全て出力することができる。

なお、iotaは指定した数値から始まる数列を生成する関数。原始関数のι(イオタ)が由来だとか。
この関数を用いるとN!の全列挙ではTLEするようなケースでも組み合わせを求めることができる。
試しにいくつかの(N,K)でやってみたところ、(20,10)や(100,3)程度なら高速に動作した。
オーダーがどれくらいか見積もることができなかったけど、Nがそれほど大きくなければO(N^K)くらいで動いている気がする。
誰かちゃんとしたオーダーがわかる人がいたら教えてくだされ。

追記:
next_combinationで生成された、先頭からK個の数列がCombinationということは、その部分数列(ソート済み)をnext_permutationにかけてあげればpermutationの全列挙も可能だということに気づいた。
先ほどのコードのwhile文のところを

    vector<ll> v2(K);
    do{
        rep(i,0,K){
            v2[i] = v[i];
        }
        do {
            printa(v2,K);
        }while(next_permutation(v2.begin(), v2.end()));

    }while(next_combination(v.begin(),v.begin() + K,  v.end()));

みたいにすればv2にはnPkの全列挙が入るね。やったね。
計算時間はK!倍になるのかな、いや律速はnext_combinationだからそこまで変わらないのかな。よくわからず。

なんか全体的にもっと速い方法がある気がするなぁ。突き詰めてくと面白そう。

MacでDockの日本語表示が文字化けしてしまった

ふと自分のMacのDockerのtooltipをみたらこんな感じになってました。
f:id:yuji9511yuji:20181030223213p:plain
文字化けですね。何やらunicodeっぽい何かが出てきてしまっています。

原因は突き止められていないんですが、変わったことといえば自分のポケットWifiを自分のMacBookに接続したことくらいなので、多分その時に自動的にインストールされたドライバとかが原因ではないかと思われます。

とりあえず、ググって上の方に出てきた

$ killall Dock

こいつをターミナルで実行してみたが解決せず。

そのあと別のページにあった「/Library/Preferences/com.apple.dock.plistを消してDockを再起動」を実行したら直りました。つまりこんな感じですね。

$ rm /Library/Preferences/com.apple.dock.plist
$ killall Dock

これ叩いて念の為Macを再起動してあげればうまくいくと思います。
Speed Wifi nextのドライバには気をつけましょう...

C++の約数とか使う時用の関数

O(\sqrt{N})なのでN=1e10とかなら動くはず。

vector<ll> divisor(ll M){ //約数の全列挙
    vector<ll> dd;
    for(ll i = 1; i*i <= M; i++){
        if(M % i == 0){
            dd.push_back(i);
            if(i * i != M){
                dd.push_back(M/i);
            }
        }
    }
    sort(dd.begin(), dd.end());
    return dd;
}
vector<ll> factor(ll M){ //素因数分解
    vector<ll> dd;
    if(M == 1){
        dd.push_back(1);
        return dd;
    }
    for(ll i = 2; i*i <= M; i++){
        while(M % i == 0){
            dd.push_back(i);
            M /= i;
        }
    }
    if(M != 1) dd.push_back(M);
    sort(dd.begin(), dd.end());
    return dd;
}

よくある処理を使いやすい関数にまとめていく作業って大事。