Qtumという暗号通貨を買った。この暗号通貨はProof of Stakeを採用している。マイニング報酬を得るために普通はクライアントをずっと立ち上げておかなければいけないのだけれど、Qtumはstakingを他人にdelegate（委任）することができる。

で、良く分からずにその辺の操作をしていたら、4,000円分くらい溶けた。悲劇を繰り返さないようにメモを書いておく。

Delegationを開始するには約1 QTUM、delegationを中止するには約0.02 QTUM掛かるので注意。

あと、delegationを受け付けるようにした。マイニング報酬のうち5%を私が受け取る。デフォルト設定だと最小100 QTUMからのところ、最小10 QTUMから受け付けるようにしている。よければ使ってください。ただ、delegateする前にこの記事を一通り読むことをおすすめします。

https://gist.github.com/kusano/c9be0020210b5dee82e2a6063293af26

Qtumとは

coin.z.com

日本語だとこれが一番詳しいだろうか。

BitcoinとEthereumのいいとこ取りというか、プログラムの作りとしては、Bitcoinがベースになっている。Bitcoinの送金の認証の部分は簡単なスクリプト言語になっている。ここに、コントラクトを作成する命令や、コントラクトを実行する命令を追加している。

一通り触ってみた感じ、とても出来が良い。ブロックチェーンのエクスプローラーがしっかりしているのも良い。

qtum.info

Proof of Stake（PoS）とは

以前に書いた。

qiita.com

Bitcoinの電力消費は以前から話題になっている。それを解決するProof of ○○として記憶容量があるのだけど、それもちょうど今日話題になっていた（その用途なら新品よりも中古のHDDを買い漁りそうな気もするが……）。

pc.watch.impress.co.jp

取引の正当性を証明するのに何らかのリソースを使うのではなく、そのコインを持っていることのみを使うのは究極の解決策のような気がしてくる。

問題があるとしたら、電力なり記憶領域なりを利用して採掘されたわけではないコインに価値を感じるか？というところだろうか。100万円分の電力を消費して採掘されたコインなら100万円分の価値があるように思えるが、コインから生まれたコインに価値を感じるか？という。本当は順序が逆で、100万円分の価値があるから100万円分の電力が注ぎ込まれるのだろうけど。

あとは、仮想通貨全体に占める採用例はそれほど多くはないので、何か致命的な問題が残っているというリスクもあるかもしれない。

QtumのPoSのパラメタはシンプルで、1ブロックあたり4 QTUM（半減期で減っていく）。所持しているQTUMの量に応じた確率で採掘できる。ただし、取引が採掘に使えるのは取引が入っているブロックから500ブロック経過した後。採掘間隔は平均2分に調節されるので、16時間。この16時間があることによって、チェーンが分岐したときに双方がチェーンを伸ばしたがるということを防いでいるのかもしれない。

公式のチュートリアルでの推奨やクライアントの仕組みとして大きな取引を100 QTUMくらいの取引に分けるようになっているのは、この16時間があるから。採掘したら新規取引扱いになるので500ブロックは採掘できなくなる。金額が大きいと16時間がバカにならない。

今、状況を見てみたところ、採掘に参加しているコインの総量は2,000万QTUMくらいで、期待年利は4.6%　参加するコインの総量が増えれば年利は下がるし、減れば上がる。Whitepaperによると、発行数は1億QTUMで、最初に5,1000万QTUMが販売されたらしいから、こんなものか。

f:id:kusano_k:20210421012621p:plain

Offline staking

Super stakingとも呼ばれている。

PoSのもう一つの問題として、採掘するためにはクライアントを動かし続けないといけないことがある。まあ、誰かしらクライアントと動かしていないとネットワークが破綻するのでこれは良いのだけど。ただ、ネットワークに繋ぐということはホットウォレットということであり、そこに例えば1億円分の仮想通貨を入れておくのは怖い。逆に、1,000円分の仮想通貨のためにクライアントを動かし続けるのも面倒。金額が安ければ採掘しなかったことによる損も小さいのだが、損した気分にはなる。

そこで、Qtumでは誰かに採掘をdelegate（委任）することができる。これは面白い。あくまで自分の採掘をdelegateしているだけであって、マイニングプールとは異なる。AさんとBさんがCさんに採掘をdelegateして、CさんがAさんの取引を使って採掘に成功したとき、採掘報酬は（QTUMの所有者である）Aさんと（実際に採掘してくれた報酬として）Cさんで分け合うことになる。Bさんはもらえない。

最初は、「え？　そんなことできるの？」と思ったけど、話は簡単。DelegateするAさんは事前に「報酬はx%でCさんにdelegateします」という情報を署名付きで流しておく、Cさんは「今この瞬間、Aさんの取引は採掘できる条件を満たしてますよね？」とブロックを作る。他の参加者は、Cさんが本当にAさんからdelegateされているかや、Cさんがx%以外の報酬を取っていたりしないかを見張る。詳しくは、

github.com

これを全てコントラクトで実装していたら、「なるほど、BitcoinとEthereumを合わせるとそんなこともできるのか」となってとても綺麗な話だったのだけど、そんなことはなかった。Delegateするところはコントラクトだが、採掘するところはBitcoinのプロトコルがガッツリ書き換えられている。それならそれで、delegateするところも無理にコントラクトを使わなくて良いと思うんだよな……。

Delegateするコントラクトはこれ。6,064バイト。

github.com

これだけでかければ、delegateするのに1 QTUM分くらいのガス（コントラクトを実行する手数料）が掛かるか……と思ったけど、そうではなかった。

コントラクトのソースコードはこれ。わざわざ、ガスを2,000,000消費するようになっている。

https://github.com/qtumproject/offline-staking-contract/blob/bd7b160f574f3a34c4f12ca009477d90ddc01c54/offline-staking.sol#L66-L72

      // we need to make this function call expensive to avoid spam, so here we consume ~2M gas that will go to miners
        if(gasleft()<0x1E9480) revert("Not enough gas left to consume, the recommended gas limit to call this function is 2,250,000");
        uint gas=gasleft();
        while(true) {
            dummy=0x0;
            if(gas-gasleft()>=0x1E8480)break;
        }

で、それに気が付かずに、数回無駄にdelegateしたり解除したりしてお金を溶かしました。確認画面にはちゃんとガスの使用量上限とガスの料金は書かれていたから、計算すれば良かったのだけど。送金が0.001 QTUMくらいでできるのに、採掘のdelegateにそんなにコストが掛かるとは思わなかった……。

f:id:kusano_k:20210421015753p:plain

罠があって、初期設定だと、あるアドレスAをdelegateする → そのコントラクトを実行するのにアドレスAからQTUMが支払われる → 残金が別のアドレスBに送信される → アドレスAの残金が0になる　ということが起こる。「Use change address」のチェックを外しましょう。そもそもなぜこんな設定があるかというと、店Aに支払ったときと店Bに支払ったときの送金元アドレスが同じだと、同じ人が支払ったと紐付けられてしまうというプライバシー的な問題があるから。それができてしまうようになるというリスクはある。

f:id:kusano_k:20210421021505p:plain

あるいは、「コインコントロール機能を有効化する」にチェックを入れると、送金時に下のようなダイアログを表示できて、自分に送金された取引の一覧から使用する取引を選んだり、残金の送金先を手動で設定したりできる。ちゃんと100 QTUMごとに分かれているかを確認するのにも使える。

f:id:kusano_k:20210421021948p:plain

Delegateしたアドレスの残高が0になってしまっても慌てる必要は無い。自分の持っている他のアドレスからdelegateしたアドレスに送金すれば良いだけ。送金手数料はdelegateする手数料よりとても安い。

Offline stakingに対する攻撃

stake-a-thon.qtum.org

Offline stakingを受け付けていて（掲載を申請した）アドレスの一覧が公開されている。これに載っている人に悪意があったり、あるいは載せることで悪意のある人に目を付けられたときに何が起こるか。公式ブログにも色々と書かれている。

blog.qtum.org

Offline stakingを受け付ける側に悪意がある場合。

DelegateされたQTUMを勝手使ってしまう
- これはできない
- これができないから、大金（大QTUM）をコールドウォレットに入れて、自分の管理する別のクライアントにdelegateするということができる
  - ハッキングでネットワークに繋いでいるクライアントに何をされても、損するのはそのクライアントに入れているお金だけ
「Delegationを受け付けるよ」と言いながら、採掘しない
- これはできる
- 採掘できればdelegation報酬分を得するからそんなことはしないだろうと期待するしかない
- エクスプローラーで採掘できたかどうかは見られるので、期待値より少なければ怪しい
- 頑張ってスクリプトを書けば、「このブロックが採掘されたタイミングで先に私の取引で採掘できたはずでは？」と怪しむことはできるかもしれない
  - でも、PoSを採掘してみると分かるけど、手元で採掘に成功しても他の誰かに先を越されることは普通にある
