ちゃっくのメモ帳

ちゃっくがメモしときたいことをメモしとくよ

ISUCON9の予選を敗退したっぽい

ISUCON

ISUCON9の予選にチームIQ1で参加しました。
チームのメンバーは僕(学生)、yaketake(社会)、zakuro(社会)でした。

予選から少し時間が経ってしまったので記憶が薄れかけているので、怪しい記述が多いですが、一応参加期を書きます。

朝9時半
集合。3人とも開始前に揃うことに成功した。

競技開始。とりあえずインスタンスの起動。
一応ここで詰まると辛いので，他の2人の監視のもとで建てる。
インスタンスの起動は事前に一通りやっていて良かった。ただ、ISUCON Discord見るとなんか免許証とか求められてる人がいるらしくてAlibabaに免許証提出するの嫌だなぁとか不安だったから問題なくインスタンスを建てれてよかった。
とりあえずチームIQ1の方針は複数台構成は競技終了1時間くらいでやろうねくらいの雰囲気だったのでとりあえずインスタンスは1台立てた。

インスタンスが起動したらとりあえずpythonに切り替えてベンチマークを走らせ，アプリケーションの把握。
この時点で確か1400点くらい。
今回のアプリISUCARIを開く。
とりあえずアプリはメルカリっぽいなにか。
ログインすると大量の画像が目に入ってくるので，とりあえずこの画像をnginxで静的に配信することにした。
これをやってる間にyaketakeさんはローカルでアプリが動くようにしていて、zakuroさんはソースコードを読んでいた。

nginxで静的に画像を配信してベンチマークを走らせるが点数は上がらない。
これは多分別に画像をDBに入れてるわけではなくflaskが配信してくれているのでそんなにコストは大きくなかったのだと思う。

次にとりあえず典型のN+1の解消をすることにする。zakuroさんはどこにN+1があるのかわかっているっぽかった。
zakuroさんとそれぞれどこのN+1を解消するか相談する。
数分返事がないと思ったら明らかなN+1を全部解消していた。（早すぎてビビった）
確かこの時点で点数が3500点くらい？

試しにcache-controlを設定したが、点数は上がらないのでcache-controlはとりあえず外すことにする。
nginxのworkerとmysqlのworkerを増やすが点数は上がらず。

このあたりでyaketakeさんがAPIが連続で呼び出されているところを見つける。
yaketakeさんはAPIコールを減らせないかとかAPIの使用を調べ始める。

(ここらから割と何していたか記憶がないので時系列ぐちゃぐちゃ)
slow queryを設定。すこしコストの大きいクエリはあるがこれ以上最適化できなかったり、アプリのパフォーマンスに対してクエリ処理のコストが低かったりで、とりあえず後回し。
ソースコードの@lru_cacheが気になる。これ、分散させたときに不整合の原因になりそうだから外したい。外してベンチマーク走らせてもそんなに影響がなさそう。
zakuroさんがなにかして5000点くらいまであがる(何をしてたか記憶がない)。
複数回ベンチマークを走らせるとfailしまくる。
「俺、またなにかやっちゃいました?」
DBがRedisに載せられそうという意見がでる。僕はそもそもDBがボトルネックになってる雰囲気がないのであんまり効果がないと予想して反対。
dstatを見ても別にCPUがネットワークの問題でもなさそうで分散すればいいというわけでもなさそう。
割と何をすればいいかわからなくなってきたので、プロファイラを動かした。
PythonのLineプロファイラを動かすとAPIの呼び出しがボトルネックになってることがわかった。同じ場所にN+1が紛れていたが、API呼び出しのコストが大きすぎてN+1の影響があんまり大きくないのでAPIをやっぱどうにかしたいという判断。
APIをまとめて呼び出せないかと思ったけど無理そう。とりあえず非同期にAPIを呼び出せばいいということで総意がとれる。
Pythonで非同期処理はasyncioを使えばいいらしいが、誰も使ったことがなくてここで戸惑う。
みんなで「Goにすればよかった...」って言い出す。
残り30分くらいでFailしない感じになったが残り15分くらいでgitがぶっ壊れる(え....)
というか、分散化に乗り出すのがおそすぎて分散させる時間が残っていない。
gitが壊れた結果、アプリケーションが動かなくなって焦る。
僕は別に分散用に用意しておいたインスタンスを分散用ではなくバックアップ用として動くようにする。
gitを直して残り数分でベンチを動かすとFailする。
このあたりでjobがリジェクトされたりしていたので、負荷が大きすぎてAPIの呼び出しに時間がかかりすぎてFail判定になっているのではないかと話すがどうしようもないのでクリックしまくってjobをなんとか投げるがFail。
最後は諦め。

