プログラミング

TwitterにDeflate圧縮されたバイナリをアップロードして利用する 🤔

まずはこれらのツイートを見てほしい。echo 'class ${public static void main(String[]a)throws Exception{var b=new int[810000];https://t.co/hd3ce1Xpzc(new https://t.co/vgGGZeOChL.File("/media/0")).getRGB(0,0,900,900,b,0,900);for(int i:b)if((i&255)!=0)System.out.write(i);}}'>$.java java $.*>_.java java _.* #シェル芸 pic.twitter.com/aCxDjD9ZS1— 社畜ちゃん (@Shachiku_nyan) February 23, 2023 次は◉のターンめう～ 　１２３４５６７８ Ａ　　　　　　　　 Ｂ　　　　　　　　 Ｃ　　　　　　　　 Ｄ　　　〇◉　　　 Ｅ　　　◉〇　　　 Ｆ　　　　　　　　 Ｇ　　　　　　　　 Ｈ https://t.co/TZGGgxwtH7— シェル芸bot (@minyoruminyon) February 23, 2023 5F6F6E4F5G6G7G8H3D5H8G3E2E6D6H7H7D4G7E3F2G7F8F8E4H4C5C3C5B2C1C6B7A8C8D7C2D6C7B3G3H2H8B4B5A8A6A1H3A4A1B1A3B2B1E2F1G1F1D2A #シェル芸 https://t.co/mYeyPWMN9Y— 社畜ちゃん (@Shachiku_nyan) February 23, 2023 〇の勝ちめう！ 　１２３４５６７８ Ａ◉〇〇〇〇〇〇〇 Ｂ◉〇〇〇〇〇〇〇 Ｃ◉〇〇〇〇〇〇〇 Ｄ〇〇〇〇〇〇〇〇 Ｅ〇〇〇〇〇〇〇〇 Ｆ〇〇〇〇〇〇〇〇 Ｇ〇〇〇〇〇〇〇〇 Ｈ〇〇〇〇〇〇〇〇 https://t.co/1Ux236CqEU— シェル芸bot (@minyoruminyon) February 23, 2023 シェル芸bot（@minyoruminyon）とは、それがフォローしているユーザが #シェル芸 等のハッシュタグをつけてシェルコマンドをツイートしたとき、引用RTでその出力をつぶやくbot [注1] 。 つまり、上記のツイートはシェル芸botにjavaコマンドを実行させてオセロをしているということになる。しかしオセロのソースコードは含まれていないように見えるが……？ /media/0シェル芸botには、ツイートに添付された画像を /media ディレクトリ下にあるものとして実行する機能がある。1枚ならその画像は /media/0 。 つまり最初のツイートは、画像を読み込んで java.awt.image.BufferedImage.getRGB(int startX, int startY, int w, int h, int[] rgbArray, int offset, int scansize) によって埋め込まれたバイナリを取り出しているということになる。 記事タイトルが物々しかったが、「Deflate圧縮されたバイナリ」とは、ただ単に「バイナリを埋め込んだPNG画像」のこと。 ちなみにDeflateはおなじみZIPやgzipにも使われる可逆圧縮アルゴリズム。 ちなみに元ツイートを書いた人によると、埋め込まれているのはJavaのソースらしい [2]。手元で実行してみたらわかる。 扱える画像今どうなっているかは知らないが、どうも数年前時点でのTwitterの画像の仕様はこうらしい [3]（読み間違いがあれば申し訳ない）。JPEGは原則、quality85の4:2:0クロマサブサンプリングされたJPEGとして再エンコードされる。ただし次の条件をすべて満たすならば再エンコードしない。画像サイズが4096x4096以下である。5MB以下である。画像の回転が必要であるような情報を持っていない。1ピクセルあたり1バイト未満である。WebPもquality85のJPEGに変換される。PNGは色深度や画像サイズによって異なる。PNG-8は保持される。PNG-24,PNG-32のうち、実際の色数が256色以下であるならばPNG-8に変換される。上記を満たさないPNG-24,PNG-32のうち、画像サイズが900x900以下ならば保持される。上記を満たさないPNG画像は、JPEGに変換される。扱える最大の画像サイズは4096x4096である。 つまり、900x900のPNG-32を使えば約3MBもの情報を使うことができる。4枚使えば4倍（要検証）。 ……4096x4096のPNG-8でも16MBの情報を使えるのでは？などと思ったが多分JPEGに変換されるんだろう。知らんけど。 あとはプロトコルを交換しておけばメモ帳アプリのスクショをツイートするよりも大量の情報を一気に投稿できる（誰にわかるねん）。 おまけ失敗しとるやないかい！ Lorem ipsumが出る予定だったのに/media/0: PNG image data, 15 x 10, 8-bit colormap, non-interlaced https://t.co/V6BDW0Wr5q— シェル芸bot (@minyoruminyon) February 28, 2023 ツイート1: 本当なら 8-bit/color RGB になってもらう予定だったが、256色以下だったので colormap に変換されてしまった例!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`a%bcdefghijklllllllll https://t.co/MTbx2B4GR7— シェル芸bot (@minyoruminyon) February 28, 2023 ツイート2: WebPに変換される（多分？）とかいう知らない仕様によってASCIIコード表から順番に持ってきたみたいな謎文字列が出ている例 参考文献[1] 社畜ちゃん（@Shachiku_nyan）「echo 'class ${public static void …」 https://twitter.com/Shachiku_nyan/status/1628601778345500674 （2023年2月27日アクセス） [2] 社畜ちゃん（@Shachiku_nyan）「@AAAR_Salmon javaのソースそのまま押し込めてますw」 https://twitter.com/Shachiku_nyan/status/1628699291454963712 （2023年2月28日アクセス） [3] NolanOBrien「Upcoming changes to PNG image support」 https://twittercommunity.com/t/upcoming-changes-to-png-image-support/118695 （2023年2月28日アクセス） [注1] ふるつき「今の所判明しているシェル芸botの仕様」 https://furutsuki.hatenablog.com/entry/2018/07/13/221806 （2023年2月28日アクセス）

内容を見る

人工知能

OUCRC最強オセロAI決定戦@学祭 の報告

2022年11月5日、2022年11月6日――岡山大学祭が3年ぶりにオンサイト開催されたこの日、電子計算機研究会は一般教育棟A37講義室を借りて展示をしていた。 ゲームが多数展示される中、1つ異質な存在があった。AI vs AI オセロ対決 のディスプレイである。 7月末に発足したこのプロジェクトは、以下のように進んだ。 8月上旬　主犯はゲームを決定するための投票をする。クソデカオセロ（盤面20x20のオセロ、原作）に決定。 8月中旬　主犯はターン制ゲーム用のサーバ（Go, MQTT）を途中まで作っていたが放棄する。 9月下旬　プロジェクトが再始動する。 10月上旬　主犯はモックサーバ（Go, HTTP）の作成を開始する。OpenAPI で仕様書を書いて OpenAPI Generator で自動コード生成したかったらしい（文言からわかるように、頓挫している。理由は仕様を決めかね続けてエターナったため）。 10月中旬　主犯はオキリョウ氏にサーバ（Kotlin, HTTP）作成を依頼する。まっともぉん氏はUnityでディスプレイ用アプリの作成を開始する。まっともぉん氏はAIを完成させ、アプリに内蔵する。 10月下旬　主犯はオセロゲームの作成を開始する。オキリョウ氏はサーバとAIを完成させる。 10月28日　ゲーム内容を通常の8x8のオセロに変更。 11月4日　学祭前日。みんなでデスマーチ :smiling_face:。 11月5日　学祭1日目。未明、主犯はモデルの学習プログラムを完成させ、学習を開始する。明け方、Pon氏はAIを完成させる。1日目展示開始時点で完成していたAIは3つであった。 11月6日　学祭2日目。午前12:03、主犯は通信プログラムを完成させ、AIを使える状態にする。2日目展示開始から数分後にセットアップし、無事4つのAIが対戦した。 ガバガバっぷりが酷い。スケジュールをもう少しきちんとして欲しい。9月の空白の区間は何だったのか。しかももともとこのプロジェクトの参加予定者は4人より多かった。 AIについての作者コメント AI作者の4名からコメントを頂きました。 まっともぉん（MatsuBot）仕組み1. 配置可能な場所をリスト化にする 2. リストの値をランダムに1つ取得する 3. 配置する ランダム配置 AI BOTです。 時間に余裕あれば開放度理論とマス目自体の重みで判定する簡単なアルゴリズムを組もうとはしてた…感想ランダムAIもなんだかんだ勝率良かったのが一番驚愕でした（本当は「時間かけて作ったAIがランダムBOTに負けてる乙ｗｗｗ」って全力で煽りたかったけど、みんな徹夜して作成してたので流石に言えなかった。余裕もって作れ！！とは思うけど） 対戦・表示する仕組みがせっかく整ったので、AI持ち寄って戦わせる企画を部で相続するのはありかも？プログラミング・AI・通信について学べるし何はともあれお疲れ様どす確かにプログラミングの重要な要素を色々カバーできてるし、勉強会の材料としてよさそう。ソースをオープンにしてくれ。 なりました オキリョウ（Hoge）仕組み1. 定石（https://bassy84.net/othello-top-index.html）うさぎと虎と牛のうち、主要なものを入力 2. 開放度理論（https://kozu-osaka.jp/cms/wp-content/uploads/2020/11/077c2ec004566f2968e2f3089333ede7.pdf）を元に、数手先（大体4手くらい）を読んで（自分の開放度 - 相手の開放度）の合計が最も小さくなるような手を打つ 3. 全探索（残り11手）感想ガキの時にC#でオセロAIを作ったことがあったがクソ雑魚だった それから一回り成長したことを実感できてよかった 成績としては自分だけ無双している 勝てる分には嬉しいが、もう少しいい勝負してほしかった せめて他のBotにはランダムBotくらいボコボコにして欲しかった・・・ コードはこちら：　https://github.com/Wansuko-cmd/reverse-appごめん。みんな乱択ベースだから許して。 Pon（Pon）仕組み1. 配置可能な場所とその時めくれる石数をリスト化する 2. そのリストを「めくれる石数」の降順でソートする 3. そのリストの「めくれる石数」が同じものを一定確率で入れ替える． 4. そのリストの上位log_2(残りのターン数)個の中からランダムに一つ選ぶ． 5. 選んだものの場所へ配置する．感想他のAIに勝てるか自信があまりなかったがまさかランダムAIに引き分けるとは思わなかった．正直めっちゃ悔しい！めくれる，めくられる石数を数手先まで重み付きで読んでみればまた結果は変わったかもしれない．（ワンチャン時間あったら作るかも） 通信関連について勉強することになったのは意外だったが，結構いい勉強になった．他にもpythonのファイル分割などの（個人の実装で）初めて試したことやプログラムの作り方における反省点（最初クソデカ関数作ってしまった）とかが分かったので良い経験になったと思っている．とりあえず次にこのような機会があった時にAIで勝てるよう勉強頑張ります． お疲れさまでした！序盤取りすぎないというロジックを乱択で組むのは面白い。Pythonについてはパッケージ管理ツールを使うと便利なので今度教える（今回は NumPy と Requests ぐらいだったので困らなかったが）。 終に鮭（Salmon）仕組み畳み込みニューラルネットワーク（転置畳み込みを含むのでそう言っていいかは分からない）で盤面から状態行動価値関数を計算するように作った。 所謂 Deep Q Learning（DQN）のようなものだが、一般的な手法として存在を知っていたわけではなく、足りていない部分が多いと思う。 層は以下の構成だが、振り返るとあまり良さそうではない。オセロにおいて辺や角に置かれている駒は極めて重要なので、畳み込みより全結合のほうが良かったかもしれない。 図1: Salmon AI の CNN の構成 学習においては、自身と対戦を行い、各試合の勝敗に応じて各対戦者の指した手に良いか悪いかを割り当てて教師ベクトルとする。 これを100回行うごとにミニバッチ学習をする。感想ニューラルネットワーク歴3週間ほどである上、よく使われる構成も知らないため適当に組んだ。これより前には MNIST しか組んでいない。 そもそもQ学習だと思っていない。クラス分類問題のつもりで作った（その割に運用時は argmax ではなく softmax を使っているが）。 とりあえず今思いついている改善点は、 - 全層 fc にする（下手に畳み込みしない） - 負けたときの手を学習データに含めないようにし、損失関数を CrossEntropy にする の2つ。 追伸：v2 では全層全結合にした。モデルの state_dict は36KB→100KB超に増えた。 他のAIに対しての勝率は良いとは言えないが、ひとまず v1 には勝てるようになったので良かったかなと。 結果報告 さて、最強決定戦なのにインメモリデータベースに保存しており最早学祭時の対戦データが残っていない本企画である。 オキリョウ氏の協力を頂き、データベースを PostgreSQL に置き換え、再現して実行した。 図2: ルームデータの保存形式（psqlでSELECTしている画面） 結果を Python で適当に加工し、JSON に変換して保存し直した。# jq '{ users, results: [.results[0]] }' results.json {   "users": {     "d34a33b0-b29a-4daa-8682-1604bcc4dbf6": "Pon",     "053b45b6-c029-4b19-9f62-f5d366a9a89e": "MatsuBot",     "99cb0ee1-f56b-46bf-8d91-6bae860603bd": "Salmon",     "f751d4ad-cebd-4f9e-be2b-01d9ca8d34f5": "Hoge"   },   "results": [     {       "black": "99cb0ee1-f56b-46bf-8d91-6bae860603bd",       "white": "d34a33b0-b29a-4daa-8682-1604bcc4dbf6",       "board": "2,1,1,2,2,2,2,2|2,2,1,2,2,2,2,1|2,2,1,2,2,2,2,1|2,2,1,1,1,2,2,2|2,1,1,2,2,1,2,2|2,1,2,2,1,2,2,2|2,2,1,1,1,1,2,2|2,2,1,1,1,1,1,2"     }   ] } 勝率各AIの勝率は以下のようになった。 表1: 各AIの勝率表 スクリーンショット 図3: まっともぉん作の表示アプリ （文責：終に鮭 a.k.a. AAAR-Salmon）