- 「あ、こいつ採掘していないな」と分かって他の人に乗り換えるのにも、1 QTUM掛かってしまう
- 悪意というか、飽きて止めるというのが多そう
- このリスクが大きいので、自分で採掘することにした
掲載されているdelegation報酬が嘘
- クライアントに設定した報酬より安いと採掘されない、高い場合はその報酬がそのまま支払われる
- これもできる
- そもそも、delegationを受け付ける側は特にコントラクトを実行したりはしないようで、外部からクライアントで最小報酬を何%にしているのか確認するすべが無い
- 嘘を付いてもメリットは無いだろうと思うしかない

Offline stakingをdelegateする側に悪意がある場合。

勝手にdelegateする
- 上記の一覧に載っていなくても、エクスプローラーからOffline stakingをしているアドレスを探すことはできる
- まあ、delegateされて損することは無いだろう
- 自分用に最小報酬を0%にしている場合は、ちょっとイラっとする
  - ので、上記のFAQだとそういうときはwhitelistで運用しろと言っている
最小報酬未満でdelegateする
- そういう取引はクライアントが採掘しないはず
大量にdelegationを送りつける
- 負荷が高まりそう
  - 「この取引で採掘できるかな？」というのを毎秒試しているので
- これを防ぐため、delegationのコントラクトはガスを大量に消費するし、Minimum UTXO Valueが設定できるようになっているのだろうか

Super stakingします

ということで自分で採掘することにしたので、ついでにdelegationも受け付けるようにした。

gist.github.com

私は未だにNEETCOIN（今でも参加しているのが700万NEET程度しかいないので、1,000 NEETくらいの手持ちで毎日何回も採掘できている）や、XPCoinも採掘しているから、しばらくは続けると思います。止めるときは、なるべく↑のGistに書くようにします。保証はしませんが。

デフォルトでは100 QTUM未満は受け付けないようになっているのだけど、ここを10 QTUMにしているので少額でもどうぞ。

~~ただ、ソースコードのこの部分がちょっと気になる。~~

            // Check the super staker min utxo value
            if(coinTxPrev.out.nValue < DEFAULT_STAKING_MIN_UTXO_VALUE)
                return state.Invalid(BlockValidationResult::BLOCK_INVALID_HEADER, "stake-delegation-not-min-utxo", strprintf("CheckProofOfStake() : Stake for block at height %i do not have the minimum amount required for super staker", nHeight));

https://github.com/qtumproject/qtum/blob/cb6fefeab03bb88544660c37b39ddf7c94e7a278/src/pos.cpp#L240

DEFAULT_STAKING_MIN_UTXO_VALUE は100 QTUM。コメントやソースコードを追うに、これはdelegationを受け付ける私が100 QTUMを持っていれば良いと思うのだけど……。

開発者直々のコメントが付いていた。Delegateする側はいくら少なくても良いらしい。

JB395 commented 18 hours ago Qtum offline staking accepts delegated addresses with any quantity of QTUM.

あと、度々書いているようにdelegateするには約1 QTUM必要なので、小額でdelegateして得かどうかは良く考えてほしい。現在の年利は4.6%　2021年末に半減期で報酬が2 QTUMになる予定。

2021-03-30

DISCO presentsディスカバリーチャンネルコードコンテスト2021参加記

www.discoverychannel.jp

略称DDCC2021。これに参加して、こんな感じでパチンコをしてきた。

このコンテストは毎年こんな感じで実機を動かす問題。画面の中ではなく物を動かすのは楽しそうだよなぁと思っていたので、参加できて満足。まあ、順位はショボかったけど。

予選

例年はAtCoder上で開かれていたのに、今年は自社のサイト。別にAtCoderが嫌いなわけではないけど、日本のプログラミングコンテストがAtCoderに独占されてしまうのはそれはそれで不安なので、良い流れ。

そのせいか問題は（ABCを全完できるくらいの人にとっては）簡単。私は開始45分くらいで全部解いた。

procon.disco.co.jp

「いくら問題が簡単とはいえ、強い人と弱い人の差は出るだろ？　なぜお前が本戦に進めているの？」という話がある。いつもは本戦に200人くらい集めていて、この本戦に行ったことはある。ただし、実機を動かせるのは、本戦の中でのコードコンテストで上位の人だけ。私は指をくわえて見ていた。今年は感染症対策のために人数を絞り、コードコンテスト無しで全員が実機を動かせる。就活年度の学生が20人、その他の人が10人。私の実力ではまず無理な人数。

ひとつはAtCoderでの開催ではないので、気が付いていない人がそれなりにいたこと。また、事前に申込みが締め切られるので、コンテスト開始直前に気が付いても遅い。 Twitterで「気が付かなかった」と嘆いている人がそれなりにいた。

もうひとつ、

Q: stdc++やboostなどのライブラリは使用可能ですか？

A: C/C++の標準ライブラリではないため、使用できません。

https://procon.disco.co.jp/backnumber/ddcc2021_qual/faq.html

というルールに引っ掛かった人が多かったのではないかという噂がある。 stdc++とは、gccに存在するbits/stdc++.hというヘッダファイルで、これを#includeすると全ての標準ヘッダが#includeされる。普段から使っている人がそれなりにいるらしい。懇親会でもあれば中の人に真相を訊いてみたかったけど、無かったので闇の中。

問題の解答とソースコードを合わせて提出する昔のGoogle Code Jamのような形式で、コンテスト中の正否は解答だけで判定されるので、コンテスト中には気が付けない。昔のGoogle Code Jamは、たしか「なんなら手で解いても良いよ」で提出されたソースコードはチェックされていなかったと思うけど、DDCCは後からソースコードを動かしてたしかにその出力が出てくるのか確認しているのかもしれない。まあ、リアルタイムにそれをやろうとすると大変だろうな。

本戦（問題以外）

当日に緊急事態が宣言されていたら、オンラインで後日にという話だった。緊急事態宣言は終了したから無事開催。

正直、「よくやるなぁ。まあやるなら行くけど」と思っていた。感染症対策はしっかりしていた。まず、受付で付けてきたマスクを主催者が用意したものに交換。「マスク着用必須です」は今なら良く見るけど、これだけでは参加者がどんなマスクを付けているのか分からないのか。アルコール消毒。エレベーターはスタッフ1人と参加者3人以下を厳守。 200人集めていたときと同じ広い会場に、参加者別にビニールテントが組み立てられていた。机の上には、アルコールスプレーとフェイスシールドとゴミ袋（会場のゴミ箱は使うなということか）。会場の自販機は使用禁止。

うおおおおおお個室個室個室個室個室！！！！！！！！！ pic.twitter.com/Nvs7zttrMN
— こるとん (@kyort0n) 2021年3月28日

最後に実機で確認するときは参加者が周りに集まって観戦する。ここでも実機の周りにビニールテントを置いていた。あ、会場の隅にあったビニールテントは単なる予備ではなかったのか。 3グループに分かれての入れ替え制で、入れ替え時には消毒。

解散前には「オフ会しないでまっすぐ帰れ」と釘を刺していた。

本戦（問題）

f:id:kusano_k:20210328153729j:plain

問題は、冒頭の動画の通り。射出機の角度に加えて、台の角度を動かせる。カイジのような20トンの水は必要無い。玉を打ち出しながら台の角度を変えることはできない。プログラムは、（台の支柱3本それぞれの高さ、射出機の角度、玉を何発打つか、玉を打った後の待機時間）の列を出力する。装置はこれを読んで、台と射出機の角度を変えてから、玉を打ち出す。玉は全100個。 1個の穴あたり有効なのは10個までで、穴に入った有効な玉数×1個でも玉が入った穴の個数が得点。最初に全動作をまとめて出力するので、穴に入った個数を見てから動きを変えるようなことはできない。

まずはシミュレーターで競う。どのような動作をしたのかは分からず、点数だけが返ってくる。これで正の点数を取った人だけが実機で動かせるとのこと。

穴の方向に射出機を向けるだけでしょ？ → フォーマットエラー。なぜかと思ったら、射出機の可動範囲を超えていた。直接は狙えない穴もあるのか。まあ、正の点数を取れば良く満点を取る必要は無いから、範囲を超えたやつはクリップしておくか → 正の点数ゲット。ちなみに、この前半の点数はどうでも良いと思っていたが、最後の実機で同点だったらシミュレーターの点数で順位を付けるというルールがあり、これで最終的に順位がちょっと落ちた。