感想

zakuroさんがN+1問題を解消する速度が早すぎる。
僕はなんかNginxとMysqlの設定を適当に弄ったりプロファイラ動かしてボトルネックになってそうな部分を探すだけをやっていた。
Pythonで非同期なんか直感的にかけない.....(慣れてないだけかも)
最後のベンチマークが詰まってるの、APIが返せてないんじゃないかって思うけど違うのかなぁ.....
というか、分散させる話は....? (ちゃんと時計を見て計画的にやりましょう)

フォントHackGenを入れたんだよっ

HackGen(白源)というフォントがあるらしいのでインストールしてみた。
ちょっと躓いたのでメモ。
環境はubuntu18.04
githubからリポジトリをcloneする。

git clone https://github.com/yuru7/HackGen.git

するとmake_hackgen.shがあるのでこれを動かせばいい。

ただし、自分の環境ではいくつかツールが足りず失敗した。
まずはaptでttxとttfautohintをインストールする

apt install fonttools ttfautohint

これでも失敗して、Pythonのassertで落ちてしまった。
自分の環境ではPython2のモジュールとしてfonttoolをインストールしていないのが問題だった

pip2 install fonttools

これでmkae_hackgen.shを実行すればbuildディレクトリにttfファイルが追加されるので、$HOME/.fontsにコピーしてfc-cache -fvを実行したら使用できるようになった。



いや、pythonのfonttoolsが無いとダメなの普通にわからないでしょ....
(というかpythonでfonttoolが無いというエラーを出してほしい...)

IQ1も就活したんだよっ

その他

りあんやうくさんの就活エントリに影響されて書きました。乗るぜこのビッグウェーブに。

りあんほど強くないので、修士卒の一般人の参考にはなるかと思います。


企業名とかは隠します。
知り合いで企業名とかも知りたいって人は言ってくれればサークル向けに書いたものを見せます。
rogyの人はrogywikiを見て。

先に結論を言うと4AC2WA1RE(2?)って感じです。

自己紹介と面接で話した内容

  • 競技プログラミング
    • Atcoder,Topcoder,Codeforcesで青底辺です
    • 後はICPC2017でつくばやタイに行ったりしましたが、これはチームメイトが強かったので、就活で競プロについて話す時は青底辺ですと言いました
    • そもそもあんまり就活で競プロについて話していません(これはレート的に話題にするほどの価値が無いと判断したので)
  • 研究
    • 学部ではデバッガの研究
      • 学部の頃の成果としては国際会議に通したり、国内で研究会に論文だしたりしました。会社によっては研究についてめちゃくちゃ聞かれてびっくりしました。正直学部の頃の研究は細かいところを忘れていたので焦りました。
    • 修士ではプログラミング言語の研究

あとはICFPCやってみたりISUCONやってみたりって感じですが、どちらも1回しかやってなくてゆるふわなのであんまり話題にしませんでした。

インターンは1年に満たないくらいの期間でA社に、夏に1ヶ月B社に行ってました。

後はenPITのITSPについて話しました。これは東工大が参加しているIT特別教育プログラムのチーム開発の授業です。

面接全体では、ITSPと研究の話とインターンが多かったですね。
特に企業はチームで動くことが多いからかITSPの話をすることが多かったと記憶してます。
(就活結構昔なので忘れてきてる)

就活準備

1月に1度だけアカリクのイベントに行きました。先輩の紹介で行くと1万円貰えるので金に目がくらんで飛びつきました。
行ったらハンドスピナーがもらえて大喜びしてしまい、ハンドスピナー回しながら逆求人するみたいな行為をしてしまいました。

あとは大学で開催されている説明会?の懇親会に行ったら、知らない人に「IQ1の人ですか?」って言われて怖かったです(誰だったんだあれは...)。

個人的には情報理工学院で開催されてるやつは行く価値はあるかもしれないけど、大学で開催されるやつはノイズが多すぎて微妙。

就活