内容を見る

ガジェット/ハードウェア

WSLを入れよう！　入れなければ　ならぬ

どうも。部のPCにWSLを入れて回る職人です。貴様（敬称）のPCにも入れなさい。 一応WSLについて軽く解説しておくと、Windows Subsystem for Linuxの略で、Windows 10以降で利用できるLinuxの仮想環境です。 WSL2はHyper-Vアーキテクチャを利用する仮想マシンプラットフォームの上でWindowsとLinuxをコンテナとして動かす機能です（注）。 つまりLinuxがコンテナとしてWindowsと同じレイヤーで動きます。 ここ がわかりやすいのでもうちょっと詳しく知りたい人は読んでくれ。正しいかは知らん （注）メインOS（ホストOSと呼んでいいのか分からんので誤魔化してこういう言い回しにした）であるWindowsを、Windowsサンドボックスというコンテナとして隔離して動かすだけであって、Hyper-VのようにWindowsコンテナを複数作る機能はWSLの範疇外のことです。 これは今後もインストールしたり、環境をリセットしたりしたくなったときのための自分用のメモ書きです。とりあえず入れよう今はコマンド1つで入れられるようになったんですね。しかもただディストリビューションをインストールするだけじゃなく、WSLと仮想マシンプラットフォームの有効化最新のWSL用LinuxカーネルのダウンロードとインストールWSL2をデフォルトに設定までやってくれるらしいです。はえ～（ソース：イカリ おこのみ屋 https://docs.microsoft.com/en-us/windows/wsl/setup/environment） コマンドは、wsl -l -oでインストール可能なディストリビューションの一覧を表示、wsl --install [-d <Distro>]でディストリビューションを指定してインストールできます（-dオプションを省略するとUbuntu）。 ただし、このインストール方法はWindowsのビルド19041（Win10 2004）以降でのみの対応です。 前はこれに該当するバージョンでもダメだったので古いバージョンにも降りてきたっぽいですね。ありがたい。 それ以前のWindowsを使用していたり、一覧に出ないディストリビューションや、 docker export して吐かせたtarballなどをWSLディストリビューションとして利用したい場合（wsl --import でできます）、DockerバックエンドとしてのみWSL2を利用したい場合などはこれまで通り手動でインストールしてください。 しかしAlpine Linuxがないな。なぜ（普段遣いするPCはUbuntuでもいいけど、たまにしか触らないPCなら軽量な方が……）。起動インストールしたディストリビューションを起動します。スタートメニューに追加されてるのでクリックしてください。 暫く待つと Enter new UNIX username: とユーザー名を入力するように言われるので入力します。なんでも良いです（rootとかでなければ）。 パスワードも設定するよう求められるので適当に決めてください（どうせそのローカル環境でしか使わないからpassにしてるけど多分よくない）。入力途中は何も表示されませんがそれであってます。Bashの設定Bash以外のシェルを使うのもいいんですが、最初はBashにしとくのが無難かなと思います。デファクトスタンダードなので[独自研究]。個人的にはfishというシェルを推していますが、POSIX互換じゃないし万人受けはしないだろうなーと思います。何も設定しなくても便利なのでdockerみたいな使い捨ての環境でも重宝しますよ。abbrとかいう神機能もあるし（Macなどでも標準で採用されていて人気のあるzshにはzsh-abbrという拡張があるようですが）。でも使い捨ての環境でそんなシェル中心に触る作業多くないか。 WSLを使う上ではなんたってシェルが命です。現状、Win10のデフォルトでは多分GUIに対応していませんので。 故に使いやすいように設定していきます。いや私はしませんので貴方で勝手にやってください。設定するファイル編集する必要のあるファイルは主に .bashrc です。最初から色々書いてくれてるのでまずmv .bashrc .bashrc_origなどとして一度除けます。echo '. $HOME/.bashrc_orig' > .bashrcとかなんとか打てば .bashrc を作成して（ディレクトリでなく書き込み権限があればファイルが存在しても上書きしちゃうので順番には気をつけましょう）その中身が. $HOME/.bashrc_origになります。これで .bashrc_orig が読み込まれます。これより後ろの行に自分で設定を追加していきます。エイリアスの設定エイリアス(alias)とは別名のことで、コマンドに別名をつけることができます。 これを利用して、最低限必要なエイリアスを .bashrc にvimなりなんなりで書いてください。それが以下です。alias rm='rm -i' alias mv='mv -i' alias cp='cp -i' alias ls='ls --color=auto'rm，mv，cpのiオプションは上書きする際に確認をするオプションです。これがないと事故りやすいので必ず書いてください（rmについてはtrash-putなどを使ったほうがいいかもしれませんが）。 lsのcolorオプションは読んで字の如く色をつけるオプションです。ないと見づらいので書いたほうがいいです（同様にgrepも書いたほうがいい）。ただし、lsもgrepもUbuntuなら初期設定の.bashrc（つまり上で移動した.bashrc_orig）に書いてあるので書かなくてもいいです。Windowsパスの引き継ぎをしないようにする初期設定だとWSLの側で環境変数PATHを引き継いでしまいます。するとLinuxから直接コマンドで叩くことがないようなものを大量にTab補完時の検索対象にしてしまい、邪魔だし検索時間も長くなります。これをしないように設定しましょう。sudo tee -a /etc/wsl.conf << END 1>/dev/null [interop] appendWindowsPath = false ENDこれでよし（普通にVim使えや[解説1]）。/etc/wsl.conf に2,3行目の内容が書き込まれたはずで、これでWindowsのパスが含まれないようになりました。一部だけ叩けるようにしたいでも一切Windowsの側のアプリケーションを叩かないかといえばそうでない場合があるかもしれません（例えば私はVisual Studio CodeはLinuxからWindowsにインストールしているものを呼び出すことがよくあります）。こうした場合のために、シンボリックリンクを作っておきましょう。 例えば C:\Users\salmon\AppData\Local\Programs\Microsoft VS Code\ にVSCodeがインストールされていたとしましょう。このとき、その中の bin\code をLinux側から叩くことでVSCodeを起動することができます。フルパスで打つのは面倒なので、パスの通った場所にシンボリックリンクを置きます。 例えばmkdir -p ~/.local/winbin echo 'export PATH="$PATH:$HOME/.local/winbin"' >> ~/.bashrc ln -s "/mnt/c/Users/salmon/AppData/Local/Programs/Microsoft VS Code/bin/code" ~/.local/winbin/codeとすれば ~/.local/winbin にパスを通してシンボリックリンクをそこに置くことができます。その他おすすめのツール等せっかくLinuxを入れたら入れるべきものはたくさんありますが、ぜひネットで探してみてください。私がおすすめするツールはこの辺です。Vim（Viとの違いは知らんけど設定しなくても色がつくので入れてる）Python3（さらっと書けるから入れてるやつ。シェルだけでは厳しいときに。python3 -c でワンライナーにも組み入れられる。pyenvで入れるべき？知らんがな）Git（言わずとしれたバージョン管理システム。そらいるよ）GitHub CLI（git clone git@github.com:USER/REPO.git って打つの面倒やん。gh repo clone [USER/]REPO で済むんですよ）fish（さっきも言ったけど）jq（CLIで動くJSONプロセッサ。パイプの途中でJSONデータを使いたいときとかcurlと組み合わせて使ったりとかすると便利かも）yq（CLIで動くYAMLプロセッサ。本当は入れてないシリーズその1）Rust,Cargo（Rustをしょっちゅう書くわけではないのだが、Rust製のコマンドラインツールは速いものが多い上、cargo install で一発インストールできて重宝している）pnpm（Node.jsのパッケージ管理ツールなのだが、これ自体がNode.jsのバージョン管理ツールも兼ねている。.node-version ファイルに対応したら本格的にnvmもfnmもいらなくなる）Docker（コンテナ仮想化プラットフォーム。Docker Desktop for Windowsを入れてるが別にコマンドしか叩かないのでLinuxスタンドアロンでいい気がする。GoogleがGoogle Kubernetes EngineなんてIaaSを出してるのでK8sことKubernetesもそのうち使いたい）Pandoc（ドキュメント変換ツール。本当は入れてないシリーズその2。Markdownで書いたテキストをLaTeXに変換したりできる） さあ、みんなもLinuxで楽しいシェルライフを楽しもうな。ke2daira で遊ぼうや参考文献[1] Qiita matarillo「WSL2とHyper-Vの関係」 https://qiita.com/matarillo/items/ca1eecf8f9a3cd76f9ce [2] Microsoft Docs「Set up a WSL development environment」https://docs.microsoft.com/en-us/windows/wsl/setup/environment [3] Wikipedia「Wikipedia:独自研究は載せない」https://ja.wikipedia.org/wiki/Wikipedia:独自研究は載せない [解説1] cat とヒアドキュメントを利用してファイルに書き込む小技はよくありますが、ファイルリダイレクションに関しては sudo で書き込み権限を与えることはできません。そのため、sudo cat ではなく sudo tee を用いてファイルに書き込みを行っています（tee は標準入力で受けたものを標準出力とファイルに吐き出すコマンド）。入力した内容はターミナルに残るので出力は /dev/null に飛ばして消しています。この方法はDebianでのgh のインストール等でも使われていました（入力はヒアドキュメントではなくパイプですが）。

内容を見る

プログラミング

4200000000Hzでゴリ押す！！！(2)

