取得に失敗しました

2020年度 入部

Twitter GitHub YouTube

終に鮭

自称・ヘビ使い

自己紹介

競プロをします。情報系2回生になります。一応副部長です。
好きなアルゴリズムは幅優先探索です。
C++からBrainf*ckまで幅広く触ったことがあります。現在は自称Pythonista。競プロはC++とPythonでやってます。

好きな/よく使う言語:C++、Python3、JavaScript、sh/Bash、sed
苦手/嫌いな言語:C、Visual Basic、LISP、Batch Script、PowerShell
覚えたい言語:Rust、awk、Go、Java、TeX

この人が書いた記事

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

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

こんにちは。鮭です。 皆さんは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つまでしかファイルを追加できず、組織アカウントでは利用できません。 本当に終われ

> 内容を見る

プログラミング Polygon
プログラミング

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)\) で解けます。 高速素因数分解は覚えとけ。

> 内容を見る

プログラミング Polygon
プログラミング

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

こんにちは。色々右往左往しながら競プロ企画の実施に漕ぎ着けました。 コードゴルフ開催中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を公開した、というのが事の顛末です。

> 内容を見る

プログラミング Polygon
プログラミング

競プロ環境構築#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の導入までやりたいですね。

> 内容を見る

プログラミング Polygon
プログラミング

競プロ環境構築#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++の競プロ向け環境構築について説明します。乞うご期待。

> 内容を見る

プログラミング Polygon
プログラミング

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

こんにちは。日々競技プログラミングの精進を重ねている、終に鮭といいます。 皆さん、プログラミングしてますか?あるいは興味がありますか? ――結構。プログラミングを始めたい/上達したいという方々におすすめのコンテンツがあります。それが 競技プログラミング です。競技プログラミングとは競技プログラミングは、オンラインゲームです! 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

> 内容を見る