就活は11月か12月くらいから初めました。結構早いと思うのですが、割とメンタルが貧弱なので早く内定を貰って安心したかったというのが大きいです。

α社

選考フローはWeb→1次面接→最終面接
でした。11月くらいに1次面接を、12月くらいに最終面接を受けました。

Webテストはただの競プロっぽいやつでした。

1次面接ではインターンの話とITSPの話を主にしましたが、半分くらいの時間を質問に使ってしまいました。
これは単純に向こうの話してくれた技術が面白かったので気になることを聞いてたら時間が消滅しました。

数日後に2次面接の日程調整をしました。
2次面接は2秒で終わりました(大嘘)。
正直2次面接の内容をあんまり覚えていません(すみません)。

2次面接が終わるとその場で内定をいただけました。
AC

β社

11月くらいに応募しました。
A4で3枚、英語の履歴書を要求されました。これを書くのはめちゃくちゃ疲弊しました。
提出した直後(数分後)に不採用のメールが来ました。
流石にあんまりなので、「これおかしくない?」みたいなのをサポートに投げたら、応募はActiveになったのですが、状態が不明でサポートにもう一度今の状態を質問したらあまりにも要領を得ないメールが返ってくるってのを繰り返した結果面倒くさくなったので放棄しました。
半年以上経った今でも応募状態がActiveになってるのですが何がどうなってるのかわからないです。
RE

γ社

面接では現CTOや前CTOと話しました。
ちょうどCTOが変わった後くらいだった(?)のでCTOの書いた記事くらいは読んでいきました。

話した内容は研究の話とITSPだったと記憶しています。

後日内定の連絡を頂きました。

最終的にどこに行くか迷ってるときにご飯とお酒を食べさせて頂いたり、お話を聞かせてもらったりしてくれて気にかけて頂いてありがたかったです。ありがとうございました。

AC

δ社

アカリクのイベントで話して、受けることにしました。

選考フローは1次面接→2次面接→不明です(WAしたので)

1次面接ではITSP、研究、競プロなど上で書いたことを全部話しました。しかし、詳しくは書きませんがなんかスイッチが入ってしまって、鉞マシーンとかしてエンジニアに向かって鉞を投げまくるバーサーカーになってしまいました。
ダメだと思ったけど後日次の面接の日程調整が入ってOK

2次面接ではどういうことが聞かれるかが前日に人事のかたから連絡が来たのですが、自分の中で答えを出せないまま面接を受けました。
2次面接では偉い人と面接をしました。基本的に話を聞いていました。話を聞いているとだんだん「ここは自分に合わないきがするなぁ」ってなってきました。
後日不採用の連絡が来ました。

WA

ε社

選考フローはコーディングテスト→1次面接→最終面接でした。

コーディングテストは普通の問題(とは?)でした。

1次面接は30分x4人でしたが、それなりの期間インターンをしていたのでお互いに聞くことがあんまりないというのを繰り返しました。

1次面接のあと、僕がインフルにかかったりして2次面接まで1,2ヶ月開けてもらいました。

2次面接も30分x4人でしたが、こちらは偉い人が多く、あんまり喋ったことがなかったのですが、どちらかというと会社選びのアドバイスを頂いたりしました。

後日内定を頂きました。

面接のたびにいろいろご飯を頂いたり、内定のときにお酒を飲ませて頂いたりしました。ありがとうございます。

AC

ζ社

1月の中旬に応募しました。
コーディングテストがあったりオンライン面接があったりオンサイト面接があったりします。

2月にオンライン面接を受け、3月にオンサイトでコーディングインタビューをしました。
コーディングインタビューでは4人で一部英語でした。
一部面接官の英語がわからなかったのですが、ホワイトボードも使えない状況になり「もう一度ゆっくり簡単な英語で喋ってくれ」を英語で喋る機械になってました。

社食は噂通り美味しかったです。

1週間くらいして不採用の連絡。
WA

η社

ソシャゲを作っている会社です。
アカリクのイベントでエンジニアと僕の研究について話をして盛り上がったので受けました。

ここはAtcoderでコンテストを開いてるところです。

1次面接はエンジニア2人と行いました。1時間くらい研究について話しました。学部の研究について記憶が薄れてて焦りました。1次面接はこれだけで実質論文発表でしたが、国際会議のときとかよりもいろいろ質問してもらえて嬉しかったですね。