今回はアルゴリズムとCPUのパワーでパズルを全力で解きます。 Exponential Idle（Android版 / iOS版）というクリッカー系放置ゲーム中のミニゲームである、矢印パズルを攻略します。 こちらのnoteの記事にめっちゃ影響を受けて書くことにしました。 と言っても、初級と中級は私でも頑張れば解けたのと、上級も先行研究があるので、エキスパートに絞って話を進めていきます（まあ上級も同じプログラムをちょちょっといじれば簡単に解けますが）。訂正とお詫び前回のサムネイルの一部に「♪ラデツキー行進曲（1.5倍速）」とありましたが、正しくは1.543倍速です。謹んでお詫び申し上げます。ルール説明（エキスパート）図1：矢印パズル（エキスパート）のルール六角格子状に並べられたタイルをタップすると、そのタイルを含む周囲（最大）7個のタイルがそれぞれ時計回りに60°回転します。 それを繰り返してすべてのタイルの向きを上向きに揃える、というルールです。目標盤面を入力として受け取り、各タイルのタップ回数を出力する。基本の考え方1回タップすることに60°回転するので、6回同じ場所をタップすれば盤面の状態は変わらず、加法巡回群をなすような6元集合、$\mathbb{Z}/6\mathbb{Z}$ を持ってくる。解法案1参考文献[3]と同様に、$\mathbb{Z}/6\mathbb{Z}$ 上の37次の線形方程式を解くことに帰着させる方法です。が。 聡明な読者の方ならお気づきでしょう。$\mathbb{Z}/6\mathbb{Z}$ は体でしょうか。2,3,4は乗法逆元を持たないので体ではないですね。 すると線形方程式を解くときに除法が使えないということになり、掃き出し法は使えないことになります（ピボットを1にできないだけで掃き出せないわけではないだろうが、一般的なアルゴリズムをそのまま持ってくるのは厳しそう）。2掃き出しで解けない（難しい）と言っても、元は有限個しかないので $6^{37}=6.2 \times 10^{28}$ 通りすべてを試してしまえという考え方。猿。 いや無理やけど。もし1パターンを1nsで検証できたとしても6.2e19 s掛かります。実際は1パターンの検証で約7x37回の足し算をすることになるのでもっとかかります。 imos法で最適化すればどうにかなるようなレベルの話ではないです。やるだけ無駄。3大本命。DFSです。DFS自体は木の全探索なのですが、探索の必要がない部分を枝刈りすればだいぶ計算量が減ります。どれぐらい絞れるかは後述。 今回はこれを採用。プログラムこれが解を探索するプログラムです。 入力の数字は、ディスプレイモードを数字にして表示された数字ということになっています（内部的には-1して持っているが）。#include <iostream> #include <vector> #include <tuple> #include <algorithm> using index_t = std::tuple<int, int>; using board_t = std::vector<std::vector<int>>; const int mod = 6; const size_t board_row = 7, board_col = 7; void dfs(board_t &board, board_t &hands, index_t index); void flip_around(board_t &board, index_t index, int amount); index_t next(index_t index); bool is_in_board(index_t index); void print_board(const board_t board); const index_t end_index = next({ 6, 6 }); int main() {   board_t board(board_row, std::vector<int>(board_col));   board_t hands(board_row, std::vector<int>(board_col));   for (index_t i = { 0, 0 }; i != end_index; i = next(i)) {     const auto [r, c] = i;     std::cout << r << " " << c << ": " << std::flush;     std::cin >> board[r][c];     board[r][c]--;   }   dfs(board, hands, { 0, 0 });   return 0; } void dfs(board_t &board, board_t &hands, index_t index) {   if (index == end_index) {     print_board(hands);     exit(0);     return;   }   auto [r, c] = index;   // 右端辺での枝刈り   if (c == 6 && r > 3 && board[r - 1][c - 1] != board[r - 1][c]) {     return;   }   // 下端辺での枝刈り   if (r == 6 && c > 3 && board[r - 1][c - 1] != board[r][c - 1]) {     return;   }   // 上端、左端辺以外での枝刈り   if (r != 0 && c != 0) {     // 左上マスを0にするように動かす     const int hand = (mod - board[r - 1][c - 1]) % mod;     hands[r][c] = hand;     flip_around(board, index, hand);     dfs(board, hands, next(index));     flip_around(board, index, mod - hand);   } else {     for (int hand = 0; hand < mod; hand++) {       hands[r][c] = hand;       flip_around(board, index, hand);       dfs(board, hands, next(index));       flip_around(board, index, mod - hand);     }   } } void flip_around(board_t &board, index_t index, int amount) {   // 正体不明だがちゃんと最初だけ初期化処理が走る   static std::array<index_t, 7u> dpos{     dpos[0] = { -1, -1 },     dpos[1] = { -1, 0 },     dpos[2] = { 0, -1 },     dpos[3] = { 0, 0 },     dpos[4] = { 0, 1 },     dpos[5] = { 1, 0 },     dpos[6] = { 1, 1 }   };   const auto [r, c] = index;   for (const auto [dr, dc] : dpos) {     if (!is_in_board({ r + dr, c + dc })) continue;     board[r + dr][c + dc] += amount;     board[r + dr][c + dc] %= mod;   } } index_t next(index_t index) {   auto [r, c] = index;   if (c == 6 || c - r >= 3) {     r++;     c = std::max(r - 3, 0);   } else {     c++;   }   return { r, c }; } bool is_in_board(index_t index) {   auto [r, c] = index;   return std::abs(r - 3) <= 3 && std::abs(c - 3) <= 3 && std::abs(c - r) <= 3; } void print_board(const board_t board) {   for (size_t i = 0; i < board_row; i++) {     for (size_t j = 0; j < board_col; j++) {       if (is_in_board({ i, j })) {         std::cout << board[i][j] << " ";       } else {         std::cout << "  ";       }     }     std::cout << "\n";   }   std::cout << std::endl; } こんなに const とか & とか書くんだったら最初からRustでやればよかったなと若干の後悔。 ぼちぼち解説していきます。 まずここ。using index_t = std::tuple<int, int>; using board_t = std::vector<std::vector<int>>;index_t というエイリアスに std::tuple<int, int> を当てています。 index_t index = {row, column}; となっているならば、index は、row 行 column 列のパネルの位置を表します。 board_t には std::vector<std::vector<int>> を当てていますが、 board_t board(R, std::vector<int>(C)); としたならば、board は、R 行 C 列のパネルの二次元配列を表します。（入力と）パネルの現状態と出力する手数に使います。 図2：indexの指し方 次はここ。index_t next(index_t index) {   auto [r, c] = index;   if (c == 6 || c - r >= 3) {     r++;     c = std::max(r - 3, 0);   } else {     c++;   }   return { r, c }; }next関数はその名の通り、次に探索する（タップ回数を決定する）点を決定する関数で、DFSでの探索順に直接関わってきます。 定義はまあ見りゃわかりますね（ifの条件に c - r >= 3 とか書いてあるが、これは条件をいっぱい書きたくなかったからうまいこと纏めてあるだけ）。 2行目の auto [r, c] = index; ってのは構造化束縛というC++17以降で追加された機能です。分割代入だと思って大体問題ありません。 一応探索順を図に示しておくとこうです。図3：DFSの探索順この順序にしているのは、単純に分かりやすいという以外にもう一点理由があって、枝刈りがしやすいという点。 枝刈りの方法はdfs関数を見ればわかります。 void dfs(board_t &board, board_t &hands, index_t index) {   if (index == end_index) {     print_board(hands);     exit(0);     return;   }   auto [r, c] = index;   // 右端辺での枝刈り   if (c == 6 && r > 3 && board[r - 1][c - 1] != board[r - 1][c]) {     return;   }   // 下端辺での枝刈り   if (r == 6 && c > 3 && board[r - 1][c - 1] != board[r][c - 1]) {     return;   }   // 上端、左端辺以外での枝刈り   if (r != 0 && c != 0) {     // 左上マスを0にするように動かす     const int hand = (mod - board[r - 1][c - 1]) % mod;     hands[r][c] = hand;     flip_around(board, index, hand);     dfs(board, hands, next(index));     flip_around(board, index, mod - hand);   } else {     for (int hand = 0; hand < mod; hand++) {       hands[r][c] = hand;       flip_around(board, index, hand);       dfs(board, hands, next(index));       flip_around(board, index, mod - hand);     }   } }私もそこまでアホではないし、この関数は深い再帰を伴うので引数の大部分は参照で受けるようにしました。 部のC#erの皆さんが卒倒するかもしれませんが、vector<T>は値型です。というか、C/C++に値型・参照型という分け方はありません。 明示しない限り常にすべて値渡しになるので、ちゃんと参照渡しになるよう指定してやります。 さておき、枝刈りの話。これも図に示したほうが早いでしょう。図4：dfs関数の枝刈り図3に示した探索順から分かるように、27,32,36のノードでは、そのノードを操作した後は左上と真上の変化がないので、その2箇所の状態は必ず同じでなければならず、そうでなければ後退して探索し直すことになります。34,35,36でも左上と左下で同じことが起こります。 また図3から分かるように、ある時点で探索しているパネルの左上にパネルがあったとき、探索しているパネルを動かした後に再び左上のパネルが変わることはないので、左上は0にならなくてはなりません。よって左上のパネルを元にただ一通りに決まります。逆に言えば、0～5の中から自由に選べるのは左上にパネルが存在しない0,1,2,3,4,9,15のたった7個のパネルのタップ回数のみです。したがって、検証の必要なパターン数は $6^7 \approx 10^{5.45}$ 通りだけになります（ただし、関数呼び出し自体が重いことと、これらの点の不正性が分かるまでに再帰の深いところに潜ることがあるのでやはりある程度計算に時間はかかる）。 こんな感じで殆どの点で枝刈りが行えることがわかりますね。 if (index == end_index) {   print_board(hands);   exit(0);   return; }で、最後36番が終わればここの分岐にたどり着いて終わりです（なんでこの人exitとreturn両方書いてるんだろう）。 でも図4を見てもらえばわかりますが、36番ノードだけチェックが入ってないんですよね。 これでいいのかと言われれば良くて、解が存在するならば、36番ノードだけが非0であることはありません。 流石に解が存在しない問題は生成されないだろうということでここは一つ。 flip_around(board, index, hand); dfs(board, hands, next(index)); flip_around(board, index, mod - hand);ところでこの部分ですが、再帰DFSにおける常套手段です。 ある変換（ここではある1パネルをn回タップすること）が可逆であるならば、dfs呼び出しから帰ってきた後に逆変換（ここでは同じパネルを6-n回タップすること）を行えばうまいことDFSになります。是非覚えておいてください。 以上。閑話void flip_around(board_t &board, index_t index, int amount) {   // 正体不明だがちゃんと最初だけ初期化処理が走る   static std::array<index_t, 7u> dpos{     dpos[0] = { -1, -1 },     dpos[1] = { -1, 0 },     dpos[2] = { 0, -1 },     dpos[3] = { 0, 0 },     dpos[4] = { 0, 1 },     dpos[5] = { 1, 0 },     dpos[6] = { 1, 1 }   };   ... }この部分、何ですか。自分で書いたけどどういう理屈で初期化されているのかわかりません。C++プロの方、教えて下さい。 aggregateならメンバ名を指定して初期化する方法があるけど、その延長と考えていいんですかね。参考文献[1]Conic Games「Exponential Idle - Google Play のアプリ」<https://play.google.com/store/apps/details?id=com.conicgames.exponentialidle> [2]Gilles-Philippe Paille「「Exponential Idle」をApp Storeで」<https://apps.apple.com/jp/app/exponential-idle/id1538487382> [3]ちゃそ「Exponential Idle #2 矢印パズル攻略法（と二元体GF(2)上の線形方程式について）」<https://note.com/so_ra_64/n/n9c2eb6a5ef6f> [4]ますたー。/繰り上げP「焼き甜花ちゃんシリーズの作り方＆素材」<https://www.nicovideo.jp/watch/sm37861810> [5]いもす研「いもす法」<https://imoz.jp/algorithms/imos_method.html>

プログラミング

競プロ環境構築#3 Python編

