2023-08-15

AtCoder新ジャッジにC言語で数学関数（libm）を使うためのおまじない

AtCoderの新ジャッジにおいて C言語のコンパイルオプション -lm がついておらず、数学関数(libm) を使う事が出来ません。（引数が定数の場合最適化によって使えてしまう事もあります）そこでこれらのコードを実行するために x87 をアセンブリから使う方法やlibmを動的ロードする方法が有志によって見つけられました。

qiita.com

x87 使うよりも libm を自力でロードして、使う分シンボル抜く方がやりやすいような気も。というか dlopen(3) の man https://t.co/qGcwDhIud3 の例にも当にそういうのあるし
※まあでも -lm をコンパイル時のリンクオプションとしてつけてもらう、が妥当とは思う。流石に厳し過ぎる。 https://t.co/pHEztwIgkV
— angel (as ㌵㌤の猫) (@angel_p_57) 2023年8月9日

そこで、これのうち libm の動的リロードをマクロにし、三行のスニペットにしました！ LOAD_LIBM マクロを追加すれば同様に追加することができます。また、これらの引数/戻り値が double 以外の関数を扱いたい場合やエラー処理をきちんとしたい人はよしなに書き換えてもらえるとありがたいです。良さげな改良がある場合は twitter などで教えてくれると喜びます(この記事からリンクを貼ったりしたいです)。

#include <dlfcn.h>
#define LOAD_LIBM(FUNC) double (*FUNC)(double);__attribute__((constructor))static void loadlibm_##FUNC(){FUNC=dlsym(dlopen("libm.so.6",RTLD_LAZY),#FUNC);}
LOAD_LIBM(sqrt); LOAD_LIBM(sin); LOAD_LIBM(cos);LOAD_LIBM(tan); LOAD_LIBM(atan2);

例

#include <dlfcn.h>
#define LOAD_LIBM(FUNC) double (*FUNC)(double);__attribute__((constructor))static void loadlibm_##FUNC(){FUNC=dlsym(dlopen("libm.so.6",RTLD_LAZY),#FUNC);}
LOAD_LIBM(sqrt); LOAD_LIBM(sin); LOAD_LIBM(cos);LOAD_LIBM(tan); LOAD_LIBM(atan2);

#include<stdio.h>

int main(){
  double a;
  scanf("%lf",&a);
  printf("sqrt(%lf) = %lf\n", a, sqrt(a));
  printf("sin(%lf) = %lf\n", a, sin(a));
  printf("cos(%lf) = %lf\n", a, cos(a));
  printf("atan2(%lf) = %lf\n", a, atan2(a));
}

sqrt(2.000000) = 1.414214
sin(2.000000) = 0.909297
cos(2.000000) = -0.416147
atan2(2.000000) = 1.365650

2023-01-04

Relaxed Convolution(Online FFT)によるexp/inv/log/sqrt/pow 【備忘録】

初めに

この記事ではあくまでも時間計算量のオーダーのみを考慮しているため、定数倍についての保証はありません。

relaxed convolutionとは

$\mathcal{O}(N\log ^2 N)$ で多項式の積を計算するオンラインアルゴリズムです。Online FFTと呼ばれる事もありますが、Relaxed Convolutionの方が使われていそうだったのでこちらで統一します。このアルゴリズムを使うことで形式的べき級数の $\exp$ / $\mathrm{inv}$ / $\log$ 等も出来ます。

relaxed convolution のやり方

Kiriさんのわかりやすい解説があったのでここでは割愛させて下さい qiita.com

www.sciencedirect.com

積分のやり方

$\int f dx$ の $N$ 項目は、 $f$ の $N-1$ 項目に $N$ をかけた物なので、一つ前の項を保存しておけば出来ます。

exp(f) のやり方

\begin{align} g=\exp(f) \end{align} とおくと、

\begin{align} gf'&=&f'\exp(f)\\ \int gf' dx &=&\exp(f)\\ &=&g \end{align} より、 $g$ の $N-1$ 項目までと、 $f'$ の $N-1$ 項目までをrelaxed convolutionにて掛け合わせる事で出来ます。

verify : https://judge.yosupo.jp/submission/119568

relaxed convolution を高々定数項だけずらす拡張