角度的に直接狙えない穴がある。また、穴の位置をExcelでプロットすると、他の穴の後ろにある穴もある。

f:id:kusano_k:20210330012810p:plain

ここで台を傾けるのか。なるほど。手元でも玉の動きを物理的にシミュレートして、台と射出機の角度をランダムに決めて、狙った穴に入るかどうかを判定すれば良いだろう。という実装をしている間に時間切れ。ちなみに、シミュレートは0.001秒ごとに玉の位置と速度を更新するようにしたけど、台を左右にしか傾けないならば数値計算でわりと簡単に出せるっぽい。他の参加者が言っていた。たしかに。

シミュレーションの順位発表。真ん中ちょい下くらい。この時点で台を傾けるところまで実装している人も多いのか。さすが。

会社紹介を聞いて、実機コンテストの問題発表。だいたいそのままだけど、制限時間が短くなるらしい。台や射出機の角度を10回変えると考えると、時間が足りない。 10個全部の穴を狙うのか、穴の数を絞って球数を増やすのかの駆け引きだろうか。コーディング時間が短くて焦っていたからあまり自信は無いけど、狙う穴の数を絞る選択肢は無いよなぁ。角度をランダムに決めて入るかどうかをシミュレートするやつ実装完了。実機コンテストも提出の度に（運営の）シミュレーターのスコアが返ってくる。想定しているスコアよりも低いのはなぜだ……。

実機での中間確認。ああ、玉を打ち終わった後で次の角度の変更が行われるとはいえ、打った玉はまだ移動中で、そこで台を動かすと移動中の玉の狙いがズレてしまうのか。玉を打った後の待機時間はそのためね。でも、時間はギリギリだから、ただ待つくらいならとりあえず打っておいたほうが良いよなぁ。運良くどこかの穴に入るかもしれないし。

コーディング2回目。台を傾けなくても狙える穴のときに台を傾けるのは悪手なので、傾けないようにする。角度ガチャだけだと一瞬で実行が終わる。後は何をしよう。実機には当然誤差があるはずである。ギリギリだと入るかどうか怪しいよね。ということで、狙った穴のサイズを小さいと思い、狙っていない穴のサイズは大きいと思って、なるべく中心を狙うようにしてみる。本当は出た結果を微調整すると速いのだろうけど、それはやっていない。

最終結果。冒頭の動画のように、台を傾けないで狙える穴にはだいたい入ったけど、傾けて狙うものはほとんど入らずに終了。悲しい。

他の参加者の話を聞くに、台の傾きをなるべく小さくするというのがポイントだったらしい。 1回目の確認のときに、「やっぱり傾けるとどうしてもズレるな。傾きを変えると移動中の玉が外れる以外にもこのデメリットがあるので、傾けなくてすむ穴は傾けないべきだな」とは考えていたけれど、0-1ではなくて、傾きが大きければ大きいほど誤差が大きくなるとまで考えるべきだった。

手前で曲がってしまっている。解説の人が「転がり抵抗」がどうこうと言っていた。台の素材は堅いゴムみたいな感じだったから、抵抗が大きくて速度が落ちるんだろうなぁ。

uwiさんが、傾きを固定するということをしていて頭が良いなと思った。たしかに、ちょっと軌跡を曲げられれば何でも良いので、1種類の傾きで複数の穴が狙える。射出機の角度を変えるだけでも一緒に台の角度を変えても使う時間は一緒だけれど、台を傾けなければ事前に打っている玉の軌跡が変わらないというメリットがある。

台の角度は3本の支柱の高さで変えるので、好きな向きにできる。「左右は使うけど、前後方向の傾きを変える意味は無いよね」と思っていた。奥の方を下げることで、玉を加速させて早く穴に入れ、次の角度変更の影響を小さくしている人がいた。なるほど。

実機ならではだと思ったのが、隅に当てて穴に入れている人がいた。この台の周囲には隙間があって台から外れた玉は落ちていくのだけど、台の隅だけは支えるため隙間が無い。ここを狙って枠に反射させ、そのままでは狙えない穴を狙っていた。

「これ時間的に満点は無理ですよね？」「いや、射出機と台の角度を10回変えると無理なのであって、ギリギリを狙って2個の穴に入れられれば可能性はある」という話もあった。

「考えることが少なくてつまらなくない？　時間も限られているからしょうがないか」とか思っていたけど、本当は考えることはいくらでもあったわ。私の考えが足りないだけだった。リアルに物を動かしているのだから、そりゃそうか。面白い。

2021-03-28

SoftEther VPNのL2TPにWindows 10の標準機能のL2TPで繋ぐときのエラー

ja.softether.org

SoftEther VPNクライアントを使えば良いのだけど、OSの標準機能だけですむならそのほうが良いよね。

f:id:kusano_k:20210328000101p:plain

リモートサーバーが応答しないため、使用するコンピューターとVPNサーバー間のネットワーク接続を確立できませんでした。これは使用するコンピューターとリモートサーバー間のネットワークデバイス（ファイアウォール、NAT、ルーターなど）の1つがVPN接続を許可するように構成されていないことが原因だと考えられます。管理者またはサービスプロバイダーに問い合わせて、どのデバイスが問題を引き起こしているのかを判定してください。

IPv6アドレスもIPv4アドレスも引けるドメインを指定していたのだが、これをIPv4アドレスでの指定にしたら繋がった。例示されている原因はどれも関係無かった。

他にハマりそうなところ。1個1個オフにして確認したわけではないので、関係無かったり、デフォルトの設定で問題無かったりするものもあるかも。

L2TPはSoftEtherの本体とは別に有効無効が切り替えられるので、有効にする
L2TPはSoftEtherの管理画面のポート一覧には出ていない、UDP 500とUDP 4500を使うので、開ける
接続先のネットワーク上にDHCPサーバーが無いなら、「仮想NATおよび仮想DHCP機能（SecureNAT）」を有効にする
レジストリのHKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\PolicyAgentにAssumeUDPEncapsulationContextOnSendRuleという名前の32ビットDWORD値を作って値を2にする
- Configure L2TP/IPsec server behind NAT-T device - Windows Server | Microsoft Docs
- 接続先がNATのときの話で、関係無いか？
接続元のルーターの設定で「IPsecパススルー」を有効にする
コントロールパネルのネットワーク接続でVPNに対応する接続のプロパティ→セキュリティで認証を「次のプロトコルを許可する」にする

f:id:kusano_k:20210328001332p:plain

2021-02-07

Quora Programming Challenge 2021

www.quora.com

Division 1に参加して、247/700点。 100位台。

今年初めて開催で来年もあるかもしれないので、色々と書いておく。端的に言うと、実装が重くてつらい。

Quora Programming Challenge

Quoraは最近良く目にするようになったQ&Aサイト。 Stack Overflowに比べて回答が少ないがその分回答に気合いが入っているように思う。

トップページにリンクを貼ろうと思ったが……トップページはログインフォームが出てくるだけなのか。こんな感じのサイト。

jp.quora.com

CEOが競プロガチ勢らしい。

CEOが競プロガチ勢なのに、なぜか競プロコンテストを開いてなかったQuoraが、ついにコンテストを開くとは…https://t.co/n7A6vAPnZJ
— nico_shindannin（診断人） (@nico_shindannin) January 14, 2021

Google Code Jamのように複数ラウンドに分かれていたりはしない一発勝負。ただし、タイムゾーンを考慮して、Division 1とDivision 2に分かれている。どちらかに一方に出ても良いし、両方に出ても良い。どちらも10以内なら賞金、50以内ならTシャツ。

タイムゾーンに配慮していると言っているけど、これ日本がとても不利じゃない？ Division 1は日本時間の23時から翌日3時、Division 2が同日の10時から14時。両方出ればその分有利。普通に1回だけの開催ならば睡眠時間を適当にズラすが、3時から10時の間にピタリと睡眠時間を持ってくるはつらい。ということでDivision 2はスルーした。

問題はDivisionごとに全7問で全て100点。簡単でも難しくても点数が同じなので、順位表の解いている人の人数から簡単な問題を見極める必要がある。でも、コンテストサイトに順位表が無い。 1時間ごとくらいにトップ50位までの順位表が貼り出される。

誤答ペナルティは無し。提出数と間隔にちょっと制限はあるが気にするほどではない。

制約の小さなテストケースを通すことによる部分点が多い。今となってはこの方式も珍しい。

私のコンテスト中の様子と回答

1問目: digest

Quoraの記事推薦システムが題材。企業コンテストでこういう問題良いね。