Windowsの方はWSLを入れて読んでください。 Pythonはいいぞ。Pythonはクソ。私がPythonを始めようとしているすべての人（上級者とか逸般人とか言われる人を除く）に言っていることです。 Pythonをやりましょう。 プログラミング初心者が一番最初に触るのに適している言語はPython…そんなわけ無いですね。JavaScriptだと思います(個人の感想です)。 JavaScriptについては別の回でやります。 まあPython人気ですし。やりましょう。図1：Googleトレンド「プログラミング言語」関連トピックの人気順5位がPython(2021年6月28日現在)←執筆をサボってたのがバレちゃう！ Pythonが初心者向けである理由ググれ。というのもなんなのでちょっとぐらい僕の見解を話します。動的型付け言語である言語の特性の話ですが、型を意識してプログラムを書くというのは知識なしでは難しいと思います。 単にモノを作りたい、というだけであれば別に静的型付けに拘る必要はないですし、余計な難点が取り払われると考えることができます。 本物の初心者はエラーログを読めないことが多い[独自研究]のでそっちのほうが楽です。実はそんなに新しくないPythonはここ数年で[いつ?]急速に流行りだした言語ではありますが、Python 2.0(廃止済み)が2000年に、Python 3.0が2008年にリリースされています。 …いや言うて新しいやん、Go,Rust,Kotlinあたりと同じぐらいの時期やん、と思われるかもしれません。 が、それは言語としての話であって処理系としての話でいうとPython 3がだいぶ早いです。Go 1は2012年3月28日、Rust 1.0.0は2015年5月16日、Kotlin 1.0.0は2016年2月15日です。 対してCPython v3.0は2008年12月4日です。 まあ大幅な仕様変更が有ったとは言え、随分前からv2.xの処理系は有ったわけですから当然っちゃ当然ですね。 余談ですが、今は見る影もないCPython v1.0.1は1994年2月16日にリリースされました。Gitが生まれたのが2005年といえば相当昔なのがわかると思います。 利用者が多いという点も、情報が多いことに寄与していると思われます。 公式リファレンスも充実しています（もっとも、競プロだから公式リファレンスと多少のモジュールだけ見てれば十分という話ですが）。 競プロにおいてPythonが微妙な点遅い最大の欠点と言っても過言ではない。そう、このCPythonというインタプリタは普通に使うと遅いです。 それはもうとにかく遅い。ABC182-E の言語別実行時間分布 Rust はっや pic.twitter.com/mh6aXMAxNo— scol (@scol_kp) November 9, 2020 上記tweetの一番右が多分CPython 3だと思いますが、AC者滅茶苦茶少ないですよね。なぜかと言えば普通に書くと遅いから。 Python 3自体の使用者はかなり多いのですが（C++に次いで2番目[要出典]）、 ユーザーの大半はPyPyというCPythonとは別のインタプリタを使っています。 CPythonで動くコードをほとんどそのまんま動かせて、しかも早いのが素晴らしいところです。 AtCoderで未だにPyPy 7.3.0（Python 3.6）が使われているのが玉に瑕ですが、次の言語アップデートを気長に待ちましょう。Off-side Ruleサッカーの話ではなくて。ここでは、左端から離れる（off-side）規則のことです。インデントでブロックを表します。 対になる概念はCurly-bracket programming（中括弧でブロックを表す）。 Pythonという言語の設計思想は調べてもイマイチわかりませんが、 一つ言えそうなことは「プログラムが動くためには、美しく有るべき（SHOULD）。」ということです。動いてはならない（MUST NOT）、まで強くはないです。 ついでに、現在のPythonの言語仕様は PEP（Python Enhancement Proposal; Pythonをよりよくする提案）という提案を多数取り込むことで出来上がっています。 マージされたPEPの中でも最も有名なのはPEP8でしょう。 Pythonの生みの親であるGuido van Rossumを含む3人によって提案された、コードスタイルについての規則です。 その中では、インデントの推奨サイズ（半角スペース4個、2個でも8個でも、タブスペースでもない）や1行の推奨最大文字数まで指定されています。 それで、それの何が問題かと言えば、コードをコピペしたときにインデントが崩れたとして、それを自動で直すことができません。 コピペライブラリを貼り付ける場合にわざわざインデントを手動で直さなければならず、不便きわまりありません。 中括弧を使わなくともブロック末尾にendキーワードを置くRubyでは問題にならないのですが…… 本編お待たせしました。環境構築について話していきます。 例によって、#1 共通編を前提としますが、 使っているHeadless CMSサービスの都合上、<details> <summary>要素とかidによるページ内リンクが使えずごちゃごちゃしているので、 そのうち大幅改版してDockerfileでも作ることにします。乞うご期待。 正規表現でうまいこと置換すれば任意のHTML要素を置けるとかそういうことを言わない。 さて、Pythonの環境についてですが、一応CPythonとPyPy両方の説明をします。 速度的にはPyPyのほうが手抜きして高速化できるのですが、AtCoderのPyPyではNumPy等の便利なライブラリが使用できません。 CPythonで使えるライブラリはここのQiita記事に書いてありましたが、実際使えそうなのはNumPy、Numba、NetworkXぐらいでしょうか。SciPyも使える時があるのかな。 私は標準ライブラリしか使わないので基本PyPyです。PyPyUbuntuでPyPy3をインストールする方法は複数あります。aptを利用してUbuntu公式リポジトリのpypy3/focal 7.3.1+dfsg-4をインストールする公式で配布されているPyPy3 7.3.0のビルドをダウンロードするpypy.orgからPyPy3 7.3.0のソースをダウンロードしてビルドする手っ取り早い1と2の方法を紹介します（PyPyは公式でも自分でビルドすることは推奨されていないので）。方法1 apt install説明するまでもないような気がしますが。$ sudo apt install pypy3 $ pypy3 -Vはい。方法2 ビルド済みのPyPyをダウンロードこれもtarをダウンロードしてきて展開して適切な場所に配置するだけです。簡単ですね。$ sudo apt install wget $ cd /tmp $ wget https://downloads.python.org/pypy/pypy3.6-v7.3.0-linux64.tar.bz2 $ sudo tar vxjf pypy3.6-v7.3.0-linux64.tar.bz2 -C /usr/local/lib $ cd /usr/local/bin $ sudo ln -s ../lib/pypy3.6-v7.3.0-linux64/bin/pypy3 pypy3 $ pypy3 -VCPythonAtCoderで2021年11月現在採用されているCPythonのバージョンは3.8.2です。aptを利用してUbuntu公式リポジトリのpython3/focal,now 3.8.2-0ubuntu2をインストールするpython.orgからPython 3.8.2のソースをダウンロードしてビルドするとまあPyPyと概ね同じですが、Linux向けビルド済みパッケージを公式が配布していないので、 Ubuntuからの供給が絶たれれば自分でビルドする他なくなります。方法1 apt install$ sudo apt install python3 $ python3 -Vはい。方法2 ソースからビルドする時間がかかるのであんまりしたくありませんが、一応。$ cd /tmp $ sudo apt install wget xz-utils gcc make zlib1g-dev libssl-dev libbz2-dev libffi-dev $ wget https://www.python.org/ftp/python/3.8.2/Python-3.8.2.tar.xz $ tar vxJf Python-3.8.2.tar.xz $ ./configure --prefix="$HOME/.local" $ make $ make test $ sudo make install $ echo "PATH=$HOME/.local/bin:\$PATH" > ~/.bashrc && source ~/.bashrc $ python3 -VライブラリのインストールCPythonはいくつかライブラリが入っているという話をしたので、一応入れておきましょう。$ pip3 install networkx numba numpy scipy何も考えることはないですね。 こちらとしてはインストールに難儀しました。 ./configure時に--prefixオプションを指定しないと、make install時に/usr/local/binに書き込もうとするので権限がなく、sudo make installするとpip installがrootでしか使えませんでした。 また、libssl-devを入れないとそもそもpip installできないし、libbz2-devがないとNetworkXが、libffi-devがないとがNumbaとSciPyが使えませんでした。 これでお好きなようにPythonのコードを書くことができます。VSCodeの拡張機能PythonPylancepython-snippetsVisual Studio IntelliCodeあたりを入れとけばいいんじゃないですかね。知らんけど。

ガジェット/ハードウェア

ChromeSetup.exeをブラウザを使わずにダウンロードする

#ショート記事週間4本目（週とは） こんにちは。皆さんはWebブラウザは何を使っていますか？Google Chrome、Microsoft Edge、Mozilla Firefox、Safari等々…色々ありますが、まさか未だにInternet Explorerを使ってる人はいませんよね？？？？？？このサイトのAnalyticsを見ると今月4人（うち少なくとも2件は部室からのアクセス）もIEユーザーが訪問してることになってるんですが、こちらとしてはやめていただきたい（JavaScriptのエンジンが古い、レンダリングエンジンが古い）のでChromeに乗り換えろ（突然の無礼な命令形）。 未だにIEユーザーが居るせいでどれだけのエンジニアが苦労してると思ってるんだ 恥を知れ 人として大事な何かを取り戻せ もしIE以外が動かないとしてもIE以外のブラウザが動かないようなOSは（一般目的で）使うな 失礼、ちょっと熱くなり過ぎました 図1：終わりだよ さて、IEを使っている人はそのまま乗り換えてもらったらいいんですが、問題はMicrosoft Edgeです。別に今使っている人に強要はしませんが、絶対Google Chromeに乗り換えたほうがいいと思います。EdgeのエンジンはChromeと同じChromium/Blink/v8なんですが、EdgeはChromeの劣化版と言わざるを得ない程度には使いづらいので。 アンチWindows 10、アンチMicrosoft EdgeなWindows 10ユーザーの皆様のために、一度もEdgeを起動することなくChromeインストーラをダウンロードする方法をお教えします。 結論から言えば、PowerShellでInvoke-WebRequestを叩きます。問題はChromeのダウンロードリンクで、まあまあ複雑なJavaScriptが走って動いているので、生のURLを得るのはちょっと面倒でした。 開発者ツールのNetworkタブを開いた状態で普通にダウンロードリンクをクリックすると、次のようなリンクを得られました。 https://dl.google.com/tag/s/appguid%3D%7B8A69D345-D564-463C-AFF1-A69D9E530F96%7D%26iid%3D%7B463FFD83-EB1B-5C72-7FF9-50A229322B89%7D%26lang%3Dja%26browser%3D4%26usagestats%3D1%26appname%3DGoogle%2520Chrome%26needsadmin%3Dprefers%26ap%3Dx64-stable-statsdef_1%26installdataindex%3Dempty/update2/installers/ChromeSetup.exe しかしGUIDとか付いてるのを見るにちょっとダメそうな気がしますね。SHA-1とかのハッシュではないものの、アップデート来るたびにこのリンク使えなくなりそう で、次のリンクでも使える事がわかりました。 https://dl.google.com/tag/s/ap=x64-stable-statsdef_1/update2/installers/ChromeSetup.exe あとはInvoke-WebRequestを叩けば終わりです。 PowerShellで以下を実行すればユーザーのDownloadsフォルダに落ちます。cd "$env:USERPROFILE\Downloads" Invoke-WebRequest https://dl.google.com/tag/s/ap=x64-stable-statsdef_1/update2/installers/ChromeSetup.exe -OutFile ChromeSetup.exeこれでインストーラが落ちました。良かったね。

内容を見る

Unity

Unityでクソデカリバーシを作った日記なのにリバーシ要素があまりにも薄すぎる なんでやねん

初めてUnityを使いまして、習作としてリバーシを作りました。その名も「大は小を兼ねる クソデカリバーシ」です。 Unityroomで公開しています。https://unityroom.com/games/scalable-reversi さて、日記形式で開発記録を掘り返していきます。Gitのlogから記憶を呼び起こしているので捏造等あるかもしれません。 Unity未経験のプログラミング経験者目線での進捗なので、「はーこういう進め方もあるのかー」と参考にしてみてください。だからって一番最初にShaderに取り掛かるやついないと思うぞ1週目7/31（土）Affine変換（Wikipedia）を用いて一気に大量のコマを動かすことのできるリバーシを作ろうとUnityを触り始める（テスト前に何やってんだ） ちなみにこの頃はZ/8Zが体をなさない（乗法逆元を持たない元が存在する→複数のコマの座標を変換したとき同じ座標に移動することがある→409 Conflict）ことをどうしようか悩んでいた8/1（日）適当なサイトに書いてあるのをパクってShader Graphでグリッドを作った8/2（月）Input#GetKeyDown(KeyCode)とかTransform#positionとかSpriteRenderer#colorとかを使ってカーソルの移動を実装 この時点でキー操作はできるようになってて割とモチベが湧いた8/3（火）Prefabの概念を知る コマをPrefabをInstantiateすることで配置できるようになる8/4・5（水・木）開発おやすみ 多分水曜は英語の期末課題を片付けて、木曜は試験がなくなったので部室でシャニマスしてた8/6（金）なぜか急にリバーシが完成した はやい ちゃんと1weekじゃん もしかしたらcommitせずためてただけで木曜も開発してたのかも あとはスコアをリアルタイムに表示するUIを作成2週目8/7（土）おやすみ8/8（日）Cg/HLSL言語を使ってフラグメントシェーダを書く これによって盤面サイズが可変になった（ということは、Affine変換のアイデアはもう捨てている） ちなみにShader Graphでも変数使えるのであんまり書く意味なかったみたいですよ8/9（月）おやすみ8/10（火）ゲームプログラム側を可変サイズに対応させるのとタイトル画面の作成とSingletonパターンを覚えるのとSEの追加 TextMesh Proの存在を知る8/11（水）Sliderを動かすとリアルタイムに値が表示されるようにするなど8/12（木）TextMesh Proの導入によってGitHubの言語統計が滅茶苦茶になったのでgithub-linguistについて調べて除外する8/13（金）グリッド全体のサイズを調節して常にグリッドが正規直交正方形になるように これせんと斜めがめっちゃ見ずらいんですわ 盤面リセットとかも実装 Unityゲーム開発者ギルド（通称UGDG）に入る ワクチンの副反応で9時に寝る3週目8/14（土）Unityのコルーチンについてなんとなーく知る あとMaterialPropertyBlockを使うことでMaterialを直接編集しないように8/15（日）ちっさいリファクタリング8/16（月）おやすみ8/17（火）ツイートリンクを実装8/18（水）スクリーンショットの保存を実装（WebGL版はJavaScriptのblobを活用するなどしている（ソースコード）） C#の拡張メソッドの作り方を知る8/19・20・21（木・金・土）完全乱択のクソザコAIを実装（完成！） ちなみに3日かかったのは変数名を変えたときに1つ残してしまったせいでパス周りの実装がバグってたから感想本当は1,2週間で完成させるつもりだったのがだいぶ長引いてしまったけど、色々と身についたので悪くはない 来月のunity1weekに向けて頑張ります