2次面接のときにインフルエンザにかかって、リスケしてもらったのですが、かなり人道的な対応をしていただきました。こういうところでちゃんと対応してくれると信頼度が増しました。

2次面接もエンジニア+人事の方と面接。少し前にオンサイトコンテストでみた人が面接官でびっくりしたりしました。
この面接では、何ができるかを確認するみたいな感じだったと思いますが、あんまり覚えてません。

1週間後くらいに内定を頂きました。

AC

後日談: PPLにポスター発表しに行ったときに担当の人事の方にあってびっくりしました。

θ社

Atcoderでもコンテストを開いているが、それ以上に普通に有名な会社。
アカリクのイベントで人事の方とお話をしてうけることになったが、面接の予約が常に埋まっていて面接をすることなく辞退させていただいた。
受ける人が多いのでしょうがないと思う。

ι社

Atcoder Jobsから申し込んだ会社。
応募から1ヶ月以上連絡がなく、レート的に採用する気ないのかなぁと思ったりしていた。
後から連絡はあったが、あんまり連絡が遅いと気が萎えてしまい辞退。

どこに行くかの基準

どこに行こうかは割と迷いました。
ただ、あんまり悩んでも結論は出ないと思ったので自分の中で4月までに決めて連絡しようと思ってました。
が、スマブラをしてたら遅れました。

どこに行くか決める基準として、待遇とかも少し気にしたのですが新卒なので得られそうなスキルを考えたりしたほうが最終的に幸せかなぁとか考えたりはしました。ただ、どうしても答えは出ないので割と雑です。

あとは家からの通勤時間とかは考えました。家の立地的にどこも実家から通えてしまうので割とこれは気にしました。


あとはフレックスと裁量労働の話は聞いたけど忘れました。何が違うかは何回か調べたけど忘れました。
リモートは興味がなかったので僕の中では特に判断基準に含まれませんでした。
(インターンをいていたときに思ったんですが、リモートってチームの行動が難しくなったりしないんですか)

まぁ最終的には合わなければやめればいいくらいの気持ちで生きているので実はそこまで深く考えてないです。

就活を終えて

りあんやうくさんと同様スーツを着ることはありませんが、僕は別にスーツに対してそこまで抵抗がないのでオフィスカジュアル(謎)よりはスーツって言われたほうがわかりやすくて好きかもなぁくらいには思いました。

別に不採用だった企業に対してネガティブなイメージは無いです。ただ、あまりにも連絡がない企業に対しては割とネガティブなイメージをいだきました。


競プロで就活的な話が好きな界隈がいそうなので、そういう話をすると多分青底辺くらいだとあんまり嬉しみはないです。競プロできると主張するほど強く無い割に、やったこと無いってわけでもどういうアピールをすればいいかよくわかりませんでした。(あくまで僕の体感なので参考程度に)。
ただ、コーディングテストがあるならCF Div2 ABCくらいを30問くらい素振りしたほうが良いと思います。(Atcoderでもいいんですがコーディングテストの練習としてはCFの方がイメージしやすかったのはなんでですかね)

東工大生で就活に不安がある人はITSPを取ることをおすすめします。授業に沿ってるだけでチーム開発できて成果物が湧いてくるので自分で開発するきっかけがつかめない人はやるべきだと思ったりしました。

最初に書いたように、僕は研究、インターン、ITSPを軸に就活を進めました。この辺りで共通するのは「どういう失敗をしたか」とか「どのあたりが難しかったか」とかがどうしても出てくるので使いやすいネタになった感じです。


就活全体としては比較的承認欲求が満たされたのでむしろ楽しかったような気がします。
コーディングインタビューとか質問面白かったし、面接官がエンジニアだと会社の技術的な話を聞いたりできて普通に面白かったです。
あとは、ご飯が美味しかったので世間一般に言われているほど辛い作業でもありませんでした。
ESについても、これを書くのに苦労するところに応募するの、多分マッチしないので応募しないみたいなスタンスは多少ありました。
お祈りされるとどうしても悲しくなるのでかぐや様を読んだりして精神を回復したりしてました。