ユーザーがユーザーをフォローすることもできるし、ユーザーが記事をフォローすることもできる。記事には記事を作成したユーザーが存在する。これらの関係から、記事 $S_k$ のユーザー $U_i$ に対するスコアは、

$\sum_{j=1}^m a\left(U_i, U_j\right)\times b\left(U_j, S_k\right)$

と計算される。関数 $a$ と $b$ の値はユーザー同士やユーザーの記事とのフォローしているかどうかとかの関係から決まる。これで各ユーザーについてスコア上位3件の記事を推薦しろという問題。

ユーザー数と記事数がどちらも最大200。制限時間が0.5秒。 $O\left(n^{3}\right)$ 通るかな？　通るよね。 $a$ と $b$ の値を事前に計算しておく。

実装が面倒でバグって時間が溶ける。計算が複雑だからサンプルケースと見比べるの大変。何とか修正して通った。

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

int main()
{
    int n, m;
    cin>>n>>m;
    vector<int> creator(n);
    for (int &c: creator)
        cin>>c, c--;
    int p, q;
    cin>>p>>q;
    vector<vector<bool>> FU(m, vector<bool>(m));
    for (int x=0; x<p; x++)
    {
        int i, j;
        cin>>i>>j;
        FU[i-1][j-1] = true;
    }
    vector<vector<bool>> FS(m, vector<bool>(n));
    for (int x=0; x<q; x++)
    {
        int i, k;
        cin>>i>>k;
        FS[i-1][k-1] = true;
    }

    vector<vector<int>> a(m, vector<int>(m, -1));
    for (int i=0; i<m; i++)
        a[i][i] = 0;
    for (int i=0; i<m; i++)
        for (int j=0; j<m; j++)
            if (FU[i][j] && a[i][j]==-1)
                a[i][j] = 3;
    for (int i=0; i<m; i++)
        for (int j=0; j<n; j++)
            if (FS[i][j] && a[i][creator[j]]==-1)
                a[i][creator[j]] = 2;
    for (int i=0; i<m; i++)
        for (int j=0; j<m; j++)
            for (int k=0; k<n; k++)
                if (FS[i][k] && FS[j][k] && a[i][j]==-1)
                    a[i][j] = 1;
    for (int i=0; i<m; i++)
        for (int j=0; j<m; j++)
            if (a[i][j]==-1)
                a[i][j] = 0;

    vector<vector<int>> b(m, vector<int>(n));
    for (int i=0; i<m; i++)
        for (int j=0; j<n; j++)
            if (creator[j]==i)
                b[i][j] = 2;
            else if (FS[i][j])
                b[i][j] = 1;

    for (int i=0; i<m; i++)
    {
        vector<pair<int, int>> S;
        for (int j=0; j<n; j++)
        {
            int s = 0;
            if (creator[j]==i || FS[i][j])
                s = -1;
            else
                for (int k=0; k<m; k++)
                    s += a[i][k]*b[k][j];
            S.push_back(make_pair(-s, j));
        }
        sort(S.begin(), S.end());
        for (int j=0; j<3; j++)
            cout<<(j==0 ? "" : " ")<<S[j].second+1;
        cout<<endl;
    }
}

2問目: escape

グリッド上の迷路に閉じ込められてしまったので、SからEまで移動して脱出したい。何体かのガードがいて、各ガード $i$ は（マンハッタン距離で） $d_{i}$ の範囲の好きな場所に移動できる。捕まらないように脱出する最小ステップは？

ガードの移動可能な範囲を壁にしてしまえば良い。各ガードについて求めていると間に合わないので、同時に求める。移動範囲の広いガードは先に、狭いガードは後に時間差で置いていき、1マスずつ広げていくイメージ。

これは素直に通った。

#include <iostream>
#include <vector>
#include <string>
#include <utility>
using namespace std;

int main()
{
    int n, m, k;
    cin>>n>>m>>k;
    vector<string> M(n);
    for (string &s: M)
        cin>>s;
    vector<vector<pair<int, int>>> G(n*m+1);
    for (int i=0; i<k; i++)
    {
        int r, c, d;
        cin>>r>>c>>d;
        G[d].push_back(make_pair(r-1, c-1));
    }

    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};

    vector<pair<int, int>> T;
    for (int s=0; s<=n*m; s++)
    {
        vector<pair<int, int>> P;
        P.swap(T);

        for (auto p: P)
            for (int d=0; d<4; d++)
            {
                int tx = p.second + dx[d];
                int ty = p.first + dy[d];
                if (M[ty][tx]!='#')
                {
                    M[ty][tx] = '#';
                    T.push_back(make_pair(ty, tx));
                }
            }

        for (auto p: G[n*m-s])
            if (M[p.first][p.second]!='#')
            {
                M[p.first][p.second] = '#';
                T.push_back(p);
            }
    }

    int sx = -1;
    int sy = -1;
    int ex = -1;
    int ey = -1;
    for (int y=0; y<n; y++)
        for (int x=0; x<m; x++)
        {
            if (M[y][x]=='S')
                sx = x,
                sy = y;
            if (M[y][x]=='E')
                ex = x,
                ey = y;
        }
    if (sx==-1 || ex==-1)
    {
        cout<<"IMPOSSIBLE"<<endl;
        return 0;
    }

    vector<vector<int>> D(n, vector<int>(m, -1));
    D[sy][sx] = 0;
    T.clear();
    T.push_back(make_pair(sy, sx));

    for (int s=1; s<=n*m; s++)
    {
        vector<pair<int, int>> P;
        P.swap(T);

        for (auto p: P)
            for (int d=0; d<4; d++)
            {
                int tx = p.second + dx[d];
                int ty = p.first + dy[d];
                if (M[ty][tx]!='#' && D[ty][tx]==-1)
                {
                    D[ty][tx] = s;
                    T.push_back(make_pair(ty, tx));
                }
            }
    }

    if (D[ey][ex]==-1)
    {
        cout<<"IMPOSSIBLE"<<endl;
        return 0;
    }

    cout<<D[ey][ex]<<endl;
}

3問目: students

$n\times n$ （ $2\leq n \leq 3\times 10^{3}$ ）のグリッドに生徒が敷き詰められている。 4近傍隣接のうち $m$ （ $0\leq m \leq min\left(2n(n-1), 2\times 10^{5}\right)$ ）組はおしゃべりをしている。おしゃべりしている生徒同士を含まないように生徒は最大何人選べる？

二部グラフの最大独立集合。

どうやって求めるんだっけ？　直感的には最大マッチングを求めて何とかするのだろうが……。ググる。

二部グラフの最小点被覆と最大安定集合と最小辺被覆の求め方 from Kensuke Otsuki

www.slideshare.net

こんなん考えても分かるわけがないな。ググって良かった。けんちょんさんありがとう。

持っているライブラリーはマッチング数しか返さなかったので、ポチポチ修正。ライブラリゲー止めてくれ。まあ、修正が必要になると、ACLではなく自分でライブラリを書いていたのが生きてくる。自分で書いたコードのほうが修正がしやすい。

提出すると47/100。 Memory Limit Exceededで落ちていた。制限は256 MiBらしい。

たしかにけっこうギリギリか……。型をsigned charに変えてもダメ。 $m$ の上限がちょっと小さいので、おしゃべりしていない生徒を除外して、おしゃべりしている生徒だけでグラフを作ってみる。こういう非本質的なところで手間を掛けさせるのは止めてくれ～

今度はTime Limit Exceeded。最大流のアルゴリズムをDinicに貼り替えてみたら、バグった。諦め。

今気が付いたけど、これ、cinを止めれば通ったか……？

#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

/*
void maxflow(vector<vector<int>> E_, vector<vector<int>> &F_, int s, int t)
{
    int n = (int)E_.size();

    vector<vector<int>> E(n), R(n), Forg(n);
    vector<vector<int>> F(n);
    for (int i=0; i<n; i++)
    for (int j=0; j<(int)E_[i].size(); j++)
    {
        int v = E_[i][j];
        R[i].push_back(int(E[v].size()));
        R[v].push_back(int(E[i].size()));
        E[i].push_back(v);
        E[v].push_back(i);
        F[i].push_back(F_[i][j]);
        Forg[i].push_back(j);
        F[v].push_back(0);
        Forg[v].push_back(-1);
    }
    vector<bool> U(n);
    function<int (int, int)> dfs = [&](int p, int f)
    {
        if (p==t)
            return f;
        U[p] = true;
        for (int i=0; i<(int)E[p].size(); i++)
        if (!U[E[p][i]] && F[p][i]>0)
        {
            int t = dfs(E[p][i], min(f, (int)F[p][i]));
            if (t>0)
            {
                F[p][i] -= t;
                F[E[p][i]][R[p][i]] += t;
                return t;
            }
        }
        return 0;
    };
    
    int flow = 0;
    while (true)
    {
        for (int i=0; i<n; i++)
            U[i] = false;
        int f = dfs(s, 0x7fffffff);
        if (f==0)
            break;
        flow += f;
    }

    //return flow;
    for (int i=0; i<n; i++)
        for (int j=0; j<(int)Forg[i].size(); j++)
            if (Forg[i][j]!=-1)
                F_[i][Forg[i][j]] = F[i][j];
}
*/