内容を見る

プログラミング

Git hookを書こう！

#ショート記事週間（そんなものはない） 皆さん、開発にGitは使ってますか？使ってない人、使いましょう。使っている人も、hookという機能を使ったことがありますか？今日はGit hookの紹介をします。 hookとはGit hookというのは、各種gitコマンドを実行する前後のタイミングにおいて実行されるシェルスクリプトのことです。 リポジトリの .git/hooks/ に特定の名前のシェルスクリプトを置くことで実行されます。これを利用すれば、例えばcommitする直前に署名のメールアドレスを確認したりできるようになります。 例：commitする直前にメールアドレスを確認する（pre-commit）#!/bin/sh # hookはデフォルトでは標準入力を受け取れないのでターミナルから入力をリダイレクトする exec < /dev/tty echo "The author of this commit is to be $(git config user.name) <$(git config user.email)>." # readで入力待ちにする echo -n 'Press any key to continue...' read 小ネタこの記事の内容はこれぐらいのカスカスな記事なんですが、書いたhookが「自分のスイッチを切る装置」並に無駄（ここでは労力に対しての作用が少ないという意味）だったので紹介します。 具体的には、ファイル名末尾（拡張子）が .pdf .log .aux のいずれかがstagedであればそのままcommitするかどうかを尋ね、そのままcommitしない場合それを取り除いて（git restore --staged FILE）commitするというスクリプトです。 #!/bin/bash exec < /dev/tty SECRET=$(git diff --name-only --staged | grep -e '.pdf$' -e '.log$' -e '.aux$') if [ $? -eq 0 ]; then   echo 'Following files which should not be public are to be committed.'   echo -e "\e[31m${SECRET}\e[m"   echo -n 'Are you sure to commit them? [y/N]: '   read YN   case $YN in     [Yy]* ) exit 0 ;;     * ) ;;   esac   echo -n 'Do you want to omit them and commit? [Y/n]: '   read YN   case $YN in     [Nn]* ) echo 'Commit aborted.'       exit 1 ;;     * ) ;;   esac   git restore --staged $SECRET fi でもこれ、.gitignore に *.pdf$ *.log$ *.aux$ を指定すれば終いなんですよね……case文の勉強になったしまあいいか……

内容を見る

ガジェット/ハードウェア

呪われた（自分で呪った）フォルダを解呪した話

こんにちは。鮭です。 皆さんはWindowsでこれまで使えていたファイルやフォルダにアクセスできなくなってブチギレたことはありますか？ 私はあります。別にブチギレてはいませんが、先日以下のようなやりとりがありました。 呪いについて先輩：Dドライブに置いたOneDriveのフォルダを（管理者を含む）別のユーザーから見れへんようにしたいんやけど、どうしたらいい？ 私：多分プロパティ>セキュリティ>詳細設定から自分のユーザーにフルコントロール権限を付与して、Administratorsを全て拒否にすればいいんじゃないですかね？ 先輩：すごいそれっぽいみたいな感じでやったんですが、まさかのその先輩からもアクセス不可能になってしまいました（タイトルにもある「呪い」）。 何がいけなかったのでしょうか？ まあどう考えてもAdministratorsの権限を拒否してるからですね（とは言え、単に指定しない状態にしただけではAdministratorsならば権限を取得することが可能） なので、先輩の言ったようなことはWindowsのファイルシステムのみではおそらく実現できません。 まず呪いを解く 例のフォルダは70GBもあります。いくらDドライブが3TBあるからといって、解呪しないで放置するわけには行かないサイズ感なので、なんとかします。 さて、まずは状況を把握しましょう。 件のフォルダがどのようにして呪われたかというと、他人が所有権を持っているフォルダについて、自分のユーザーにフルコントロール権限を与え、UsersやAdministratorsから権限を剥がすとこうなってこうなってこうなります ウィザードにあるように、所有者を変更すればアクセスできるのですが、サブディレクトリにも拒否権限が引き継がれており、数百～数千個のファイルを手で相手するのは無理があります。 ACL関連のコマンドを利用 所有権とアクセス権が失われてしまった状態から復旧するのに役に立つコマンドがあります。 それが、 takeownとicaclsです。 百聞は一見に如かずといいますし、実際に使ってみましょう。 PS D:\> takeown /f "cursed-folder" /r /a 成功: ファイル (またはフォルダー): "D:\cursed-folder" は現在 Administrators グループによって所有されています。 成功: ファイル (またはフォルダー): "D:\cursed-folder\child" は現在 Administrators グループによって所有されています。 成功: ファイル (またはフォルダー): "D:\cursed-folder\child\grandchild" は現在 Administrators グループによって所有されています。 成功: ファイル (またはフォルダー): "D:\cursed-folder\child\grandchild\新しいテキスト ドキュメント.txt" は現在 Administrators グループ によって所有されています。 PS D:\> icacls "cursed-folder" /reset /t 処理ファイル: cursed-folder 処理ファイル: cursed-folder\child 処理ファイル: cursed-folder\child\grandchild 処理ファイル: cursed-folder\child\grandchild\新しいテキスト ドキュメント.txt 4 個のファイルが正常に処理されました。0 個のファイルを処理できませんでした 解説します。 takeownコマンドはファイルの所有権を特定のユーザーに与えるためのコマンドです。 /fオプションでファイルを指定し、/rオプションで再帰的に処理、 /aオプションで管理者（Administratorsグループ）に所有権を与えます。 これによって管理者がアクセス権を変更できるようになります。 icaclsコマンドはファイルのアクセス権を指定するためのコマンドです。 第一引数でファイルを指定し、/resetオプションでアクセス権をリセット（デフォルトの継承値にする）、/tオプションで再帰的に処理しています。 これによってアクセス権が元の状態に戻ります。 良かったね、これで元通りだよ。 当初の目的は 当初の目的は、「管理者を含む自分以外のユーザーからアクセスできないようにする」ことでした。 この手順はアクセス権をもとに戻すだけであって、目的は達成できていません。 ではどうすればいいかというと、EFS(Encrypted File System)を利用します。 ……部室のPC、Windows 10 Homeやから使えへんわ！！ ちなみにEFS（上図の「内容を暗号化してデータをセキュリティで保護する」）を使えば、ユーザーに紐付けされた秘密鍵を利用して復号するので、目的が達成できます。自宅のPCで試してみたところ、うまく管理者でもアクセスできないようになりました（特殊な方法を使えばどうか分かりませんが）。やはりWindowsはProを買えということだな ～終～ ちなみにOneDriveにはPersonal Vaultという機能がありますが、無料では3つまでしかファイルを追加できず、組織アカウントでは利用できません。 本当に終われ

内容を見る

プログラミング

4200000000Hzでゴリ押す！！！(1)