かぐや様の藤原千花を見ると2秒で精神が回復しました。どうも僕は夕立とか藤原千花のような見た目に弱いようです。
かぐや様は藤原千花も好きなのですが、途中から四条眞妃さんがかなり好きになりました。眞妃先輩の良いところは、本人は可哀想なんですが、石上くんに対して優しいところに惹かれました。特に、文化祭で石上くんがつばめ先輩を誘うように発破をかけるシーンが1番好きな眞妃先輩のシーンです。逆に藤原千花は見た目は好きなのですが、途中から異常者感がどうしても否めませんでした。でもかわいいのでオッケーです。
個人的には途中からストーリーが重くなってきてしまい、最初の軽いコメディだった頃のほうが作品としては好きだったなぁという気持ちもあります。現在発売されている最新刊の最後のほうが氷かぐや様が出てきて続きが気になる終わり方をしたので早く新刊が出てほしいのですが、話が重そうなのであんまり長く続くと読んでて苦しそうだなぁと思いながらもめっちゃワクワクして新刊発売を待ってます。

最後に

りあんよりも一般スペックの修士卒の就活エントリなので比較的参考にはなると思います。(レッドコーダーは人外なので人外の就活みても参考にならないでしょ！)

前にも書いたのですが、別に不採用でも悲しくなってもその企業を嫌いになったりはしないです。
コンテスト中にWAが返ってきたときのほうが明らかに精神状況悪いです。

しかし、あまりにも連絡がなかったりするとめちゃくちゃイメージが悪くなるというか、待ってる間割とモヤモヤするので勘弁してほしいです。もちろん企業はたくさんの学生を処理してて忙しいことは理解しているのですが、連絡がいつくらいになりますくらいの一報は欲しいです。1週間くらいなら別にいいんですが、1ヶ月は割と精神が参ります。

SRM 762 Div1 Easy LexicographicPartition

Topcoder 競技プログラミング

問題概要

community.topcoder.com

長さAの数列nを連続部分列に分解する。
ただし、連続部分列に含まれる要素の合計は正にならなくては行けない。
この時、Aの連続部分列を前から長さを見た数列をBとする。
辞書順最小のBを求めよ。

解法

前から貪欲するだけ。
A[i]以降を考えるとA[i] +... + A[j] > 0 かつ A[j] + ... + A[n-1] > 0となる最初のjを探索すれば良い。
これは求めるものが辞書順最小なのでj-iを最小にすることを考えると明らか。

class LexicographicPartition{
    public:
        vector <int> positiveSum(int n, vector <int> Aprefix, int seed, int Arange){
            vector<int> A(Aprefix);

            ll state = seed;
            for(int i=Aprefix.size();i<n;i++){
                state = (1103515245 * state + 12345);
                A.push_back(state % (2 * Arange + 1) - Arange);
                state = state % (1LL << 31);
            }

            vector<ll> sum(n+1,0); // sum[i] := A[0] + ... + A[i-1]
            rep(i,n){
                sum[i+1] = sum[i] + A[i];
            }

            cout << A << endl;
            cout << sum << endl;

            vector<int> ans;
            int i;
            for(i=0;i<n;){
                bool ok = false;
                for(int j=i+1;j<=n;j++){
                    // check [i,j)
                    if(sum[j] - sum[i] > 0 && (sum[n] - sum[j] > 0 || j == n)){
                        ans.push_back(j-i);
                        i = j;
                        ok = true;
                        break;
                    }
                }
                if(!ok){
                    cout << i << endl;
                    return {-1};
                }
            }

            vector<int> res;
            res.push_back(ans.size());
            if(ans.size() > 200) ans.resize(200);
            for(auto v : ans) res.push_back(v);
            return res;
        }
};
<||

* 感想
これを落としたのは反省。
落ちた理由は実装でDFSした結果計算量がO(N^2)になっていた。

ICFPC2019に参加したんだよ

破滅

追記

チームメンバーは僕の他にすごぷろ(@jke_null)、zakuro(@emotionalcattle)、kuwa(@lrmystp)、葦(@Ashur_titech)でICFPC 2019にチームIQ1として参加した。
一応使用言語は僕がC++、すごぷろさんがPython、zakuroさんがjs、葦くんがC++から途中でPythonに変更した感じ。

金曜日夜
問題を読んで「関数型おじさんの書いたなろう小説かな」って気持ちになった。