template<class T>
T maxflow(vector<vector<int>> E_, vector<vector<T>> C_, int s, int t)
{
    int n = (int)E_.size();
    vector<vector<int>> E(n), R(n), Corg(n);
    vector<vector<T>> C(n);
    T mx = {};
    for (int i=0; i<n; i++)
    for (int j=0; j<(int)E_[i].size(); j++)
    {
        int v = E_[i][j];
        R[i].push_back((int)E[v].size());
        R[v].push_back((int)E[i].size());
        E[i].push_back(v);
        E[v].push_back(i);
        C[i].push_back(C_[i][j]);
        Corg[i].push_back(j);
        C[v].push_back(T());
        Corg[v].push_back(-1);
        mx = max(mx, C_[i][j]);
    }

    vector<int> D;
    vector<int> I;

    auto bfs = [&]()
    {
        D = vector<int>(n, -1);
        vector<int> Q;
        D[s] = 0;
        Q.push_back(s);
        int q = 0;
        while (q<(int)Q.size())
        {
            int v = Q[q++];
            for (int i=0; i<(int)E[v].size(); i++)
            if (C[v][i]>0 && D[E[v][i]]==-1)
            {
                D[E[v][i]] = D[v]+1;
                Q.push_back(E[v][i]);
            }
        }
    };

    function<T(int,T)> dfs = [&](int v, T f)
    {
        if (v==t)
            return f;
        for (int &i=I[v]; i<(int)E[v].size(); i++)
        if (C[v][i]>0 && D[v]<D[E[v][i]])
        {
            T d = dfs(E[v][i], min(f, C[v][i]));
            if (d>0)
            {
                C[v][i] -= d;
                C[E[v][i]][R[v][i]] += d;
                return d;
            }
        }
        return T();
    };

    T flow = {};
    while (true)
    {
        bfs();
        if (D[t]==-1)
            break;
        I = vector<int>(n, 0);
        while (true)
        {
            T f = dfs(s, mx);
            if (f == T())
                break;
            flow += f;
        }
    }
    //return flow;
    for (int i=0; i<n; i++)
        for (int j=0; j<(int)Corg[i].size(); j++)
            if (Corg[i][j]!=-1)
                C_[i][Corg[i][j]] = C[i][j];
    return 0;
}

#include <iostream>
#include <queue>

int main()
{
    int n, m;
    cin>>n>>m;
    vector<int> x1(m), y1(m), x2(m), y2(m);
    for (int i=0; i<m; i++)
    {
        cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
        x1[i]--, y1[i]--, x2[i]--, y2[i]--;
    }

    //  https://www.slideshare.net/drken1215/ss-86894312
    vector<vector<int>> M(n, vector<int>(n, -1));
    for (int i=0; i<m; i++)
    {
        M[y1[i]][x1[i]] = 0;
        M[y2[i]][x2[i]] = 0;
    }
    int C = 0;
    for (int y=0; y<n; y++)
        for (int x=0; x<n; x++)
            if (M[y][x]>=0)
                M[y][x] = C++;
    vector<bool> O(C);
    for (int y=0; y<n; y++)
        for (int x=0; x<n; x++)
            if (M[y][x]>=0)
                O[M[y][x]] = (y+x)%2!=0;

    vector<int> e1(m), e2(m);   //  even, odd
    for (int i=0; i<m; i++)
    {
        e1[i] = M[y1[i]][x1[i]];
        e2[i] = M[y2[i]][x2[i]];
        if (O[e1[i]])
            swap(e1[i], e2[i]);
    }

    vector<vector<int>> E(C+2);
    vector<vector<int>> F(C+2);
    for (int i=0; i<m; i++)
    {
        E[e1[i]].push_back(e2[i]);
        F[e1[i]].push_back(1);
    }
    for (int i=0; i<C; i++)
        if (!O[i])
        {
            E[C].push_back(i);
            F[C].push_back(1);
        }
        else
        {
            E[i].push_back(C+1);
            F[i].push_back(1);
        }

    maxflow(E, F, C, C+1);
    for (int i=0; i<C+2; i++)
        E[i].clear();
    vector<int> EC(C);
    vector<bool> FF(C);
    for (int i=0; i<C; i++)
        if (!O[i])
            FF[i] = true;
    for (int i=0; i<m; i++)
    {
        if (F[e1[i]][EC[e1[i]]]!=0)
        {
            E[e2[i]].push_back(e1[i]);
            FF[e1[i]] = false;
        }
        else
            E[e1[i]].push_back(e2[i]);
        EC[e1[i]]++;
    }

    queue<int> Q;
    for (int i=0; i<C; i++)
        if (FF[i])
            Q.push(i);
    while (!Q.empty())
    {
        int q = Q.front();
        Q.pop();
        for (int e: E[q])
            if (!FF[e])
            {
                FF[e] = true;
                Q.push(e);
            }
    }

    int ans = 0;
    for (int i=0; i<C; i++)
        if (!O[i] && FF[i] ||
            O[i] && !FF[i])
            ans++;
    for (int y=0; y<n; y++)
        for (int x=0; x<n; x++)
            if (M[y][x]<0)
                ans++;
    cout<<ans<<endl;
}


/*
int main()
{
    int n, m;
    cin>>n>>m;
    vector<int> x1(m), y1(m), x2(m), y2(m);
    for (int i=0; i<m; i++)
    {
        cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
        x1[i]--, y1[i]--, x2[i]--, y2[i]--;
    }

    //  https://www.slideshare.net/drken1215/ss-86894312
    vector<vector<int>> E(n*n+2);
    vector<vector<signed char>> F(n*n+2);
    for (int i=0; i<m; i++)
    {
        int p1 = y1[i]*n+x1[i];
        int p2 = y2[i]*n+x2[i];
        if ((x1[i]+y1[i])%2!=0)
            swap(p1, p2);
        E[p1].push_back(p2);
        F[p1].push_back(1);
    }
    for (int y=0; y<n; y++)
        for (int x=0; x<n; x++)
            if ((x+y)%2==0)
            {
                E[n*n].push_back(y*n+x);
                F[n*n].push_back(1);
            }
            else
            {
                E[y*n+x].push_back(n*n+1);
                F[y*n+x].push_back(1);
            }

    maxflow(E, F, n*n, n*n+1);
    for (int i=0; i<n*n; i++)
        E[i].clear();
    vector<int> EC(n*n);
    vector<bool> FF(n*n);
    for (int y=0; y<n; y++)
        for (int x=0; x<n; x++)
            if ((x+y)%2==0)
                FF[y*n+x] = true;
    for (int i=0; i<m; i++)
    {
        int p1 = y1[i]*n+x1[i];
        int p2 = y2[i]*n+x2[i];
        if ((x1[i]+y1[i])%2!=0)
            swap(p1, p2);
        if (F[p1][EC[p1]]==0)
        {
            E[p2].push_back(p1);
            FF[p1] = false;
        }
        else
            E[p1].push_back(p2);
        EC[p1]++;
    }

    queue<int> Q;
    for (int y=0; y<n; y++)
        for (int x=0; x<n; x++)
            if (FF[y*n+x])
                Q.push(y*n+x);
    while (!Q.empty())
    {
        int q = Q.front();
        Q.pop();
        for (int e: E[q])
            if (!FF[e])
            {
                FF[e] = true;
                Q.push(e);
            }
    }

    int ans = 0;
    for (int y=0; y<n; y++)
        for (int x=0; x<n; x++)
            if ((x+y)%2==0 && FF[y*n+x] ||
                (x+y)%2!=0 && !FF[y*n+x])
                ans++;
    cout<<ans<<endl;
}
*/

3問目: walls

公開された順位表で解いている人数が少なかったのでスルー。

4問目: tourism

木が与えられる。頂点では金がもらえる。辺では金が取られる。移動元と移動先のクエリが複数与えられ、それぞれについて、金が尽きないように移動できる初期所持金の最小値を求める。

各頂点xについて、xから根に移動するときに必要な初期所持金と、根からxに移動するときに必要な初期所持金と、xから根に移動したときに所持金がいくらになっているかを求めておけば、各クエリが $O(n)$ で処理できる。