$f$ の $N-t$ 項目まで、 $g$ の $N-t$ 項目までをかけ合わせたものの $N$ 項目までを手に入れることが出来ます。 $f=f_0+f_1x^t$ ( $\mathrm{deg}(f_0) \lt t$ )、 $g=g_0+g_1x^t$ ( $\mathrm{deg}(g_0) \lt t$ ) とおくと、

\begin{align} fg=f_0g_0+(f_1g_0+f_0g_1)x^t+f_1g_1x^{2t} \end{align}

$f_0$ と $g_0$ に関しては高々定数項しかないため前半3項は愚直に計算しても計算量はボトルネックとなり得ません。また、 $N \geq t$ の場合、 $f$ の $N-t$ 項目は $f_1$ の $N-2t$ 項目であることから、 $f_1$ と $g_1$ をrelaxed convolutionで掛け合わせる事で $f_1g_1$ の $N-2t$ 項目まで手に入り、これにより $fg$ の $N$ 項目までを手に入れる事が出来ました。これは Kiriさんのブログの図の左上の $1 \times 1$ のマスを増やしたと考えると直感的に理解出来るかと思います。また、fとgの項数が高々定数個ずれる場合、小さい方に合わせてあげれば良いです。

inv のやり方

$g=1/f$ とおくと、 $fg-1=0$ であることから、 \begin{align} [x^N] fg = [x^N] (f \mod x^{N-1}) \times (g \mod x^{N-1}) + [x^0]f \times [x^N]g + [x^N]f \times [x^0]g \end{align} を前章の拡張を用いて計算する事で $g$ の $N$ 項目を求める事が出来ます。

verify : https://judge.yosupo.jp/submission/119569

log のやり方