土曜日
問題概要を共有した後、僕が入力のパーサーを書き始めてバグらせる。デバッグしてたら後からパーサーの実装を開始したすごぷろさんと同時にパーサーの実装が完了する。
この間にzakuroさんが自動テストツールを作り始める。
IQ1は土曜日から開始したがコンテスト自体は金曜日の夜から始まっており、作業開始時点でteleportとcloneが追加されていた。
個人的には去年のICFPC的にcloneはlightningが終了した後に開始すると思っていたので驚いた。

基本的な方針としてすごぷろさんはとりあえずDFS+最適化でcloneにさっさと手をつけようとしていた感じだった。
僕はビームサーチで探索していこうかなという感じ。
葦くんは盤面をグラフにしてく方針を考えていたっぽい。kuwaさんもこれに賛成してた。

zakuroさんに「コマンドラインから動く自動テストツールが欲しい」って言ったら夕方には完成していた。流石って感じ。

1日目はビームサーチ書ききれずに終了。
すごぷろさんはDFSをするやつを書き終えていて流石に速いなあという気持ちになった。
葦くんも実装が完了していなかった。

日曜日
すごぷろさんがいつcloneを動かしてたかしらないけど日曜日にはdfs+cloneが動くようになっていた。
僕はビームサーチを動かしたら最後の方に盤面が小さい穴だらけになってビームサーチである程度減らした後にBFSで近いところにから埋めていくという方針に変更。

また、日曜日の朝には新しい部門が生えていた。Lambda-coinをマイニングするという部門で土曜の23時から開始していたが、やるなら早い方が良かった。(これは仮想通貨の特性上)。
すごぷろさんは気がついたらマイニング用のパーサーを書いていてくれた。
すごぷろさんとマイニングしたほうが良いか相談したけど他のチーム見る限り2万点くらいは取れそうな雰囲気を感じてやったほうがいいかなぁくらいの感じになったので葦くんに投げた。
このマイニングが思ったより大変で大まかな方針は経っていたが実際にそれでいけるかは問題によるなぁという気持ちは会った。

僕はビームサーチ→BFSという方針を相変わらずやっていたが、Wheelの実装でバグらせていた。Wheelの使用を途中でキャンセルできないのでBFSで1マス移動で探索するとバグることに気がつくのに時間がかかった。
すごぷろさんは多分DFSとCLONEの最適化をしていたんじゃないかなぁ(多分)


月曜日
社会人組は出勤してしまったので僕と葦くんだけでやっていた。
葦くんはマイニングの実装が大変そうだというのと方針が微妙で頭を抱えていた。
15時くらいに「盤面全体を初めからiSeqとoSeqの両方が含まれないように一定サイズで区切って最小全域木を構築したら行ける気がする」とか適当なことを言ったら葦くんは実装をしてくれたけど、これは実際に入力に対してやろうとすると区切ったブロックが小さくなりすぎて制約を満たせなかったらしい。この時点でマイニング終了なので諦めた。

僕はビームサーチ+BFSで1~150のケースで割とすごぷろさんのケースに勝てていたのでビームサーチである程度削った後はBFSで最寄りの空きますに移動したあとにそこからビームサーチをし直すことを繰り返すという方針に拡張していた。
実際にやろうとすると計算コストがおもすぎるが、そこはサーバーで4並列で動かせばまぁなんとかなるやろという雑な方針。
更に、腕の優位性は大きい盤面で効いてきそうというのと大きい盤面のほうがスコアが重要になってくるはずなので開始地点から近い腕は最初に取っておくことにした。
ビームサーチの評価関数は「残り未到達領域+ターン数-腕の数」とした(小さい方が優秀)。
ビーム幅20~30くらいで深さは20~100くらいで探索した。
これをサーバーで150ケース計算したら月曜日が終了してしまった。

反省

ビームサーチを使うと、どうしても1,2マスよりも大量の未到達マスがある方向に行ってしまうので最終的にあちこちに未到達マスが残ってしまい、最後の方で大量の移動をすることになってしまう。
これはビームサーチに探索の深さ制限を設けてるからであるが、この制限は計算時間的に外すことができないのでホントは1,2マス残った部分を評価関数に含めるべき。ただ、これを計算すると評価コストが上がりすぎてビーム幅か探索の深さを諦めることになるので却下。
結果としてはビームサーチを選択したのは余り良い方針ではない。
この問題は明らかにTSPなので焼きなまし+2-optとかが良いらしい。
この辺りの勘が働かなかったのはどうしてもマラソン系を普段やらないからというのと、ちゃんと考察せずに思いつきの方針で突っ切ろうとしたのがダメ。