書いてみたけどサンプルケースが合わない → あ、経由するのは根ではなく最小共通祖先か。

だいたい差分計算ができそうだが、必要な金の最小値を取っているところがあり、これはSegment Tree的なことをしないといけない。この時点で残り10分。解けるわけがない。終わり。

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

int main()
{
    int n, m;
    cin>>n>>m;
    vector<long long> x(n);
    for (long long &t: x)
        cin>>t;
    vector<vector<int>> E(n);
    vector<vector<long long>> T(n);
    for (int i=0; i<n-1; i++)
    {
        int v, w;
        long long t;
        cin>>v>>w>>t;
        v--, w--;
        E[v].push_back(w);
        T[v].push_back(t);
        E[w].push_back(v);
        T[w].push_back(t);
    }

    vector<long long> MF(n);    //  MF[x]: needed money from x to 0
    function<void(int, int, long long)> f1 = [&](int c, int p, long long t)
    {
        if (p>=0)
            MF[c] = max(0LL, t-x[c]+MF[p]);
        for (int i=0; i<(int)E[c].size(); i++)
            if (E[c][i]!=p)
                f1(E[c][i], c, T[c][i]);
    };
    f1(0, -1, 0);

    vector<long long> MT(n);    //  MT[x]: needed money from 0 to x
    function<void(int, int, long long)> f2 = [&](int c, int p, long long m)
    {
        if (p>=0)
            MT[c] = max(0LL, max(MT[p], -m));
        for (int i=0; i<(int)E[c].size(); i++)
            if (E[c][i]!=p)
                f2(E[c][i], c, m+x[c]-T[c][i]);
    };
    f2(0, -1, 0);

    vector<long long> MS(n);
    function<void(int, int, long long)> f3 = [&](int c, int p, long long m)
    {
        if (p>=0)
        {
            m += x[c];
            MS[c] = m;
        }
        for (int i=0; i<(int)E[c].size(); i++)
            if (E[c][i]!=p)
                f3(E[c][i], c, m-T[c][i]);
    };
    f3(0, -1, 0);

    for (int i=0; i<n; i++)
        cout<<i<<" "<<MF[i]<<" "<<MT[i]<<" "<<MS[i]<<endl;

    for (int i=0; i<m; i++)
    {
        int a, b;
        cin>>a>>b;
        a--, b--;
        //cout<<MF[a]+max(0LL, MT[b]-MS[a])<<endl;
        cout<<MF[a]+max(0LL, MT[b]-MS[a])<<" "<<MF[a]<<" "<<MT[b]<<" "<<MS[a]<<endl;
    }
}

2020-11-19

日本ディープラーニング協会G検定でGoogle検索はありなのか？

2020年第3回試験で合格した✌

G検定とは、一般社団法人日本ディープラーニング協会（JDLA）が主催するディープラーニングに関する2個の試験のうちの簡単なほう。公式サイトに、

ディープラーニングの基礎知識を有し、適切な活用方針を決定して、事業活用する能力や知識を有しているかを検定する。

G検定とは - 一般社団法人日本ディープラーニング協会【公式】

と書かれているように、実際にディープラーニングの実装を行う人ではなく、企画担当者やマネージャー向けの試験でしょう。

難易度はわりと低く、ある程度の前提知識があれば、公式テキストに一通り目を通して、あとはググれば何とかなると思う。「2時間で約200問、1問あたり36秒。そんな時間は無い」という話もあるけど、10秒で分かる問題が3割、公式テキストの索引を引くか検索するかで30秒くらいですぐに答えが分かる問題が2割ずつ、あと2割は1-2分時間を掛けてしっかりググって、（何割で合格かは非公開だけど）残り1割は別に落としても良いだろ、くらいの時間感覚だった。

一方で、広く浅くの試験なので、検索と資料の参照を封じられると一気に難易度が上がる。ディープラーニングを使って仕事をしている人でも落ちるんじゃないかと思う。今では誰も使っていないような古いモデルも把握していますか？ネオコグニトロンって知っていますか？フォルマントという言葉は？個人情報取扱事業者に課せられる義務のうち努力義務は何？「Ethically Aligned Design」を提唱したのはどこの団体？みたいな感じ。頭を使う問題は無くてググればすぐに分かるけど、そんなに色々覚えてないよと。

ということで、試験合格のためには検索スキルが重要であり、「G検定はG(oogle)検索検定」などと揶揄されていたりもする。

ここまで読んで「え？　試験なのにネット検索ありなの？」と思いますよね。「検索したら楽勝だったわw」とツイートしたら大炎上すると思いますよね。私は思いました。

でも、受験者のブログやTwitterを見ていると、みんな当たり前のように検索の話をしている。いちいちネットで検索するよりも、頻出用語をまとめたテキストファイルを作っておくという手もあるらしい。それを売っている人もいた。

「へー、検索ありなんだ」と思って念のために、↑の公式サイトの試験概要を見ても、そんなことは一言も書かれていない。申し込んだ後のメールとかでの案内に書いてあるのかとも思ったけど、特に無し。逆に、受験開始前に同意させられる受験規約には、

なりすまし、カンニング、試験中に援助を受けたりするなど不正行為があったと判断される場合、もしくはそのような行為が疑われる場合は結果を取り消される可能性があります。

http://docs.jdla-exam.org/OperationManual_Examinees_JP.pdf#page=40

と書かれている。特に定義が無ければ、一般的に、「カンニング」というのは試験中のネット検索や資料の参照を含むはず。

5ch。

35名無し検定１級さん2020/07/16(木) 19:13:14.17ID:LWGsH0Yq

>>34

一方通行の正義を押し付けるんじゃなくて、ちゃんとルール読んだり、JDLA公式の動画とか見ような。

JDLA公式の質問会でグーグル検索については「してよい」と見解が出てるんだわ。

【ＪＤＬＡ】G検定 part2

この動画が見つからん。

これかなぁ。

www.youtube.com

19:56

できればですね。僕らオンラインでこれやりたかった。そうするとやっぱりどうしてもカンニングというかですね、手元に資料があったりとかする中で受けてくださいというものになりますので、そうすると、本当に分かっているかどうかというのを1問30秒ぐらいになりますけど、パッとパッと出てくるような状況にあるかを確認したいので、こういうった制限時間の中でたくさん答えていただくというような形でG検定を実施しています。

22:46

司会「検索することも意味があるということですよね？」

理事・事務局長「そこで得た知識も自分のものにしていただけたらという風に思っています」

司会「結局、最新の情報を入手する方法が身に付いているかということもあるということですよね。試験中に検索ができるということは」

理事・事務局長「その通りですね、はい」（小声なのでよく聞き取れず）

試験中に検索することが前提の話の流れだけど、「検索して良いですか？」「良いですよ」とはっきり言っているわけではないんだよな……。

www.youtube.com

協会主催の合格体験談オンラインセミナーでは、合格者が当たり前のように試験中の検索やカンニングペーパーの作成に言及している。

ということで、「Google検索はありなのか？」の答えは、探した限りでは、はっきり文章でOKと言っているものは無い。が、試験の主催も試験中に皆が検索や資料の参照をしていることは認識していて、咎めるつもりは無さそう。まずは公式のイベントで合格体験談を話していた人の合格を取り消せという話になるので、Twitterなどで「検索して合格した」とツイートしたところで合格を取り消されることも無いだろう。たぶん。検索に関して公式がどこかに書いているのを見つけた人がいたらコメントででも教えてほしい。

はっきりしていない状態は良くないと思う。こういう情報を知らずに受けた人は検索しても良いとは思わないだろうから、大きく不利になる。「検索ありなのかな？」と調べていたら、「自宅でのオンライン受験なのでバレません」みたいなことを書いているブログもあった。その理屈だと、カンニングと同様に規約で禁止されている代理受験もありになる。さすがに代理受験は試験主催者としては止めてほしいだろう。ちなみに、試験はブラウザなのだけど問題文のコピーはできないように対策されている。なので、検索するときは手打ち。これをコピーできるようにするブラウザ拡張があったら便利なので、そういうのも出てきかねない。

検索したら10秒で分かることを詰め込むような試験勉強はしたくないし、それをどれだけ覚えているかで合否が決まる資格に意味があるとは思わないので、試験で検索ができること自体は良いと思う。運営は「試験中にインターネットを見るのも資料を参照するのもOK」というのを試験の要項にはっきりと書いてほしい。

2020-09-21

CTFのPwnableの本の改訂版を技術書典9で頒布しています

紙は明日（9月22日23時59分）まで。電子版は会期終了後も頒布継続できるらしい。

techbookfest.org