何でもかんでもアルゴリズムとマシンパワー（主にCPU）でゴリ押します。そういう企画です。 「AtCoder水下位競プロerである私ならこういう思考をするぞ」っていうのを書きます（個人の意見ですが）。 2021年 東京大学(理系) 数学 問4(4)初回は東大の入試問題をやります。この問題をパワーでゴリ押すのは \(O(1)\) 番煎じになりますが、気にしないことにします。 実はこれ春休みの帰省中に数人で集まって解いた問題の一つで、僕だけパワーで解決しようとしてました。 問題\({}_{2021}C_{37}\bmod 4\) を求めよ。 本来はいろいろと前置きがあって、それを利用して引数を落として計算するんですが、そんなの私には分かりません。 さて、この問題をどうやって解いてやりましょうか。 解法1\({}_{2021}C_{37}\) を求める で、問題は \({}_{2021}C_{37}\) がでかすぎることです。どの程度か簡単に見積もってみましょう。 $$ \begin{aligned}  {}_{2021}C_{37}  &=\frac{2021 \times \dots \times 1985}{37 \times \dots \times 1} \\  &>\left(\frac{1985}{37}\right)^{37} \\  &>2^{212.58} \end{aligned} $$ 困りました。これでは128ビット符号付き整数(→GCCの__int128、C++ Boostのint128_t、Rustのi128など)でも収まらず、直接計算するのは厳しいです。 十分な長さの固定長整数型や多倍長整数を利用すれば出来ないこともないので一応やってみましょう。 Pythonのint型は多倍長なので何食わぬ顔で書けば実装できます。 n = 2021 r = 37 MOD = 4 ans = 1 for i in range(min(r, n - r)):   ans = ans * (n - i) // (1 + i) print(f'{n}C{r} = {ans}') print(f'{n}C{r} % {MOD} = {ans % MOD}') 実行結果は次のようになりました。 2021C37 = 10549453167137272405699426118445044729600037976073052501105621045645733312800275 2021C37 % 4 = 3 な、成程……！ $${}_{2021}C_{37}=10549453167137272405699426118445044729600037976073052501105621045645733312800275$$ なんだ……！そして \(10549453167137272405699426118445044729600037976073052501105621045645733312800275\) を \(4\) で割ったあまりは \(3\) なんだ……！ 多倍長整数での \(N \times M\) および \(N / M\) \((N\gg M)\) が \(O(\log N \log\log N)\) で計算できる（例えばFFTとNewton-Raphson法で実装）という仮定のもとで、 この方法による \({}_{n}C_{r} (r \leq n/2)\) の計算量は大きめに見積もると、 $$ \begin{aligned}&  O(\log {}_{n}C_{1} \log\log {}_{n}C_{1})   + \dots + O(\log {}_{n}C_{r} \log\log {}_{n}C_{r}) \\  =& O(\log n \log\log n) + \dots + O(\log n^r \log\log n^r) \\  =& O(r^2 \log n \log\log n) \end{aligned} $$ となります（この評価は割とガバガバですが）。 解法2\({}_{n}C_{r}=\dfrac{{}_{n}P_{r}}{r!}\) とオイラーの定理を利用する \({}_{2021}C_{37} \bmod 4\) を計算しようと思ったらこの方法が一番に思いつきました。 オイラーの定理は、競技プログラミング界隈では常識であるところのフェルマーの小定理の一般化です。 この定理は次のようなものです。 \(m\) 以下の正の整数のうち \(m\) に互いに素であるものの個数を \(\varphi(m)\) とする（言い換えれば、\(\varphi(m)=|\{n ; \gcd(m,n)=1, 1 \leq n \leq m\}|\)）。 \(a\) と \(m\) が互いに素であるとき、 $$a^{\varphi(m)} \equiv 1 \pmod{m}$$ これの何が嬉しいって、分子 \(a\) と分母 \(b\) を \(\bmod m\) で別々に計算できるので、オーバーフローさせずに固定長整数型で計算できます。 そして分子に \(\bmod m\) における分母の逆元 \(b^{-1}\) を掛ける事によって求めることが出来ます。できるはずでした。 しかしよーく考えてみましょう。\({}_{2021}P_{37},37! \pmod{4}\) っていくつになるでしょうか？ ……そうです。\(0\) になります。\(0\) に何掛けたって \(4\) で割ったあまりが \(1\) になることはありません。 すなわち、\(b \equiv 0\) の逆元 \(b^{-1}\) なんてものは存在しないので、この方法は使えません。 \({}_{2021}C_{37} \bmod (10^9+7)\) であれば求められるんですけどね…… 解法2'ただこれを回避する方法があります。 $${}_{n}C_{r}=\frac{a}{b},a={}_{n}P_{r},b=r!$$ とします。ここで、 $$ \begin{aligned}  a &=2^{\alpha_0} \times 3^{\alpha_1}   \times 5^{\alpha_2} \times 7^{\alpha_3} \times \dots \\  b &=2^{\beta_0} \times 3^{\beta_1}   \times 5^{\beta_2} \times 7^{\beta_3} \times \dots \end{aligned} $$ のように素因数分解し、約分することで $$ {}_{n}C_{r}=\frac{a}{b} =2^{\alpha_0-\beta_0} \times 3^{\alpha_1-\beta_1}  \times 5^{\alpha_2-\beta_2} \times 7^{\alpha_3-\beta_3} \times \dots $$ として計算することができます（\({}_{n}C_{r}\) は整数であるから、任意の \(i\) について \(\alpha_i \geq \beta_i\) が成り立つ）。 実際にこれを実装してみました。 from collections import defaultdict n = 2021 r = 37 MOD = 4 spf = list(range(n + 1)) for i in range(2, n + 1):   if spf[i] != i:     continue   for j in range(i * 2, n + 1, i):     if spf[j] == j:       spf[j] = i pf = defaultdict(lambda:0) for i in range(min(r, n - r)):   m = n - i   while m > 1:     pf[spf[m]] += 1     m //= spf[m]   m = 1 + i   while m > 1:     pf[spf[m]] -= 1     m //= spf[m] ans = 1 for p, v in pf.items():   ans *= pow(p, v, MOD)   ans %= MOD print(f'{n}C{r} % {MOD} = {ans}') 結果は当然解法1と同じく3です。 各自然数を \(O(\sqrt{n})\) で素因数分解して全体 \(O(r \sqrt{n})\) で求める方法もありますが、\(r \fallingdotseq n/2\) の場合も想定して、エラトステネスの篩と同様の前計算 \(O(n \log\log n)\) でSPF（Smallest Prime Factor）配列を求め、一つの自然数の素因数分解は \(O(\log n)\) で、全体 \(O(n \log\log n + r \log n)\) でできるようにしました。 全体の計算量は、\(O(n \log\log n + r \log n)\) です。 東大の問題の場合 \(r\) が小さいので微妙ですが、\(r \fallingdotseq n/2\) の場合はこちらのほうが早そうです。 解法3パスカルの三角形を使う 今回の大本命です。 解法2では計算途中で \(4 \equiv 0\) で掛けたり割ったりするから計算できなかったのが悪いので、いっそのこと足し算だけで求めてしまおうという考え。 $$ {}_{n}C_{r}=\begin{cases}  0 &(n<r) \\  1 &(r=0) \\  {}_{n-1}C_{r} + {}_{n-1}C_{r-1} &(\text{otherwise}) \end{cases} $$ この漸化式を使えば解けます。軽く証明してみましょう。 $$ \begin{aligned}  {}_{n-1}C_{r} + {}_{n-1}C_{r-1}  &=\frac{(n-1)!}{(n-r-1)!r!}+\frac{(n-1)!}{(n-r)!(r-1)!} \\  &=\frac{n-r}{n-r}\frac{(n-1)!}{(n-r-1)!r!}   +\frac{r}{r}\frac{(n-1)!}{(n-r)!(r-1)!} \\  &=(n-r)\frac{(n-1)!}{(n-r)!r!}+r\frac{(n-1)!}{(n-r)!r!} \\  &=\frac{n!}{(n-r)!r!}={}_{n}C_{r} \\ \end{aligned} $$ ではこれを実装します。 実装1: 再帰関数 漸化式と言えば再帰ですよね。見たまんま実装できるので良いと思います。 n = 2021 r = 37 MOD = 4 def comb(n, r, mod):   if n < r:     return 0   elif r == 0:     return 1   else:     return (comb(n - 1, r, mod) + comb(n - 1, r - 1, mod)) % mod print(f'{n}C{r} % {MOD} = {comb(n, r, MOD)}') でもちょっと待ってください。これ、comb関数の呼び出し回数どうなると思います？ $$ \operatorname{call}(n,r)=\begin{cases}  1 &(n<r) \\  1 &(r=0) \\  \operatorname{call}(n-1,r) + \operatorname{call}(n-1,r-1) + 1 &(\text{otherwise}) \end{cases} $$ として定義した \(\operatorname{call}(n, r)\) 回になるんですよ。つまり少なくとも \({}_{n}C_{r}\) より大きい回数呼び出されます。 大きく見積もれば \(O(2^n)\)。\(n=2021\) で、実行していい計算量ではありません。 実装2: メモ化再帰 上の実装の問題点は、\({}_{n}C_{r}\) を計算するために、\({}_{n-x}C_{r-y}\) の計算を \({}_{x}C_{y}\) 回もしてしまっているということです。 ここで、メモ化という手法を取ることによって、各 \((x,y)\) に対して \({}_{n-x}C_{r-y}\) を \(1\) 回のみ計算すれば良いようにすることができます。 from sys import setrecursionlimit setrecursionlimit(3000) n = 2021 r = 37 MOD = 4 memo = [[None] * (r + 1) for _ in range(n + 1)] def comb(n, r, mod):   if n < r:     return 0   elif r == 0:     return 1   elif memo[n][r] != None:     return memo[n][r]   else:     memo[n][r] = (comb(n - 1, r, mod) + comb(n - 1, r - 1, mod)) % mod     return memo[n][r] print(f'{n}C{r} % {MOD} = {comb(n, r, MOD)}') コードを見ればそう難しい話ではないですね。単に二次元配列に計算済みの値を保存して、計算済みならば保存した値を返すようにしているだけです。 計算量は \(O(nr)\) ですが、空間計算量も \(O(nr)\) なのが痛いところです。 実装3: 動的計画法 動的計画法とは、問題を部分問題に分割し、自明な部分問題から遷移していって元の問題を解く手法です。 メモ化再帰もこれに含まれますが、単純再帰は含まれません（動的計画法の要件に計算結果の記録が含まれるため）。 ここでは、ボトムアップに（すなわち、自明な部分問題から順に）求める方法を指します。 パスカルの三角形の \(0\) 行目から \(n\) 行目まで順番に埋めていくイメージですね。 n = 2021 r = 37 MOD = 4 dp = [[0] * (r + 1) for _ in range(n + 1)] dp[0][0] = 1 for i in range(1, n + 1):   dp[i][0] = 1   for j in range(1, r + 1):     dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % MOD print(f'{n}C{r} % {MOD} = {dp[n][r]}') これもやはり \(O(nr)\) です。 実装3': SIMD 普通に順次計算すると1クロックで1命令で、計算が終わってまた1命令出すんですが、その1命令に複数のオペランドに対する同一の演算を詰め込むことができます。これがSIMDです。 ベクトルの足し算や内積などが一番よく利用されている例だと思います。 さて、PythonでもSIMDをすることができます。 Numpyというライブラリを利用することで、配列同士の和を取ったりでき、自動でSIMDを使うようになります。内部的に PADDB 命令とかを出してるんでしょうね。 import numpy as np n = 2021 r = 37 MOD = 4 dp = np.zeros((n + 1, r + 1), np.int8) dp[0, 0] = 1 for i in range(1, n + 1):   dp[i, 0] = 1   dp[i, 1:] = (dp[i - 1, 1:r + 1] + dp[i - 1, 0:r]) % MOD print(f'{n}C{r} % {MOD} = {dp[n, r]}') 定数倍の高速化なので、計算量は変わらず \(O(nr)\) です。なお、この条件 \((n,r)=(2021,37)\) だとこっちのほうが遅くなりましたが、\((n,r)=(20000,1000)\) とかにするとめちゃめちゃ高速化できます。 まとめ答えは \(3\) です。 \(n,r\) がともに大きくなった場合は解法2'が最も高速で、\(O(n \log\log n + r \log n)\) で解けます。 高速素因数分解は覚えとけ。

プログラミング

新歓企画・競プロ部門の裏話

こんにちは。色々右往左往しながら競プロ企画の実施に漕ぎ着けました。 コードゴルフ開催中OUCRCとしての新歓期間は終わりましたが、4月末までコードゴルフを実施中です。せっかく部室に来て競プロをしてくれた人もいたのに、その時点で問題を選べてなかったのは問題でしたが。 GitHub Pagesで公開中です。 バックエンドはFirebase Cloud Firestoreです。無料でクエリ数も多いDBサーバーが使えるとはいい時代になったなあ。 図1:matsu_friends氏しか解いていないLeaderboard 是非問題を解いて、短くコードが書けたら送ってください。私が喜びます。 ※参加にはAtCoderおよびyukicoderのアカウントが必要です。 ボツ案実のところコードゴルフをするつもりではなかったのです。自分で作問した問題をアルゴ形式で出題するつもりでした。 ジャッジサーバーを立てよう最初は部室内にジャッジサーバーを立ててやろうと思っていました。 OnlineJudge 2.0というサーバーシステムを青岛大学が公開しているのでこれを使うつもりでいました。 これを考えている段階では帰省していてノートPCで検証していたわけですが、こいつを導入するとDockerが壊れる壊れる。 さっぱり訳がわからないのでこれは見送られました。 碌なのがないなら自分で作ればいいじゃない次に考えたのが自分でJavaかNode.jsかなどを使ってサーバーごと作ること。しかし3日でそれはどう考えたって無理(出来たとしても実行言語があまり多く用意できない)なのでボツオブボツに過ぎませんでした。 幻のOUCRC Moodleその次にOUCRC Moodleを爆誕させること。部室内の余ってるPCをサーバーにしてなんとMoodleを立てようとしたわけです。これができれば部内ウケはバッチリだったことでしょう。 しかしMoodleが案外曲者で、依存環境をまとめてインストールするような方法は用意されていません。 LAMP環境(Linux-Apache-MySQL-PHPのアクロニム)が要求されるわけですが(Nginx信者の私はLEMP環境にしようとしましたが同じことです)、MySQLの導入で詰まってやめました。 最終的にで、結果的にGoogleスプレッドシートに問題をまとめて手動入力することに……紆余曲折ありすぎる。 この段階でゴルフ形式にすることを決めました。アルゴ形式だと時間による有利不利の差が開きすぎると思ったので、解けることを前提としてそこからどこまで短くできるかというゴルフ形式ならよいと考えました。 そして泣きっ面に蜂で正課外活動の自粛要請(要請なのか禁止なのかは知りませんが同じこと)。 その結果、ソビエトロシアではお粗末なフロントエンドがWWWを公開した、というのが事の顛末です。

内容を見る

プログラミング

競プロ環境構築#2 C/C++編