$g=\log f$ とおくと、 $g=\int \frac{f'}{f} dx$ であることから前章までの内容を用いて計算することが出来ます。 (23/01/08/9:53 追記) $h=\frac{f}{g}$ とおくと $gh=f$ となり、これはinvとほぼ同様に処理出来るので一回のrelaxed convolutionで行う事も出来ます。

verify : https://judge.yosupo.jp/submission/119575

sqrt のやり方

$f$ の初項を非零に限定すると、 $g=\sqrt f$ とおくと、 $g^2=f$ であることから inv の章と同様に一つだけ項数をずらすことで出来ます。初項が零の時はそもそも $N$ 項目までの情報から $2N$ 項目までに非零が存在するかを知り得ないので定義から難しそうです。 (そもそも形式的冪級数のsqrtは定数項1を前提とするのが一般的という話もあります)

verify : TODO

pow のやり方

$f^M=\exp (M\log (f))$ を使えば出来ます。例の如く $\log$ の適用条件等に注意する必要があります。

verify : TODO

その他

分割統治法を用いたアルゴリズムとの併用など様々なアルゴリズムが考えられそうです。

2022-09-24

はてなリモートインターンシップ2022に参加しました

id:hotmanww です。2022/8/より三週間に渡って開催されていたはてなインターン2021に参加してきましたので、その参加記を書かせていただこうと思います。

応募と面接

選考に関しては Web から応募 → 書類審査 → 面接（オンライン）という流れで行われました。エントリーフォームを送って数日経つと、書類通過の旨を記したメールが届いていたため早速面接に。面接では最初にESの内容について話し、その後、自分の主に得意とする技術領域とはてなの扱う技術領域の差異についての話になりました。自信の得意とする技術領域はそれだけではそれを表現する文脈で弱みがあり、そういった部分を補完する為にはてなの技術領域に興味を抱いたという話をしました。

インターン第１週：講義パート前半

インターン第１週の前半は「Web API」「インフラ」「コンテナ」「マイクロサービス」「RDBMS（ブートキャンプ）」「kubanetes」「フロントエンド（ブートキャンプ）」「デザイン」の8項目の講座を受けさせていただきました。自分自身は講義内容がほぼ全て未習であったので、講義で沢山の内容を学べて凄く勉強になりました！！ scrapboxで他のメモを取りながら講義を聞いていたので、周りのインターン生のメモも見ていたのですが、わりと既知の知識の補強という形で講義パートを受けていた人が多かったようで不安になりつつも何とか食らいつこうと決意を固めていました。

インターン第１週：講義パート後半(共通課題)

講義パート第１週の後半ではインターン生全員に共通して与えられた課題に取り組みました、課題内容はブログサービスの雛形の様な物に記法を追加するという内容でした。言語は typescript/go-lang のどちらかを選べるという形で、自分はtypescript を用いて unified で実装を行うことにしました。 unified最新版がESM onlyだったため、CJSで作られた雛形からどう呼び出すかという所で詰まってしまい、バージョンダウンして進めるも納得の行くところまで進める事が出来ず、これをバネに開発パートを行おうと悔しい思いを抱えながら講義パートを終えました。

第１週最終日では開発パートの前に色々説明を頂く時間だったのですが、支給していただいていたMacのパスワードが書かれた紙を紛失していたことに気が付き、設定やXcodeのインストールで大変におまたせしてしまっていました。本当に申し訳ないです。

休日

支給していただいた Mac のセッティングをパスワードを紛失してしまっていた事から行えていなかったため、土日で行いました。最寄りの電気屋に向かいtype-C to type-A の変換ケーブル等のインターン中にあったら嬉しそうな物品を買い、自宅PCの周辺機器を外してMac に付け替えました。 LANをUSBに変換するアダプタのドライバが正式にはMac のmacOS Montereyに対応していない様で obel.hatenablog.jp ここ等を参考に手動でドライバを入れていました... その後、慣れないMac の操作感を改善するため以下のフリーソフトウェアを導入しました。

Rectangle: ウィンドウのスナップ機能を多用していたのでこれめっちゃ使えました。
Karabiner-Elements: windows の日本語キーボードを使用していたので全角半角キーを使えるようにする等の用途でこのソフトを使用していました。

インターン第２週: 開発パート

最初に練習がてら履歴の削除を行うUIのあたり判定の拡大という簡単な改善をさせて頂きました。この際にも、その後の課題とほぼ同様のフローを踏ませていただいたので概ねの進め方がわかりやすくありがたかったです。次に、実際に行う企画を決め実際にモックを作成し講談社の方にチェックを頂きました。この際に、漫画作者様の表現を損ねうる仕様になってしまっているのではないかという懸念点が上がっており、実際に講談社様においてもそちらの点を改善して欲しいという意向を頂いたので会議を重ね、改善に着手するために大幅に仕様を変更して改善を目指しました。また、金曜日に大学の成績発表があったのですが、大学のある科目について落とすはずがないと考えていた単位を落としていたことに気が付きました。教授に問い合わせて見たところ部分再履修にて履修するべき講義についてのすれ違いがあった事が判明し、何とか特別対応を頂けないかとのメールを送り、インターンの開発が佳境になっているのと合わせて不安な状態のまま一週間を終えました。

休日

日曜日にマジカルミライの公演を友達と観に行く予定だったので土曜日はその発券を行っていました。それ以外は何やっていたか覚えていませんでした...（多分寝ていた）そして日曜日の朝３時頃、たまたま起きてしまい、スマホを確認すると...加工学・実習Fの特別対応を行っていただけるとの連絡が来ていました！！ただし、当然受けていない３項目６レポートを履修する必要があり、明日からはまたインターンがバリバリ始まるという状態だったので、3~10時の間バリバリと課題を進め、その後幕張に向かいました。（実は昼公演と勘違いしてその時間で行ってた...）かなり疲れた状態でのマジカルミライだったので、企画展を回っている時にも少し目眩がして倒れなかったにせよ友達に迷惑をかけてしまった申し訳さとインターンと大学課題の兼ね合いでの不安で公演前はメンタルが終わってしまっていました... 公演で精神が回復し、逆に公演後の方が元気になってました！また、友達と夕食を食べ色々相談にのってもらって更にメンタルが回復しました！！ありがとう...ありがとう...

インターン第３週: 開発パート

懸念点がひたすらに湧いてくるのでそれを潰し続ける一週間という感じでした。最後の一日まで修正を重ねたのですが、結果的には概ね期待通りの動きはするが、少し怪しい挙動が残っているという状態で開発チームに引き継ぎという形で終わってしまいました。

振り返り

打ち合わせではアイデアや思ったことを出来る限り言語化して伝える様にしていました。様々なアイデアを出して仕様を固めるのは上手く行ったと思っているので良かったのではないかと思っています。一方で改善点としては、「一応思いついたもののデメリットが大きいのでそのままではおそらく採用するに足らない様なアイデア」を発言しようとした時にしどろもどろになってしまっていた点、そして、工数の見積もりに関して少し楽観的に考えすぎていたため想定外の自体に対応する時間が作れなかった事があったと思います。また、いよいよ佳境という所で大学の課題が入ってしまい、最大限のパフォーマンスで課題を行うことが出来ませんでした。こういった事に対処できるように余裕を持った計画を行えるようにし、また本課題をもっと余裕を持った計画で進められる様に技術の向上をしていきたいと思いました。

最後に

色々至らない所はありましたが、メンターさん、インターン運営の方々、マンガアプリチームの方々のお陰で全力を出して課題に打ち込む事が出来ました。本当にありがとうございます。

2022-02-01

お問い合わせ

2022-02-01

プライバシーポリシー

こんにちは管理人のhotman78です。下記、「プライバシーポリシー」に関して記載致しましたので、ご一読願います。

当サイトに掲載されている広告について

当サイトでは、第三者配信の広告サービス（Googleアドセンス）

を利用しています。このような広告配信事業者は、ユーザーの興味に応じた商品やサービスの広告を表示するため、当サイトや他サイトへのアクセスに関する情報『Cookie』(氏名、住所、メールアドレス、電話番号は含まれません) を使用することがあります。またGoogleアドセンスに関して、このプロセスの詳細やこのような情報が広告配信事業者に使用されないようにする方法については、こちらをクリックしてください。

当サイトが使用しているアクセス解析ツールについて

当サイトでは、Googleによるアクセス解析ツール「Googleアナリティクス」を利用しています。このGoogleアナリティクスはトラフィックデータの収集のためにCookieを使用しています。このトラフィックデータは匿名で収集されており、個人を特定するものではありません。

この機能はCookieを無効にすることで収集を拒否することが出来ますので、お使いのブラウザの設定をご確認ください。この規約に関して、詳しくはこちら、またはこちらをクリックしてください。

当サイトへのコメントについて

当サイトでは、スパム・荒らしへの対応として、コメントの際に使用されたIPアドレスを記録しています。

これはブログの標準機能としてサポートされている機能で、スパム・荒らしへの対応以外にこのIPアドレスを使用することはありません。

また、メールアドレスとURLの入力に関しては、任意となっております。

加えて、次の各号に掲げる内容を含むコメントは管理人の裁量によって承認せず、削除する事があります。

特定の自然人または法人を誹謗し、中傷するもの。極度にわいせつな内容を含むもの。禁制品の取引に関するものや、他者を害する行為の依頼など、法律によって禁止されている物品、行為の依頼や斡旋などに関するもの。その他、公序良俗に反し、または管理人によって承認すべきでないと認められるもの。免責事項当サイトで掲載している画像の著作権・肖像権等は各権利所有者に帰属致します。権利を侵害する目的ではございません。記事の内容や掲載画像等に問題がございましたら、各権利所有者様本人が直接メールでご連絡下さい。確認後、対応させて頂きます。

当サイトからリンクやバナーなどによって他のサイトに移動された場合、移動先サイトで提供される情報、サービス等について一切の責任を負いません。

2021-03-30

atcoderのjudgeの階層構造と調べ方

その他解説

はじめに

atcoderの階層構造は普段競技プログラミングをするに当たっては必要ありませんが、黒魔術をする時に使用することがあるのでまとめます

問題がある場合すぐに消します。

https://t.co/wuMDEeiJfh

Nim を利用して C++20 を使う例
— zer0-star (@0x_zer0star) June 14, 2020

aotamasaki.hatenablog.com

調べ方

bashのlsコマンドで調べます。treeコマンドとか使いたいのですがそんな物は無いので、 qiita.com で代用してます

ls /

下のディレクトリの中から使えそうなやつだけ紹介します他に使えそうな物があればhotman (@hotmanww) | Twitterまでお願いします

bin
boot
copyright
dev
etc
home
imojudge
lib
lib32
lib64
media
mnt
opt
proc
root
run
sbin
srv
sys
tmp
usr
var

/imojudge/sandbox

大体の言語はここで実行

/imojudge/sandbox
|  |--bash
|  |--bunzip2
|  |--bzcat
|  |--bzcmp
|  |--bzdiff
|  |--bzegrep
|  |--bzexe
|  |--bzfgrep
|  |--bzgrep
|  |--bzip2
|  |--bzip2recover
|  |--bzless
|  |--bzmore
|  |--cat
|  |--chgrp
|  |--chmod
|  |--chown
|  |--chvt
|  |--cp
|  |--cpio
|  |--dash
|  |--date
|  |--dd
|  |--df
|  |--dir
|  |--dmesg
|  |--dnsdomainname
|  |--domainname
|  |--dumpkeys
|  |--echo
|  |--egrep
|  |--false
|  |--fgconsole
|  |--fgrep
|  |--findmnt
|  |--fuser
|  |--grep
|  |--gunzip
|  |--gzexe
|  |--gzip
|  |--hostname
|  |--ip
|  |--journalctl
|  |--kbd_mode
|  |--kill
|  |--kmod
|  |--less
|  |--lessecho
|  |--lessfile
|  |--lesskey
|  |--lesspipe
|  |--ln
|  |--loadkeys
|  |--login
|  |--loginctl
|  |--ls
|  |--lsblk
|  |--lsmod
|  |--mkdir
|  |--mknod
|  |--mktemp
|  |--more
|  |--mountpoint
|  |--mt
|  |--mt-gnu
|  |--mv
|  |--nc
|  |--nc.openbsd
|  |--netcat
|  |--networkctl
|  |--nisdomainname
|  |--open
|  |--openvt
|  |--pidof
|  |--ping4
|  |--ping6
|  |--ps
|  |--pwd
|  |--rbash
|  |--readlink
|  |--rm
|  |--rmdir
|  |--run-parts
|  |--rzsh
|  |--sed
|  |--setfont
|  |--setupcon
|  |--sh
|  |--sh.distrib
|  |--sleep
|  |--ss
|  |--stty
|  |--sync
|  |--systemctl
|  |--systemd
|  |--systemd-ask-password
|  |--systemd-escape
|  |--systemd-hwdb
|  |--systemd-inhibit
|  |--systemd-machine-id-setup
|  |--systemd-notify
|  |--systemd-sysusers
|  |--systemd-tmpfiles
|  |--systemd-tty-ask-password-agent
|  |--tar
|  |--tempfile
|  |--touch
|  |--true
|  |--udevadm
|  |--ulockmgr_server
|  |--uname
|  |--uncompress
|  |--unicode_start
|  |--vdir
|  |--wdctl
|  |--which
|  |--whiptail
|  |--ypdomainname
|  |--zcat
|  |--zcmp
|  |--zdiff
|  |--zegrep
|  |--zfgrep
|  |--zforce
|  |--zgrep
|  |--zless
|  |--zmore
|  |--znew
|  |--zsh
|  |--zsh5

/imojudge/csharp

C#の実行環境

/imojudge/csharp
|--csharp.csproj
|--obj
|  |--csharp.csproj.nuget.dgspec.json
|  |--csharp.csproj.nuget.g.props
|  |--csharp.csproj.nuget.g.targets
|  |--project.assets.json
|  |--project.nuget.cache
|--Program.cs

/imojudge/fsharp

F#の実行環境

/imojudge/fsharp
|--fsharp.fsproj
|--obj
|  |--fsharp.fsproj.nuget.dgspec.json
|  |--fsharp.fsproj.nuget.g.props
|  |--fsharp.fsproj.nuget.g.targets
|  |--project.assets.json
|  |--project.nuget.cache
|--Program.fs

/imojudge/rust

rustの実行環境いっぱいだぁ

/imojudge/rust
|--Cargo.lock
|--Cargo.toml
|--src
|  |--main.rs
|--target
|  |--release
|  |  |--build
|  |  |  |--getrandom-8adbef0e58e29ab1
|  |  |  |  |--invoked.timestamp
|  |  |  |  |--out
|  |  |  |  |--output
|  |  |  |  |--root-output
|  |  |  |  |--stderr
|  |  |  |--getrandom-ee8d950eddb16ff2
|  |  |  |  |--build-script-build
|  |  |  |  |--build_script_build-ee8d950eddb16ff2
|  |  |  |  |--build_script_build-ee8d950eddb16ff2.d
|  |  |  |--im-rc-42fdf6419bd3d574
|  |  |  |  |--build-script-build
|  |  |  |  |--build_script_build-42fdf6419bd3d574
|  |  |  |  |--build_script_build-42fdf6419bd3d574.d
|  |  |  |--im-rc-c693654aec670260
|  |  |  |  |--invoked.timestamp
|  |  |  |  |--out
|  |  |  |  |--output
|  |  |  |  |--root-output
|  |  |  |  |--stderr
|  |  |  |--indexmap-67a39c2f11f9dfe8
|  |  |  |  |--invoked.timestamp
|  |  |  |  |--out
|  |  |  |  |  |--probe0.ll
|  |  |  |  |  |--probe1.ll
|  |  |  |  |--output
|  |  |  |  |--root-output
|  |  |  |  |--stderr
|  |  |  |--indexmap-72d0cd8fb60a4f2c
|  |  |  |  |--build-script-build
|  |  |  |  |--build_script_build-72d0cd8fb60a4f2c
|  |  |  |  |--build_script_build-72d0cd8fb60a4f2c.d
|  |  |  |--libc-6dfa91a335830f72
|  |  |  |  |--invoked.timestamp
|  |  |  |  |--out
|  |  |  |  |--output
|  |  |  |  |--root-output
|  |  |  |  |--stderr
|  |  |  |--libc-c67abeb73b11d80f
|  |  |  |  |--build-script-build
|  |  |  |  |--build_script_build-c67abeb73b11d80f
|  |  |  |  |--build_script_build-c67abeb73b11d80f.d
|  |  |  |--libm-046970b86b9acfa4
|  |  |  |  |--build-script-build
|  |  |  |  |--build_script_build-046970b86b9acfa4
|  |  |  |  |--build_script_build-046970b86b9acfa4.d
|  |  |  |--libm-9b1cabcb7828f223
|  |  |  |  |--invoked.timestamp
|  |  |  |  |--out
|  |  |  |  |--output
|  |  |  |  |--root-output
|  |  |  |  |--stderr
|  |  |  |--memchr-12f87ccc7f9931a7
|  |  |  |  |--build-script-build
|  |  |  |  |--build_script_build-12f87ccc7f9931a7
|  |  |  |  |--build_script_build-12f87ccc7f9931a7.d
|  |  |  |-...

/imojudge/visualbasic

visualbasicの実行環境

/imojudge/visualbasic
|--obj
|  |--project.assets.json
|  |--project.nuget.cache
|  |--visualbasic.vbproj.nuget.dgspec.json
|  |--visualbasic.vbproj.nuget.g.props
|  |--visualbasic.vbproj.nuget.g.targets
|--Program.vb
|--visualbasic.vbproj

/bin

色々なコマンドがある

/bin
|--bash
|--bunzip2
|--bzcat
|--bzcmp
|--bzdiff
|--bzegrep
|--bzexe
|--bzfgrep
|--bzgrep
|--bzip2
|--bzip2recover
|--bzless
|--bzmore
|--cat
|--chgrp
|--chmod
|--chown
|--chvt
|--cp
|--cpio
|--dash
|--date
|--dd
|--df
|--dir
|--dmesg
|--dnsdomainname
|--domainname
|--dumpkeys
|--echo
|--egrep
|--false
|--fgconsole
|--fgrep
|--findmnt
|--fuser
|--grep
|--gunzip
|--gzexe
|--gzip
|--hostname
|--ip
|--journalctl
|--kbd_mode
|--kill
|--kmod
|--less
|--lessecho
|--lessfile
|--lesskey
|--lesspipe
|--ln
|--loadkeys
|--login
|--loginctl
|--ls
|--lsblk
|--lsmod
|--mkdir
|--mknod
|--mktemp
|--more
|--mountpoint
|--mt
|--mt-gnu
|--mv
|--nc
|--nc.openbsd
|--netcat
|--networkctl
|--nisdomainname
|--open
|--openvt
|--pidof
|--ping4
|--ping6
|--ps
|--pwd
|--rbash
|--readlink
|--rm
|--rmdir
|--run-parts
|--rzsh
|--sed
|--setfont
|--setupcon
|--sh
|--sh.distrib
|--sleep
|--ss
|--stty
|--sync
|--systemctl
|--systemd
|--systemd-ask-password
|--systemd-escape
|--systemd-hwdb
|--systemd-inhibit
|--systemd-machine-id-setup
|--systemd-notify
|--systemd-sysusers
|--systemd-tmpfiles
|--systemd-tty-ask-password-agent
|--tar
|--tempfile
|--touch
|--true
|--udevadm
|--ulockmgr_server
|--uname
|--uncompress
|--unicode_start
|--vdir
|--wdctl
|--which
|--whiptail
|--ypdomainname
|--zcat
|--zcmp
|--zdiff
|--zegrep
|--zfgrep
|--zforce
|--zgrep
|--zless
|--zmore
|--znew
|--zsh
|--zsh5

/dev

入出力等が入ってるっぽい

atcoderさん、ここに想定解おいてみてはいかがですか？

/dev
|--fd
|--full
|--null
|--random
|--stderr
|--stdin
|--stdout
|--tty
|--urandom
|--zero

/etc

コンパイルコマンドが入ってるみたいかなり重要？

/etc
|--adduser.conf
|--alternatives
|  |--aclocal
|  |--aclocal.1.gz
|  |--appletviewer
|  |--appletviewer.1.gz
|  |--assembly-linker
|  |--automake
|  |--automake.1.gz
|  |--awk
|  |--awk.1.gz
|  |--bin2obj
|  |--bin2obj.1.gz
|  |--builtins.7.gz
|  |--c++
|  |--c++.1.gz
|  |--c89
|  |--c89.1.gz
|  |--c99
|  |--c99.1.gz
|  |--cc
|  |--cc.1.gz
|  |--chmcmd
|  |--chmcmd.1.gz
|  |--chmls
|  |--chmls.1.gz
|  |--clang
|  |--clang++
|  |--clhsdb
|  |--cli
|  |--cli.1.gz
|  |--cli-al.1.gz
|  |--cli-csc.1.gz
|  |--cli-gacutil.1.gz
|  |--cli-resgen.1.gz
|  |--cli-sn.1.gz
|  |--cpp
|  |--c-sharp-compiler
|  |--data2inc
|  |--data2inc.1.gz
|  |--delp
|  |--delp.1.gz
|  |--editor
|  |--editor.1.gz
|  |--editor.da.1.gz
|  |--editor.de.1.gz
|  |--editor.fr.1.gz
|  |--editor.it.1.gz
|  |--editor.ja.1.gz
|  |--editor.pl.1.gz
|  |--editor.ru.1.gz
|  |--ex
|  |--ex.1.gz
|  |--ex.da.1.gz
|  |--ex.de.1.gz
|  |--ex.fr.1.gz
|  |--ex.it.1.gz
|  |--ex.ja.1.gz
|  |--ex.pl.1.gz
|  |--ex.ru.1.gz
|  |--extcheck
|  |--extcheck.1.gz
|  |--faked.1.gz
|  |--faked.es.1.gz
|  |--faked.fr.1.gz
|  |--faked.sv.1.gz
|  |--fakeroot
|  |--fakeroot.1.gz
|  |--fakeroot.es.1.gz
|  |--fakeroot.fr.1.gz
|  |--fakeroot.sv.1.gz
|  |--fp
|  |--fpc
|  |--fpc.1.gz
|  |--fpc.cfg
|  |--fpc-depends
|  |--fpc-depends.1.gz
|  |--fpclasschart
|  |--fpclasschart.1.gz
|  |--fpcmake
|  |--fpcmake.1.gz
|  |--fpcmake.5.gz
|  |--fpcres
|  |--fpcres.1.gz
|  |--fpcsubst
|  |--fpcsubst.1.gz
|  |--fpdoc
|  |--fpdoc.1.gz
|  |--fplexyacc
|  |--fppkg
|  |--fppkg.1.gz
|  |--fprcp
|  |--fprcp.1.gz
|  |--fp-utils
|  |--from
|  |--from.1.gz
|  |--g++
|  |--gcc
|  |--gdc
|  |--gfortran
|  |--global-assembly-cache-tool
|  |--gnustep-back-026
|  |--grab_vcsa
|  |--h2pas
|  |--h2pas.1.gz
|  |--h2paspp
|  |--h2paspp.1.gz
|  |--hsdb
|  |--idlj
|  |--idlj.1.gz
|  |--ifpc
|  |--ifpc.1.gz
|  |--instantfpc
|  |--instantfpc.1.gz
|  |--jaotc
|  |--jar
|  |--jar.1.gz
|  |--jarsigner
|  |--jarsigner.1.gz
|  |--java
|  |--java.1.gz
|  |--javac
|  |--javac.1.gz
|  |--javadoc
|  |--javadoc.1.gz
|  |--...

/opt

ac-library,boost,haxelib,rakudo-pkgが入ってる

/opt
|--ac-library
|  |--atcoder
|  |  |--all
|  |  |--convolution
|  |  |--convolution.hpp
|  |  |--dsu
|  |  |--dsu.hpp
|  |  |--fenwicktree
|  |  |--fenwicktree.hpp
|  |  |--internal_bit
|  |  |--internal_bit.hpp
|  |  |--internal_math
|  |  |--internal_math.hpp
|  |  |--internal_queue
|  |  |--internal_queue.hpp
|  |  |--internal_scc
|  |  |--internal_scc.hpp
|  |  |--internal_type_traits
|  |  |--internal_type_traits.hpp
|  |  |--lazysegtree
|  |  |--lazysegtree.hpp
|  |  |--LICENSE
|  |  |--math
|  |  |--math.hpp
|  |  |--maxflow
|  |  |--maxflow.hpp
|  |  |--mincostflow
|  |  |--mincostflow.hpp
|  |  |--modint
|  |  |--modint.hpp
|  |  |--scc
|  |  |--scc.hpp
|  |  |--segtree
|  |  |--segtree.hpp
|  |  |--string
|  |  |--string.hpp
|  |  |--twosat
|  |  |--twosat.hpp
|  |--document_en
|  |  |--appendix.html
|  |  |--convolution.html
|  |  |--dsu.html
|  |  |--fenwicktree.html
|  |  |--index.html
|  |  |--lazysegtree.html
|  |  |--math.html
|  |  |--maxflow.html
|  |  |--mincostflow.html
|  |  |--modint.html
|  |  |--scc.html
|  |  |--segtree.html
|  |  |--string.html
|  |  |--twosat.html
|  |--document_ja
|  |  |--appendix.html
|  |  |--convolution.html
|  |  |--dsu.html
|  |  |--fenwicktree.html
|  |  |--index.html
|  |  |--lazysegtree.html
|  |  |--math.html
|  |  |--maxflow.html
|  |  |--mincostflow.html
|  |  |--modint.html
|  |  |--scc.html
|  |  |--segtree.html
|  |  |--string.html
|  |  |--twosat.html
|  |--expander.py
|--boost
|  |--clang
|  |  |--include
|  |  |  |--boost
|  |  |  |  |--accumulators
|  |  |  |  |  |--accumulators_fwd.hpp
|  |  |  |  |  |--accumulators.hpp
|  |  |  |  |  |--framework
|  |  |  |  |  |  |--accumulator_base.hpp
|  |  |  |  |  |  |--accumulator_concept.hpp
|  |  |  |  |  |  |--accumulators
|  |  |  |  |  |  |  |--droppable_accumulator.hpp
|  |  |  |  |  |  |--accumulator_set.hpp
|  |  |  |  |  |  |  |--external_accumulator.hpp
|  |  |  |  |  |  |  |--reference_accumulator.hpp
|  |  |  |  |  |  |  |--value_accumulator.hpp
|  |  |  |  |  |  |--depends_on.hpp
|  |  |  |  ...

終わり

手抜きですごめんなさい

2021-01-26

【競技プログラミング】1~2K+1の順列2つの和でK+2~3K+2の順列が作れる話

テクニック解説

ICPC海外リージョナルとかyukicoderとかatcoderで見たことある気がする(問題はatcoderのNon-triangular Triplets位しか思い出せない)

1,2,3,4,5
+
5,3,1,4,2
=
6,5,4,8,7

1,2,3,4,5,6,7
+
7,5,3,1,6,4,2
=
8,7,6,5,4,11,10,9

一般化は

1,2,3,...,2K+1
2K+1,2K-1,2K-3,...,1,2K,2K-2,...,2

2ずつ減らしていくイメージ

例

初めに