後は実装力が低すぎた。実装中になって「あー、この方針このあたりでバグるなぁ」をいくつも見つけてしまったのでこういうのをなくすべきなんだろうなぁという気持ちになった。(あとは普通にバグらせる(普通にバグらせるな))

pthread_barrier_waitを使用した同期についてのメモ

マルチスレッド プログラミング

C言語のpthreadライブラリには同期機構としてpthread_barrierが実装されている。
これはバリア同期のためのライブラリである。(バリア同期についてはいつか記事を書こうと思ってます)

pthreadのバリア同期を使用するときはpthread_barrier_waitを使うことで条件が満たされるまで実行がブロックされる。
これはシグナルが送られるまで実行をブロックする。そのためCPU時間を消費しない。
pthread_barrier_waitのmanを見るとsignalって文字は出てくるんだけど明示的にbusywaitじゃなくてsignalを使用してCPU時間を消費せずにブロックするって書かれていないので実験で確かめておきたくて実験をしたのでメモ。
CPU時間を消費しないことを確かめるために下のようなコードで実験をした。

#include <stdio.h>
#include <unistd.h>
#include <pthread.h>

#define THREAD_COUNT 2
pthread_barrier_t barrier;

void func1(){
    sleep(10);
    pthread_barrier_wait(&barrier);
}

void func2(){
    pthread_barrier_wait(&barrier);
}

int main(){
    int barrier_init = pthread_barrier_init(&barrier,NULL,THREAD_COUNT);
    pthread_t threads[THREAD_COUNT];

    pthread_create(&threads[0],NULL,(void*)func1,NULL);
    pthread_create(&threads[1],NULL,(void*)func2,NULL);

    pthread_join(threads[0],NULL);
    pthread_join(threads[1],NULL);
    return 0;
}

このコードはスレッド1は起動直後に10秒sleepする。このsleepはCPU時間を消費しない。
そしてスレッド2は起動直後にバリア同期によってwaitする。
バリア同期のカウントは2で設定しているのでスレッド1が10秒後にバリアに入らない限りスレッド2はブロックされる。
そして、スレッド1とスレッド2が終了するとプログラムは終了する。

このプログラムの実行時間をtimeコマンドで調べると次のような結果になる。

real 10.00
user 0.00
sys 0.00

ここで注目すべきはuserとsysである。
user modeでも, kernel modeでもCPU時間が消費されていない。
これでpthread_barrierによるブロックの間はCPU時間は消費されないことを確認できた。
(もし、CPU時間を消費するのならスレッド2は10秒分のCPU時間を消費しているはずなので)

pthreadライブラリにはspin_lockのライブラリもある。これはビジーウェイトしているように見えるのでCPU時間を消費するかもしれない(未検証)。


pthread_barrierがブロック中にCPU時間を消費しないことを確認したかったので行った実験なので面白いものではないのですが、この辺り明示的に書いてあるところって無いのかなぁ.....

詳解UNIXプログラミング 第3版

詳解UNIXプログラミング 第3版

TCO2019 Round1B Hard EllysPearls

解説ACしたので解法をメモっとく。やはりDPの遷移を考えるのが苦手すぎる。
地頭不足を感じてしまう....


問題
community.topcoder.com

公式解説
www.topcoder.com


問題概要

長さNの配列pが与えられる。配列の各要素は1~Mのいずれかである。
次の操作を繰り返すことで同じ値の要素同士は隣り合うように並び替える。
(例えば[1,2,3,3,1]を[2,2,1,1,3,3]のように並べ替える)

操作: 配列の要素を1つ選択し、任意の場所に移動させる

この時最低で何回操作を繰り返せば配列が同じ値の要素同士が隣り合うように並べられるか?

解説

bitDPをする(制約を見るとそれくらいしかできることがない)。
次のようなdpを考える。
dp[i][j][stae] := p[0,i)に対して考える。状態state(bit)に対応する値が確定しており、最後に確定した値がjのときの最低操作回数。(ここで状態stateが0011ならば0,1が確定していると考える)

例えば、サンプル1を考えるN=11,M=4,p={2, 4, 1, 1, 1, 3, 2, 1, 4, 2, 2}. pを0-originにして{1,3,0,0,0,2,1,0,3,1,1}とする。
dp[3][0][1011]は{1,3,0}に対して最後が0になっているような操作回数なので0。