共通編の続きです。 WSLを導入したWindows10、またはMac OSやLinuxなどのUNIX系OSを前提にしています。 Ubuntuなどの仮想マシンが使えるならばこの限りではありません。 C++はどのような言語かC言語は説明するまでもないかと思うのでC++だけ。 C++は実行速度が速く、開発でも比較的よく使われる言語です。 イテレータや参照[1]によりポインタの操作がユーザーから秘匿されたり、クラスやテンプレートなどオブジェクト指向のパラダイムが持ち込まれたりして、C言語と比べて書きやすくなっています。 C言語との互換性が非常に高く、ポインタを直接操作することもでき、低級言語として扱うこともできます。 [1] int&型などのことです。関数にint*型で渡して関数内部で間接参照する、などとしなくても良くなっています。 2021年現在の競技プログラミング界隈では、事実上C++が標準語のようになっています。 AtCoderでは多くの言語を使うことができますが、他のコンテストサイトではあまり言語が多くなかったりします。 その中でもC++とJavaは標準的で、C++のほうが速いからか情報も多いです。 [独自研究?] そのため、競技プログラミングをするならC++は初心者におすすめの言語といえます。 C言語の環境構築もほぼ同じなので一緒に解説しますが、おまけ程度にしておきます。私は初心者がC言語を使うことはおすすめしません。 これはC言語しか習っていないうちの学生にも当てはまることなので、ぜひC++を使ってください。 一部の文法はC言語と似てるけど、便利機能モリモリで書きやすくて良いですよ。 はっきり言って、公式ガイドで環境構築できないくらいのスキルしか無いのであればC++に移行すべきだと思っています。 コンパイラ選びC++のコンパイラには主に以下の3つがあります。GCC(GNU C++ Compiler)ClangVisual C++GCCGNU Compiler Collectionの一部、GNU C++ Compiler。そのコマンド名g++からそのままg++と通称されます。 大抵のLinux OSは多くのGNUソフトウェアを標準インストールしており(GNU/Linuxの思想)、 GCC(ただしここではGNU C Compilerのこと)もそのうちに含まれています。 多くのLinuxユーザーはGNU C Compilerに馴染みがあるはずであり、GNU C++ Compilerはそれとほとんど同じオプションを利用することができます。 競プロer的に嬉しいのが、libstdc++のすべてのヘッダを読み込むbits/stdc++.hヘッダがあることです。 関数ごとにいちいちincludeディレクティブを書かなくていいことは記述速度最優先の競プロではプラスに働きます。 ただし実務で使うとブチ切れられることがあるらしいので気をつけてください。 多くの競プロerがGCCを使っており、なんやかんや一番おすすめです。ClangLLVMコンパイラ基盤の一部で、C、C++、Objective-C、Objective-C++の4言語のコンパイラ群です。 Macでは標準がClangらしいですね。他のことは何も知りません。 自分のPCにすでにClangが入っているか、GNUが嫌いでなければ特に使う理由はないと思います。VC++Microsoftが開発しているC++コンパイラですが、簡単に探した限りネイティブLinuxで使えるという情報は一切見つかりませんでした。当然ながらAtCoderでも対応はなし。その他Intel C++ CompilerやAMD Optimizing C++ Compiler、NVIDIA HPC SDK Compilersなどのプロセッサに最適化されたコンパイラ。当然競プロで使われることはまずない。 コンパイラのインストールWSL Ubuntu 20.04では必要ありません。gccもg++もGCC 9が標準搭載。やったぜ。 今後AtCoderで言語アップデートが入ってGCC 10になったときのためにインストール手順を書いておきます。 完璧にAtCoderと同じ環境にしたい場合はBoostが必要になりますが、私は使っていないのでここでは紹介しません。C++忙しい人向けsudo apt install g++-9複数バージョンの管理もしたい人向け# パッケージのインストール sudo apt install g++-9 # ここから蛇足 # シンボリックリンクの書き換え # 今回はalternativesというバージョン切り替えツールを利用する # g++が設定済みでないことをチェック update-alternatives --config g++ # update-alternatives: error: no alternatives for g++ # とか出ればOK # そうでないものが出たらそのままEnterを押す # g++にalternativesの設定を追加 # これをすると/usr/bin/g++ -> /etc/alternatives/g++ -> /usr/bin/g++-9のようなシンボリックリンクが張られる sudo update-alternatives --install /usr/bin/g++ g++ /usr/bin/g++-9 5 g++ --version # g++10をインストール sudo apt install g++-10 # 優先度10なので、こちらのほうが優先度が高くなる sudo update-alternatives --install /usr/bin/g++ g++ /usr/bin/g++-10 10 g++ --version # マニュアルモードでバージョンを戻しておく sudo update-alternatives --config g++C言語alternativesの部分はg++を全部gccに書き換えればいいだけなので省略します。sudo apt install gcc-9 コンパイラの使い方AtCoderのコンテストのルールのページを見ればコマンドが書いてあります。 https://atcoder.jp/contests/abc194/rules より引用。g++ -std=gnu++17 -Wall -Wextra -O2 -DONLINE_JUDGE -I/opt/boost/gcc/include -L/opt/boost/gcc/lib -I/opt/ac-library -o ./a.out ./Main.cppオプションの説明g++：コンパイラ本体です-std=gnu++17：C++のバージョンを指定します-Wall：標準的な警告をすべて出します-Wextra：その他の警告をいっぱい出します-O2：レベル2でコンパイル時最適化します-DONLINE_JUDGE：ちょっとややこしいので後述-I/opt/boost/gcc/include：Boostを#include<>の検索対象に含めます-L/opt/boost/gcc/lib：よくわからん-I/opt/ac-library：AtCoder Libraryを#include<>の検索対象に含めます-o ./a.out：出力ファイル名を./a.outにします./Main.cpp：入力ファイル名ですDオプション-DHOGE=FUGAは入力ファイルの先頭に#define HOGE FUGAとするのと同じ効果を持ちます。 FUGAが省略され-DHOGEと書かれた場合、#define HOGE "1"とするのと同じ効果を持ちます。 Includeガードでよくやるやつですね。 AtCoder Libraryを導入するAtCoder Libraryは AtCoderのジャッジで利用することができるオープンソースなC++ライブラリです (つまりC言語は対象外、移植は様々な言語にあります。 C言語版はここ。 アクティブなプロジェクトで、C++ STLのデータ構造(setやmap等)も移植対象とするようなので、 C言語使いの皆さん、是非プルリク出してあげてください)。 一般的な開発にはあまり使われない、しかし競技プログラミングでは重宝されるような機能が多数備わっています。 具体的にはmodintUnionFindSegtreeLazySegtreemaxflowmincostflowなどが含まれます(その他にも多数あります)。ダウンロードとインストールここのGitHubリポジトリからダウンロードしてきます。 zipファイルをダウンロードして解凍してもよいのですが、 WSL Ubuntuにはunzipはデフォルトで入っていないようなのでgit cloneでダウンロードすることにします。なぜgitはデフォルトで入ってるんだろう。使うからええんやけどさ# /opt下にダウンロード cd /opt sudo git clone https://github.com/atcoder/ac-library.git # インクルードできるかチェック g++ -I/opt/ac-library ./acl_include.cppacl_include.cppの中身#include <atcoder/all> int main() { return 0; }以上。 毎回-Iオプションを付けるのが面倒な方は、環境変数CPLUS_INCLUDE_PATHにパスを付け足せばよいです。 .bash_profileexport CPLUS_INCLUDE_PATH="$CPLUS_INCLUDE_PATH:/opt/ac-library" # .bash_profileを書くと.bashrcが読まれなくなるので、こっちから読み込むように指示 source ~/.bashrc適用できたか確認source ~/.bash_profile g++ acl_include.cpp エイリアスを設定する-Iオプションを付けるのが面倒な方は～、なんて言いましたが、どちらにせよ-std=gnu++17などのオプションはつけるべきです。 しかし面倒くさい。そのためのエイリアス。 .bash_aliasesにでも次のように付け足しましょうalias g++-ac='g++ -std=gnu++17 -Wall -Wextra -O2'とりあえずこれだけあれば十分かなと思いますが、好みに応じて増やしたり減らしたりしてください。 テンプレートの作成atcoder-cliのテンプレートに設定しておくとよいです。 私はこれで十分だと思っていますが、extgcdやdijkstraなど、ライブラリを付けたい方は付けてください。#include <bits/stdc++.h> #include <atcoder/all> using namespace std; // using namespace atcoder; using ll = long long; const ll MOD = 1000000007LL; // const ll MOD = 998244353LL; const vector<pair<int, int>> dpos4 = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}}; // const vector<pair<int, int>> dpos8 = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}}; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); return 0; } stdc++.hのプリコンパイルbits/stdc++.hを使うとコンパイル速度はかなり落ちます。 何度もテストする場合、それぞれの機能ごとに逐一includeしたほうが良いかもしれません。 少なくとも、手元環境で使う場合はプリコンパイルしておきましょう。# sudoをエイリアスで書き換えるというヤバいことをするので新しいシェルに入る bash # エイリアスの末尾がホワイトスペースのとき、次のトークンがエイリアスかチェックするらしい # g++-acエイリアスを使わない場合はこれをする必要はない # CPLUS_INCLUDE_PATHを設定済みの場合-Eオプション(環境変数を引き継ぐ)は必須 # 参考：https://qiita.com/homines22/items/ba1a6d03df85e65fc85a alias sudo='sudo -E ' # 本体部分 for header in `find /usr -type f -name 'stdc++.h'`; do sudo g++-ac $header done # 立ち上げたシェルから抜ける exit # PCHが生成されたことを確認 find /usr -type f -name 'stdc++.h.gch' 次回予告次回はPythonです。こちらで検証に成功すればnumbaの導入までやりたいですね。

プログラミング

競プロ環境構築#1 共通編