紹介やサンプルページなど。

sanya.sweetduet.info

前回の記事。

kusano-k.hatenablog.com

File stream oriented programmingとか、glibc 2.31までの内容とかを追加した。

おかげで、InterKosenCTF 2020のFables of aeSOPは簡単に解けた。

qiita.com

以下、細々とメモ。

別の本にするのか改訂版にするのか

元々は、5月のコミックマーケットC98で別の本を頒布しようと思って、問題を作っていた。新型コロナウイルスでC98の中止が決定されたので放り投げた。このまま放置はもったいないので、オンライン開催の技術書典9の話を聞いて、もう1回取りかかった。

1冊にするには分量がちょっと少ない。 Twitterで「同人誌をシリーズにしても、基本的に前の本を買った人しか後の本は買わないから先細りだよ」みたいなツイートを見かける。「いや、○○2を見かけて、1と一緒に買ったことがあるぞ」とも思ったけど、まあ、そういう人は少なそうというのは分かる。 2だけで完結するなら良いけど、1も必要な本で1だけ完売となるとつらいし、その辺の管理も面倒そうだな……と前の本にこの内容を追加してまとめることにした。

実際、技術系の同人誌は「第○版」みたいなのをときどき見かける。これをやっている人は旧版の在庫をどうしているんだろうなぁ。 1回のイベントで、最初は旧版を頒布して、途中から新版に切り替えたら文句を言われそう。私の場合、今は在庫が無いからちょうど良いと思っていたけど、これは勘違いで、在庫が出てきたわ。

glibc 2.27とglibc 2.31の共存

2020年4月23日Ubuntu 20リリース。

CTFの問題サーバーはUbuntuのLTSで動いていることが多いと思う。この本で扱っている問題もUbuntu。 Ubuntuのバージョンによってglibcのバージョンも異なり、問題の解き方も変わる。 Ubuntu 18はglibc 2.27、Ubuntu 20はglibc 2.31。

github.com

予定通り5月に出していたなら、Ubuntu 18でも良かったかもしれないが、20リリース半年後に古いバージョンで出したくはない。「ま、攻撃コードをちょっと修正すればUbuntu 20で動くだろ」と思ったら甘かった。（私では）どうやっても解けなくなる問題があったり、問題で解説したいところ以外が面倒になったりする。

qiita.com

glibc 2.31の解説もするならば、同じプログラムをglibc 2.27とglibc 2.31でそれぞれ解くのも面白そうな気がしてきた。ということで、glibc 2.27とglibc 2.31の両方の環境を用意する必要がある。しかし、問題サーバーを2個動かすのは面倒。 1個のサーバーでプログラムごとにglibc 2.27とglibc 2.31を指定したい。

Dockerで動かしている問題サーバーの中で、さらにDockerを動かす（Docker in Docker）ことも考えたけれど、何かと面倒らしい。

システムのlibcとは別のlibcを置いたディレクトリを環境変数LD_LIBRARY_PATHに指定すれば、別のlibcを読み込ませることができる。でも、ldとバージョンがあっていないと起動中に落ちる。そしてldのパスはプログラムに絶対パスで埋め込まれているので、LD_LIBRARY_PATHが効かない。 ldのパスを書き換えれば良くて、patchelfというコマンドでそれができる。ついでにライブラリを読み込むディレクトリも指定できるので、LD_LIBRARY_PATHも不要になる。

patchelf --set-rpath /lib227/ --set-interpreter /lib227/ld-2.27.so program

CTFの出題者、libcを配布するついでにldも配布してくれないかな。そうしたら問題サーバーと同じ環境で問題のプログラムを動かせる。

印刷所

これまで同人誌の印刷はポプルスに頼んでいた。

技術書典曰く、オペレーションの都合上、搬入は1サークル1箱でQRコードを貼り付けろと。ポプルスに「1箱に詰めて、QRコードを貼り付けてくれ🙏」と頼んでやってくれるか分からないし面倒、一度自宅を経由するにしても、そんなでかい段ボール箱どうするんだ……。ということで、別の印刷所も使ってみるかと、提携印刷所の日光企画に頼むことにした。なお、この条件は「自宅から」送付する場合だけの話で、提携以外の印刷所でもこの辺の作業は不要だった。

ページ数が増えたことによって印刷代がシビアになってくる。日光企画の料金表を見てみると、高ぇ……。同人誌の原価の話がたびたび炎上するけど、利益0か赤字では……と思っていたら、これはベースの価格で、早めに入稿するだけで20～40%割引になる。pixivプレミアム会員なら5%割引。プレミアム会員でなくても申込み直前に会員になればOK。プレミアム会員費540円は誤差。さらに、指定の見積もりサービスで見積もりして、クレジットカード払いではなく銀行振り込みすればさらに5%割引（この5%は、元の値段ではなく、早期入稿などの割引を適用した後の価格がベース）。ということで、最終的な値段はあまり変わらない。

あと、冊数のに対しての印刷代の上がり方も印刷所によって全然違う。オンデマンドとオフセットでどちらが安くなるかとかも違ってきそう。「どこもたいして変わらないだろ」と思っていたけど、安く高品質で印刷したかったら色々と調べないとダメだな。

AMスクリーニングとFMスクリーニング

ということで、ほぼ同じ表紙を異なる印刷所に頼んだので、比較ができる。 1枚目がポプルス、2枚目が日光企画。どちらもオンデマンドで、「高精細表紙」みたいなオプションは無し。カメラのホワイトバランスは同じなので実際の色合いの違いもこんな感じ（再販などで違う印刷所のものと色合いを揃えたければ、前の本も送れば何とかしてくれるらしい）。

細かい粗い以前に、網点が規則的かランダムで見た目が全然違うような……。これがAMスクリーニングとFMスクリーニングか。こういうことをブツクサ言っていると、紙の本を買ってくれる人がいなくなりそうだけど、まあよっぽど目を近づけて見なければ分からん。

ポプルスがFMスクリーニング、日光企画がAMスクリーニング（オンデマンド印刷でもこの用語を使うのかは知らないけど）。以前の技術書典で買った「ねこのしっぽの4色フルカラーオフセット印刷スクリーン線数比較本」に載っていた。

www.shippo.co.jp

この本、AMスクリーニング15線～800線、FMスクリーニング70μ～20μで実際に印刷されていて面白い。これは印刷所にしか作れない本（少なくとも、ねこのしっぽは線数の指定は受け付けていないらしいので）。

AMスクリーニングとは、点の位置を固定して点のサイズで濃さを変える方式。線数が1インチに並ぶ点の個数。「細かければ細かいほど良いんでしょ。800線で印刷してくれ」と素人は思うけれど、線数が高くなると多階調がなめらかに表現できなくなるらしい。 800線を見ても違いが分からないが……。たぶん、点が細かいとサイズのコントロールが難しいのでしょう。

FMスクリーニングは点をランダムに配置し、点の個数で濃さを変える方式。 FMスクリーニングのほうが良さそうだが……この本曰く、

FMスクリーニングに関しては同人誌印刷業界では採用している会社が多いのですが印刷業界的には主流ではなく、過去の流行のような扱いになっていまして、製版機メーカーでも開発を止めてしまっているが現状です。

だそうで。 FMスクリーニングには、濃いところが潰れやすくなったり、淡いところで点の間隔が広がってしまうデメリットがあるらしい。 AM印刷の技術向上で、線数を上げられるようになったから、もうFMスクリーニングは要らないということなのだろうか。

2020-09-07

天下一 Game Battle Contest 2020参加記

tenka1.klab.jp

KLabから天下一Game Battle Contest 2020の賞金が届いた💰　一緒に冊子が入っていて、採用パンフか何かだと思ったら、技術書典の本だった。付箋が貼られていて、これは第9章。なるほど。 #klabtenka1 pic.twitter.com/O63cYxKhmj
— kusanoさん@がんばらない (@kusano_k) September 3, 2020

5,000円ゲット 🎉

住所を連絡したときの返信で「ブログ記事とか書いてね！」と言われていて、すっかり忘れていたので、今さら書く。

概要

KLab株式会社主催のゲームAIコンテスト。

去年までは天下一プログラマーコンテストということで、競技プログラミングのコンテストだったけれど、今年はゲームAIになったらしい。ゲームAIコンテストというとCODE VSがあった。 CODE VSはAI作成期間が数週間あってガッツリ時間が取られるけれど、天下一のほうは4時間の短期決戦。

AtCoderができる前のプログラミングコンテストとかGoogleくらいしかやっていない2009年にKLabは1回コンテストを開いていた。懐かしい。過去のコンテスト一覧に載っていないな。黒歴史なのか？