もう1つ例を考える。N=5,M=2,p={0,1,1,0,0}とする。
例えばdp[0][*][*]は初期状態として0である。(操作0回で実現可能)

  • dp[0][*][*]からp[0]=0を観測して次の状態に遷移する
    • dp[1][0][b01] = 0 (0の位置確定)
    • dp[1][0][b11] = 0 (0,1の位置確定。 最後が0なので1...10...0という並びは確定する)
    • dp[1][1][b10] = 1 (1の位置確定。0は以降の0の出現で場所が確定し、p[0]はその位置への移動が発生する)
    • dp[1][1][b11] = 1 (0,1の位置確定。最後が1なので0...01...1という並びになることが確定する)

状態遷移は次のように考えられる。
以降、表記として{0,1,2}は0,1,2の位置が確定したことする。また{0,1,2}<2>が0,1,2の位置が確定し、最後が2が確定したとする。更に、{{0,0,1,2,2}}は位置が確定した部分の配列を示すとする。

  • 観測した状態p[i]の位置が確定している場合
    • もしp[i]が最後に確定した値ならば操作をしなくて良い
      • 例えば {0,1,2}<2>の状態でp[i]=2を観測したらそのまま結合すれば操作0回でよい。つまり、{{0,0,1,1,2,2}}→{{0,0,1,1,2,2,2}}とすればよい
    • もしp[i]が最後に確定した値で無い場合、操作1回を行って確定位置に移動する必要がある
      • 例えば {0,1,2}<2>の状態でp[i]=1を観測するとする。つまり{{0,0,1,1,2,2}},p[i]=1 となってたらp[i]=1を移動して{{0,0,1,1,p[i]=1,2,2}}とする
  • 観測した状態p[i]の位置が確定していない場合
    • p[i]の位置を確定する
      • 例えば{0,1,2}<2>でp[i]=3を観測したとする。この時{{0,0,1,1,2,2}}→{{0,0,1,1,2,2,p[i]=3}}とすればよい。この時、操作は不要である。
    • p[i]は移動することだけ決定して、以降のp[i]と同じ値のときに確定する。
      • 例えば{0,1,2}<2>でp[i]=3を観測したとする。この時{{0,0,1,1,2,2}}だったとするとまだp[i]=3を付け加えずに、iの状態でp[j]=3を観測したときに{0,1,2,4,5,3}<3>とするか、更に先延ばしにするかを決定する。ただし、この時p[i]=3は必ず後ろに移動することになるので1回は操作を行う必要がある。


以上の遷移を行うとdp[N][*][*]の最小値が求める値となる。

constexpr int INF = numeric_limits<int>::max() / 3;
int dp[51][16][(1<<15)];

class EllysPearls{
    public:
        int getMin(int N, int M, vector <int> p){
            rep(i,N) p[i]--;

            rep(i,N+1) rep(j,M) rep(k,(1<<M)) dp[i][j][k] = INF;
            rep(i,M) rep(j,(1<<M)) dp[0][i][j] = 0;

            rep(i,N){
                rep(j,M){
                    rep(mask,(1<<M)){
                        if(!(mask & (1<<j))) continue;
                        if(dp[i][j][mask] == INF) continue;

                        if(mask & (1<<p[i])){
                            if(p[i] == j){
                                chmin(dp[i+1][j][mask],dp[i][j][mask]);
                            }else{
                                chmin(dp[i+1][j][mask],dp[i][j][mask]+1);
                            }
                        }else{
                            assert(p[i] != j);
                            chmin(dp[i+1][j][mask],dp[i][j][mask]+1);
                            chmin(dp[i+1][p[i]][mask | (1<<p[i])],dp[i][j][mask]);
                        }
                    }
                }
            }

            int ans = INF;
            rep(i,M) rep(j,(1<<M)){
                chmin(ans,dp[N][i][j]);
            }
            return ans;
        }
};

感想

bitDPだと思いつくのは、制約を見ると明らか。
状態の持ち方も「最後に○○した値」を状態に持つのも典型的なDPだと思う。

遷移も気づけば割と自明だったと思うが思いつかなかった。
こういう遷移が構築できなくてDPがめちゃくちゃ苦手。
今回だと、「p[i]が確定していないときに位置確定をあとに回す」というような遷移が思いつかなかった。