これから競プロを始めるWindows10ユーザーのための、快適な競プロ環境構築の方法をまとめます。LinuxでもOKです。多分Macも大丈夫。 以下に解説する方法はWindows10以外の非UNIX系OSには対応しませんが、仮想マシンを利用するか、ネイティブの対応するアプリケーションを利用すれば問題なく環境構築はできます。 記事情報記事作成日：2021-03-10最終更新日：2021-04-17 シリーズツリーここC/C++編Python編(予定)ご希望あれば他の言語やAtCoderの始め方など紹介します。筆者TwitterにDMかメンションをお願いします。 Windows10にWSL2を導入するWindows10にはWindows Subsystem for Linux(WSL)という便利な機能が備わっています。WSL2は本物のLinuxカーネルを使用することにより、ネイティブのLinuxと高い互換性を持ちます。 AtCoderのジャッジ環境も恐らくLinuxなので、なるべく環境を寄せるためにも導入します (2019/7からの言語アップデートの資料から、Ubuntu 18を使っているらしい。 GCCも10に更新されていないあたり、恐らく執筆時点では環境は変わっていない)。コンパイラなどの環境が既存の環境と競合すると面倒なので利用するという理由もあります。 具体的な導入方法はこのリンク先を見てもらったほうが早いです。 執筆中に初めて知ったんですが、Windows Insider Programに参加していればコマンド一つでインストールが完了するらしく驚き。 Windows10の不安定さにはイライラしているので、私は絶対参加したくないんですけど。今日もネットに繋がらなくてWindows Updateしたし導入手順以下の導入手順は前述のリンク先のx64マシン向けの要約です。詳細はリンク先を確認してください。また、この手順に従いいかなる損害等が発生しても、筆者は一切の責任を負いません。 WSL1をインストール済みの方も、WSL2にアップデートすることをおすすめします。「Linux 用 Windows サブシステム」機能を有効化する管理者としてPowerShellを起動し、次のコマンドを実行します。dism.exe /online /enable-feature /featurename:Microsoft-Windows-Subsystem-Linux /all /norestart作業が完了したら、再起動します。Windows10を更新するWin+Rキーを押して出てくるウィンドウにwinverと入力し、バージョンが1903より古ければアップデートします。「仮想マシン プラットフォーム」機能を有効化するPowerShellで次のコマンドを実行します。dism.exe /online /enable-feature /featurename:VirtualMachinePlatform /all /norestart作業が完了したら、再起動します。WSL2 Linuxカーネルを更新するここから最新の更新パッケージをダウンロードし、インストールします。WSLの標準バージョンを2に設定するPowerShellで次のコマンドを実行します。wsl --set-default-version 2LinuxディストリビューションをインストールするMicrosoft Storeから好きなディストリビューションを選びインストールします。今回は情報も多く、比較的新しいUbuntu 20.04 LTSをインストール。起動するスタートメニューから起動します。UNIXユーザー名とパスワードの設定が求められるので、設定します。 とりあえずこれでインストール完了です。Windows Terminalの導入は必須ではないので飛ばします(どうせVSCodeから叩くし)。テキストエディタを導入する競プロでは原則、すべてのプログラムはシングルファイルです。その都合上、「プロジェクトを管理する」スタイルのIDEとは相性が悪いです(勝手に連結してコンパイルしてしまったり、main関数が複数あって怒られたり)。 もちろんお好きなものを使っていただいて構わないんですが、おすすめはMicrosoftのVisual Studio Codeです。 拡張機能が充実していて、これ一つで大抵の言語に対応できます。私が普段使いしているのもこれです(「競プロ エディタ」でGoogle検索すると上位はVSCodeがほとんど)。余談ですが記事もこれで執筆しています。 これはWindows側にインストールすればOKです(むしろWSLはX Window Systemを自分でインストールしないと使えないのでWSL側にインストールして使うのは割と手間)。VSCodeを日本語化するVSCodeを起動して、Ctrl+Shift+Xを押して拡張機能の管理ペインを開きます。 「Japanese」で検索してJapanese Language Pack for Visual Studio Codeをインストールします。 ウィンドウ右下にメッセージが出るのでRestartをクリックして再起動します。VSCodeのターミナルからWSLを開くまず好きな場所に競プロのプロジェクト用のディレクトリを作ります。ここではWindows側のC:\kyoproにします。 これをVSCodeでワークスペースとして開きます(右クリックすると「Code で開く」というのがあると思うのでそれをクリック)。 Ctrl+Shift+@で統合ターミナルを開き、wslと入力してWSLを起動します。online-judge-toolsとatcoder-cliを導入するテストケースの一括取得、一括テスト、提出などができるようになります。それぞれPython/pipとNode.js/npmが必要。 WSLで次のコマンドを実行します。online-judge-toolsのインストールここに書いてあることを要約した。# パッケージリストをアップデート sudo apt update # Pythonを使う予定があればなるべくAtCoderのバージョンと同じものを # なければ最新でよい sudo apt install python3.8 python3-pip # Pythonとpipのインストールをチェック python3 -V pip3 -V pip3 install --upgrade pip pip3 install online-judge-tools # ojのインストールをチェック oj --versiononline-judge-toolsのバージョンが出れば成功。 パスが通っていないと怒られた場合は、find / -name oj 2> /dev/nullを実行してojの置かれている場所(実行ファイルの親ディレクトリのパス。筆者が試すと/home/[USERNAME]/.local/binであった)を確認した後、echo 'export PATH="/home/[USERNAME]/.local/bin:$PATH"' >> ~/.bashrcで~/.bashrcファイルに追記する。source ~/.bashrcで~/.bashrcを読み込み、再びojのバージョンを確認する(次回以降のWSL起動時はsourceを叩く必要はない)。atcoder-cliのインストール詳細はここ。WSLを利用する場合はLinux向けのガイドを読んでください。あちらではapt-getを使っていますが、aptのほうがいいらしいのでDebian/Ubuntu系ではaptに読み替えましょう。 npmチーム非推奨の方法 ！！！以下にある方法は非推奨なので更に下にあるほうを使ってください！！！sudo apt update # Node.jsとnpmをインストール sudo apt install nodejs npm # Node.jsとnpmのインストールをチェック node -v npm -v npm install -g npm npm install -g atcoder-cli # accのインストールをチェック acc -v2021-03-12追追記： この方法(apt)でnpmをインストールした場合、npm install -gにはやはりsudoが必要なようです(ちゃんと検証してから情報を世に出しなさい)。 そこで、npmチームはnvmのようなNodeバージョン管理ツールを利用することを推奨しています。[1] そんなわけで改めてNode.jsとnpmの導入方法を説明します。# 公式スクリプトでnvmをインストールする # 環境によってはwgetもインストールが必要 # curlを使ってもよい wget 'https://raw.githubusercontent.com/nvm-sh/nvm/master/install.sh' -O - | bash # nvmを環境変数に登録する # 上記スクリプトによって実はできているので # ~/.bashrcを再読込すればOK # シェルの再起動でもよい source ~/.bashrc # インストールのチェック nvm -v # nodeとnpmをインストールする nvm install node # インストールのチェック nvm ls node -v npm -vこれでそれぞれバージョンが出ればnvm、Node.js、npmのインストールは成功です。 [1] Downloading and installing Node.js and npm | npm Docs https://docs.npmjs.com/downloading-and-installing-node-js-and-npmWe strongly recommend using a Node version manager like nvm to install Node.js and npm.そしてatcoder-cliのインストールnpm install -g atcoder-cli acc -vatcoder-cliのバージョンが出れば成功。 2021-03-12追記： npmにsudoをつけていましたがどうもPowerShellの改行コードの問題だったらしく、LFならばsudoをつけなくても正しく実行できるようです。 色々と不便なのでGit for Windowsを導入して、"terminal.integrated.shell.windows": "C:/Program Files/Git/bin/bash.exe",と設定に書き加え、Git Bashを使えば良いかなと思います。 2021-03-12追追記： nvmでインストールすればなぜか解決されました。やったぜ。atcoder-cliの設定atcoder-cliを使えば自動でコンテストごとにディレクトリを生成して、テストケースをダウンロードしてくれるんですが、このディレクトリにテンプレートファイルを配置することもできます。ojと連携してコードテストしたり、書いたコードをAtCoderに提出できたりします。至れり尽くせりやでほんま。ojのパスを設定acc check-ojonline-judge-tools is available. と出力されればこの項は終了です。 online-judge-tools is not available.と出力された場合、find / -path "/mnt/c/*" -prune -o -name oj -print 2> /dev/nullでojの場所を探し(筆者の場合/home/[USERNAME]/.local/bin)、acc config oj-path /home/[USERNAME]/.local/bin/ojで登録します。再びacc check-ojでチェックして出れば成功です。テストケースの配置されるディレクトリ名を変更するojは指定がなければtest/ディレクトリに配置されたテストケースを認識しますが、なぜかaccはtests/ディレクトリにテストケースをダウンロードするので、このディレクトリ名を変更します。cd `acc config-dir`でconfig.jsonが配置されたディレクトリに移動します。 VimやEmacsなどの適当なテキストエディタでconfig.jsonを開き、該当行を次のように編集します。"default-test-dirname-format": "test"テンプレートを配置するcd `acc config-dir`でconfig.jsonが配置されたディレクトリに移動します。 ここにディレクトリを作成します。ディレクトリ名は言語名にすれば良いと思います。以下はC++の場合の例です。mkdir cpp移動して、テンプレートファイルを配置します。cd cpp touch main.cpp # main.cppを編集するaccに対してこれがテンプレートであることを伝えるため、template.jsonファイルを作成しますtouch template.json # template.jsonを編集する次のように書きます。当然ですが作成したファイル名に応じて適宜変えてください。{ "task": { "program": ["main.cpp"], "submit": "main.cpp" } }config.jsonが配置されたディレクトリにcd ..で戻り、該当行を作成したディレクトリ名に変更します。"default-template": "cpp"使ってみる言語に関係ない部分のインストール作業は大体終わりです。それではaccを実際に使ってみましょう。ディレクトリの生成とテストケースのダウンロード例えばABC088のD問題のテストケースをダウンロードするとします。acc new abc088上記のコマンドを入力するとログインが求められるので、AtCoderのユーザー情報を入力します。 次に上下キーとスペースキーを使って問題を選びます。選んだらEnterを押して待ちます。 完了したら、ディレクトリを開きます。ディレクトリ./abc088/dができているはずです。テンプレートを設定した場合、その中にテンプレートファイルがコピーされています。コードテストコードを書き終えたら、コードテストします。コンパイラ言語の場合コンパイラ言語の場合はコンパイルしてa.outファイルに書き出します。そして、oj tを実行すればコードテストが行われます。インタプリタ言語の場合a.outファイルを作れない場合、-cオプションをつけて実行します。ただし、標準入出力に対応している環境(Node.js等の場合は/dev/stdinを読み込める環境)でなければなりません。 例えばPython3でmain.pyをテストしたい場合はoj t -c 'python3 main.py'を実行します。その他のオプション問題によっては、絶対誤差または相対誤差が $10^{-6}$ 未満であれば正解とするといった場合があります。このような場合は-eオプションを指定します。上記の場合は、oj t -e 1E-6のようにします。もちろん-cオプションと組み合わせることも可能です。 他にもいくつかオプションがありますが、oj -hで確認できます。提出ojを使えばブラウザを使わずに問題を提出できます。さらに、accを経由すればURLの指定も不要です。ojへのログインojもAtCoderの認証を通す必要があります。oj login https://atcoder.jpを実行し、ユーザー名とパスワードを入力します。Seleniumをインストールしろと警告が出ますが無視しても構いません。accで提出accで生成された問題のディレクトリ(今回はabc088/d)に移動し、acc s main.pyのように提出するファイルを指定します。しばらく待つとAre you sure? Please type "abcd"のように表示されるので、提出してよければそのとおりに(abcdと入力して)、提出したくない場合はそのまま何も入力せずにReturnキーを押します。 本来はここでブラウザが起動して、ジャッジ結果を見られるのですが、私の環境はイカれてるらしく提出から7分も経ってやっとChromeに結果が出ました。アホか？ 2021-03-12追記： Ubuntuごとここに書いてる方法でインストールし直したら 割とすぐにブラウザが出るようになったので、気にしないでください。 まあ提出結果のページのURLはターミナルに出るので、 あまりに長いようならCtrl+Cで強制停止して、 URLをAlt+Clickで参照すればそれでよいと思います。エイリアスの設定(2021-03-14追記)コンテスト中にもoj tやacc sを使うわけですが、 acc sは3秒の待機と提出時の確認があり、 更に言語指定などが含まれてくると(Python3, Python2, PyPyなど)打つ時間だけ損してしまいます。 そこでエイリアスを設定して素早く打てるようにしておきます (昨日はその分時間ロスしてRated1000位を逃しました(半ギレ)。 あと9秒だけ早ければよかったのですが)oj test省略形がoj t。コードテストをします。 私が使っているのは以下。ただしエイリアスはあくまで文字列置換なので、ファイル名の指定は最後でないとできません。 故に、ファイル名も変数化したければ関数として実装する必要があります。alias oj-t-pypy="oj t -c 'pypy3 main.py'"acc submit省略形がacc s。AtCoderにコードを提出します。 私が使っているのは以下。ただしエイリアスはあくまで(ry ハイフン2個--で区切ると、それより左はacc sのオプション、右はoj sのオプションになります。 詳細はacc s --help及びoj s --helpで確認できます。alias acc-s-pypy='acc s main.py -- -l 4047 -w 0 -y'次回予告次回はC/C++の競プロ向け環境構築について説明します。乞うご期待。

プログラミング

初心者にこそ勧めたい競プロの世界

こんにちは。日々競技プログラミングの精進を重ねている、終に鮭といいます。 皆さん、プログラミングしてますか？あるいは興味がありますか？ ――結構。プログラミングを始めたい/上達したいという方々におすすめのコンテンツがあります。それが 競技プログラミング です。競技プログラミングとは競技プログラミングは、オンラインゲームです！ 1 2 3 4 5 これは割とマジなんですけど、もう少し真面目な説明をします。課題が与えられ、与えられた条件を満たすプログラムを書き、ソースコードをジャッジする、というものです。 解答を出すまでの速さを競ったり、多項式時間で解けない問題に対する近似精度を競ったり、コードの短さを競ったりします。AtCoderでは主に解答を出すまでの速さを競います(内々でコードゴルフしてる人もいたりするんですが、ここでは置いておく)。 で、オンラインゲーム要素なんですが、AtCoderではコンテストに出るとレーティングが付きます。Twitterで「青色になりました！」等と言いながら謎のグラフを上げてるアレです。 6 みんなアレをモチベに(ほんまか？)コンテストに参加してるんですね。なんならAtCoder Jobsで就活、インターン、バイトを有利に進められたりします。あくまで娯楽なんですけど。娯楽？プログラミングは娯楽ですよ。何言ってるんですか。……まあすべての人がそう思うわけではないんでしょうが。プログラミングを道具にパズルを解いてるみたいな感じで面白いんですけどね。競プロの強み娯楽に対してメリットを語りたくはないんですが、一応。アルゴリズムが身につく実装前から計算量がわかる 何よりもこれらですね。競プロをすると一般人(情報系学生等を除く)が一生学ぶことのないであろうアルゴリズムやデータ構造を学ぶ機会が得られます。いいですね。例えばDijkstra法とか、Segment Treeとか。大抵の人は普通にプログラミングしてても多分使わないでしょうし。 そして競プロにおいては計算量をオーダーで測ります。誤解されがちなのですが、(ほとんどの言語では)どこまでもチューニングして速くするわけではなく、定数倍の差は無視することがほとんどです。Pythonなんかはもとが遅すぎるので別ですが。 とにかく、プログラミングの抽象的な部分を深く学ぶことができます。みんなもアルゴリズムを勉強して、競プロをやろうね！ ---- 1 chokudai(高橋 直大)🍆さんはTwitterを使っています 「ちなみに今はインターネットに普通に繋がるのでAtCoderってオンラインゲームがおすすめです。」 / Twitter https://twitter.com/chokudai/status/1244638270736097284 2 こたつがめさんはTwitterを使っています 「steamサマーセールってほんと！？僕もAtCoderっていうオンラインゲーム毎日10時間やってます」 / Twitter https://twitter.com/kotatsugame_t/status/1143844015176990721 3 prd🦍さんはTwitterを使っています 「少し宣伝。 我々はAtCoderというオンラインゲームを普段やっています。完全無料！ ジャンルは競技プログラミングといって、いかに多くの問題にいかに早く正解できるかを競うゲームです。 プログラミングに興味がある人、力を試したい人、楽しく学びたい人、全てにおすすめです https://t.co/o0wpAOJKnR」 / Twitter https://twitter.com/prd_xxx/status/1044190250375888897 4 keymoonさんはTwitterを使っています 「基本無料オンラインゲームであるところのAtCoder」 / Twitter https://twitter.com/kymn_/status/1016531797792813056 5 kumakumaaaaaさんはTwitterを使っています 「趣味は競プロって言うと引かれることが多いので、競プロをバトルロイヤル形式のオンラインゲームと呼んでいる」 / Twitter https://twitter.com/kumakumaaaaa__/status/1338730125697814528 6 .終に鮭さんはTwitterを使っています 「入水しました！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！ https://t.co/HnHiZ2dkJg」 / Twitter https://twitter.com/AAAR_Salmon/status/1363125630049525763

内容を見る