suztomo.hatenadiary.org

ゲームのルール

冒頭のリンク先から、参加者でなくても見られるはず。

コンテスト時間は4時間しかないので、シンプル。でもちゃんとバランスが取れていてゲームになる。これはホントすごい。別に5,000円をもらったから褒めているわけではない。

1分ごとに20x20マスの正方形が与えられて、参加者は正方形の領域を指定してマスを取っていく。各マスには点数が決まっていて、マスの点数/取った人数　の点数が1分ごとの最後に入る。基本はこれだけ。ただし、

1辺がmの正方形の領域を確保するのに (m+1)*(m+1)*125ミリ秒掛かる
- m*mではない
- m=1なら0.5秒/マス、m=2なら0.281秒/マス、m=3なら0.222秒/マス
- mが大きいところではたいした差は無いものの、小さいところだと差が大きくて、なるべく大きく取りたくなる
「マスの点数/取った人数」は、4近傍連結成分内の最小値が、連結成分全体に適用される
- 点数の低いマスが1個でも含まれていると大損なので、なるべく小さく取りたくなる
- 点数が高いマスには人が集まるからどうせ最後は一定になるんじゃないの？
  - →高いマスは点数が下がるかもしれないが、低いマスは低いままなのでちゃんと避けないといけない
1時間ごとに点数が10倍になっていく
- 最後の1時間は最初の1時間の1,000倍
- 最初のほうはスコアを気にせず試行錯誤できる
- でも、わりと接戦になるので、2時間目から3時間目あたりは手を抜けない
- でも、この辺で一旦プログラムを止めてでも、改良できれば最後の点数の伸びが違ってくるよなぁ、で悩ましい

WebAPIを叩いてゲームに参加する。領域を確保するAPIを叩いて、指定された時間が経過する前にもう1回APIを叩くと、時間が経過するまでAPI内部で待って処理を実行してくれる。プログラム中でウェイトを入れる処理を書かなくて良くなるので、これはありがたい。 WebAPIを叩いて戦うとなると、「まず運営のサーバーへのレイテンシが小さいサーバーを借ります」となりそうなところ、そういうのもあまり要らない。すごい。

1個の盤面を全参加者で共有して戦うのは良いのだけど、サブアカウントを量産して自分が取っていないマスだけを取るというチートができちゃうんじゃないかというのがちょっと気になった。まあ、そういう奴がいたらBANすれば良いだけか。

そういえば、3Dでおしゃれな感じの人力で操作できるビジュアライザもあったのだけど、ほとんど使っていないな。最初に感覚を掴むのにちょっと触って、それ以降は放置。状況の確認もWebAPIを叩いていた。なぜかというと、状況確認のAPIにもレートリミットがあって、ビジュアライザが毎秒（だったっけ？）1回消費してしまうから。何とかしてほしいところではあるものの、AIとレートを共有していないとビジュアライザのほうのAPIをAIから叩くというズルができてしまうから難しい。

私のAI

import os
import random
import time
from typing import List, Tuple
from urllib.request import urlopen

GAME_SERVER = os.getenv('GAME_SERVER', 'https://contest.gbc-2020.tenka1.klab.jp')
TOKEN = os.getenv('TOKEN', 'xxxx')

def call_api(x) -> str:
    with urlopen(f'{GAME_SERVER}{x}') as res:
        return res.read().decode()


def calc_score(stage: List[List[int]], num_claim: List[List[int]], my_claim: List[List[int]]) -> float:
    visited = [[False for _ in range(20)] for _ in range(20)]

    def f(r, c) -> Tuple[float, int]:
        if r < 0 or r >= 20 or c < 0 or c >= 20 or my_claim[r][c] == 0 or visited[r][c]:
            return 1e+300, 0
        visited[r][c] = True
        r1 = stage[r][c] / num_claim[r][c]
        r2 = 1
        for r3, r4 in (f(r+1, c), f(r-1, c), f(r, c+1), f(r, c-1)):
            r1 = min(r1, r3)
            r2 += r4
        return r1, r2

    score = 0.0
    for i in range(20):
        for j in range(20):
            x, y = f(i, j)
            score += x * y
    return score

def main():
    while True:
        game_resp = call_api('/api/game')
        game_id, remaining_ms = list(map(int, game_resp.split()))

        if game_id < 0:
            break

        stage_resp = call_api(f'/api/stage/{game_id}').split('\n')
        assert stage_resp[0] == '20'
        stage = [list(map(int, x.split(' '))) for x in stage_resp[1:21]]

        while True:
            areas_resp = call_api(f'/api/areas/{TOKEN}/{game_id}').split('\n')
            if areas_resp[0] == 'too_many_request':
                time.sleep(0.5)
                continue
            assert areas_resp[0] == 'ok'
            num_claim = [list(map(int, x.split(' '))) for x in areas_resp[1:21]]
            my_claim = [list(map(int, x.split(' '))) for x in areas_resp[21:41]]

            score = calc_score(stage, num_claim, my_claim)
            num = 0
            for i in range(20):
                for j in range(20):
                     num += my_claim[i][j]
            print(f'game_id: {game_id}  score: {score}  num: {num}')

            best = -1.0
            r, c, size = -1, -1, -1
            base = calc_score(stage, num_claim, my_claim)
            for k in range(1, 4):
                for i in range(21-k):
                    for j in range(21-k):
                        for ii in range(k):
                            for jj in range(k):
                                if my_claim[i+ii][j+jj]==0:
                                    num_claim[i+ii][j+jj] += 1
                                my_claim[i+ii][j+jj] += 1
                        s = (calc_score(stage, num_claim, my_claim)-base)/k
                        if num<64:
                            s += random.gauss(100, 10)
                        for ii in range(k):
                            for jj in range(k):
                                my_claim[i+ii][j+jj] -= 1
                                if my_claim[i+ii][j+jj]==0:
                                    num_claim[i+ii][j+jj] -= 1
                        if s>best:
                            best = s
                            r = i
                            c = j
                            size = k
            if r==-1:
                break
            print(f"{r}-{c}-{size}")
            claim_resp = call_api(f'/api/claim/{TOKEN}/{game_id}/{r}-{c}-{size}').split('\n')[0]
            if claim_resp == 'game_finished':
                break
            assert claim_resp == 'ok'

        while int(call_api('/api/game').split()[0]) == game_id:
            time.sleep(0.5)

if __name__ == "__main__":
    while True:
        try:
            main()
        except:
            pass
        time.sleep(1)

頑張っているように見えるかもしれないが、書いたのはbest = -1.0からprint(f"{r}-{c}-{size}")の間だけ。他はサンプルコードそのまま。サンプルコードでは、ここが未取得の1x1マスをランダムに取得するようになっていた。

1辺の長さ1-3の正方形を全ての場所に置いて、一番スコアが高いところ（スコアを計算する関数はサンプルにある）に置くだけ。 1x1だけ取っていくのが良さそうだけど、点数が高いところは結局下がって、2x2とか3x3で取ったほうが良さそう盤面になることが多かった。

大きい正方形のほうが点数が高くなりがちなものの時間が掛かるという代償がある。なので、1辺の長さで割っている。これ何が正しいのか分からなかった。 1辺の長さで割ることが正しいなら1-3ではなく4とか5とかも試せるはずだけど、range(1, 4)をrange(1, 5)にしたらスコアが下がった。

みんな同じ事を考えて、最初に同じ所を取って点数がガクっと下がったら嫌なので、一応乱数で少しばらしてみた。効果は分からん。

たいしたことは何もやってないな。いつもQiitaを使っているのでQiitaに書こうと思ったが、記事のプログラミング要素が少なすぎて怒られそうなので、はてなに書いた😇

kusano_k’s blog

暗号通貨Qtumのoffline stakingについて

Qtumとは

Proof of Stake（PoS）とは

Offline staking

Offline stakingに対する攻撃

Super stakingします

DISCO presentsディスカバリーチャンネルコードコンテスト2021参加記

予選

本戦（問題以外）

本戦（問題）

SoftEther VPNのL2TPにWindows 10の標準機能のL2TPで繋ぐときのエラー

Quora Programming Challenge 2021

Quora Programming Challenge

私のコンテスト中の様子と回答

1問目: digest

2問目: escape

3問目: students

3問目: walls

4問目: tourism

日本ディープラーニング協会G検定でGoogle検索はありなのか？

CTFのPwnableの本の改訂版を技術書典9で頒布しています

別の本にするのか改訂版にするのか

glibc 2.27とglibc 2.31の共存

印刷所

AMスクリーニングとFMスクリーニング

天下一 Game Battle Contest 2020参加記

概要

ゲームのルール

私のAI