ICPC Asia Pacific Championship 2024 準備期

オープニングセレモニーのUETのパフォーマンスはUETの学生さんたちがやっていたらしいです。活力を感じます。

色々と問題準備を手伝っていました。自分が原案だった問題の記録を書きます。

C問題 (Bit Count Sequence)

昔作ってボツにしていた問題を取り出してできた問題です。 規則によって生成される巨大な数列の中に、入力から与えられる数列が連続した部分列として何個出るか求めるような問題を作りたいと思っていました。 類題として FizzBuzz の出力を連結したときに特定の部分文字列が何個あるか求める問題がどこかにありましたが、そんなノリです。

規則性のある列としてはなんでもよかったのですが popcount なんかいいんじゃないかなぁと思ってそれっぽく作りました。元々は数え上げの問題のつもりだったのですが冷静に考えると想定解がおかしい事に気づいたのでやむをえず最小値を求める問題に変えました。 問題文を整理していると最初のアイデアの根本にあった「巨大な数列」というのは消滅して、単に自然数を求めるだけの問題になりました。

様々な解法がありえる問題で、解説に書いたもの以外にも2つ異なる解法があることをコンテスト前から知ってました。 想定以上に誤答が多く、かつ落ちているケースも選手によってだいぶバラバラという、あまり見かけない状態になりました。

E問題 (Duplicates)

大昔に作ってボツにしていたところから引っ張ってきました。何を思って作ったのかあまり記憶がありません。当初は構築要素なしで、最小値だけ求める問題のつもりでした。

今回 Championship で出題するに当たって、最小値だけだと無証明で突撃できちゃうからちょっと微妙だなと思って構築要素をつけました。 方針次第ですが想像以上に難しくなったので直前になってサンプルを拡充させたりしていました。

I問題 (Symmetric Boundary)

これも大昔に作ってボツにした問題を引っ張ってきてリメイクしたものです。 当初は「点対称」という条件付けはなく、単に与えられた点を境界に持つ凸集合としてありうる最小面積を求めるだけの問題でした。 なんかかっこいいつもりの想定解があるつもりだったのですが、この設定だとかなり微妙なことになることに真面目に考え出してから気づき、この設定のままだと出題できないなぁとなりました。(理由は自明ではないですが書くのも面倒なので考えてみてください)

でも設定が個人的に好みだったのでどうにか復活させられないかとかなり試行錯誤して「点対称」な領域に限定するとまぁまぁいい感じの解法が生えることに気づいて、それを問題案として完成させました。

アルゴリズム自体は割とシンプルですが凸包を取るところで普段あまりやらないようなことを求められる(同一直線上に乗っている点も残して凸包を取ったりしないといけない)ので実装は見た目よりだいぶ罠があるんじゃないかなぁと思っています。 提出までたどりついたチームがいなかったのは少し寂しかったですが、考察自体もそんなに自明ではないはずなのでやむを得なしとも思います。

G問題

改題の提案とテストケース作成をしました。強いテストケース作るのが地味に難しかったです。

D問題, L問題

解説を書きました。包除原理も線形代数も難しい。

全体

とにかく初開催ということで参加者のレベル感がまるで掴めないので難易度調整とかまるでわからんと思いながらやっていました。 少なくとも日本大会でいうとトップ15位くらいが集まっているのでだいぶレベルは高そうで、かつ他のリージョンとかチラ見してもレベルが低い感じは全然ないように思っていました。 どちらかというとちょっと難しすぎるんじゃないかと感じるくらいがちょうどいいんじゃないかと思って自分は進めていた気がします。

開催前にチーム HoMaMaOvO の皆様から有益なフィードバックをもらえて非常に助かりました。

今回は環太平洋のアジアの国々の人たちが集まるグローバルなチームで問題セットを作り上げました。 この手の経験は個人的に久しぶりだったので良い刺激になりました。英文校正は chatgpt にかなり頼りました。

競プロの問題をいつものように準備してるだけだとなんか物足りないなぁと思って途中から kotlin を使って想定解を書いたりしていました。 書いてて楽しい言語なのがわかってよかったです。

今回は偶然にも自分の有給消化期間とコンテストの準備期間が被っていたのでかなりコンテストの準備に時間を割けました。 来年以降は… 個人的にはヒューマンリソースが欲しいところではあります。。

価値

「僕はいま自分が取り組んでいることの価値がよくわからないのです。」

昔とあるプロジェクトにいた時、社内のとある方にこういった相談をしたことがある。そのとき頂いた答えは(実際のものとはあえて違う書き方をするが)こういう感じのものだった。仮に何かに取り組んで結果が肯定的なものでなかったとしてもそれはその仮説が良くないことを示唆するという価値を産んでいる。その結果はまた違う仮説を産むものにつながるかもしれない。また、もしビジネスっぽい領域について知りたいのなら、ビジネススクールの初級向けのカリキュラムなどを取ってみるのは有りかもしれない。など。

後者についてはなるほど色々知らないことがあるなぁと思い、それから少し社会勉強のようなことをした。マーケティングや経営の基礎的な話や、実務的なレイヤーになるがロジカルに課題を洗い出して受け手に納得してもらえるような形で伝える手法論などを学んだ。これらは今でも自分の中で活きていることがあるように思う。

しかし今振り返ると自分が知りたかったのはそういうことではなかったはずである。僕は単に、自分の成したことが世の中から無視されたくなかったのだと思う。僕は数理的に物事を考えるのがそれなりに得意だったのでその流れで研究のような領域に近いところにいた。その選択は僕に活力をもたらしたときも多々あるが、研究というのは概して世の中での活動から遠いものでもあった。学会での発表などは少数の集まりに何かを聴いてもらう場に過ぎない。時間を掛けて仕上げて査読も受けたものの特に注目もされないまま忘れされていく論文がいかに多いことか。このことは僕が抱いていた願望、自分の成したことが世の中から称賛されたいとまでは言わなくともせめて無視はされないで欲しい、ということとは今思うとそれなりに反するところがあった。

もっとも、誰かのやったことが重宝もされないのは研究などの特定の領域に限ったことでなくどんな仕事でもよくあるように見える。悲しいことだが、誰かが意味があるといって大真面目に旗を振って人々が集まった先にあったものは虚像であった、といったことはどこにでもありえてしまう。遠いどこかにも、もしかするとすぐ目の前にも。


改めて僕の思っていた価値というのはなんだろうかと考えてみる。世の中から無視されたくないなどといった思いの中にある世の中とはなんのことだろうか。2～3人のなんだかよくわからない人の集まりはあまり世の中っぽくないかもしれないが、200人とか300人ならいいのか。少人数でも大企業や国家の幹部みたい人たちならいいのか。あるいは人だけではなく、地球の大気とか地上の動植物たちも含むのだろうか。

自分を受け入れて欲しい「世の中」なるものはあまりに存在が漠然としている。世の中は実は存在しないなどと狂ったことを言いたいわけではない。何かを生み出してそれを受け入れて欲しいと思っているとき、その欲望の先に成果を受け入れる人の姿があまり具体的に浮かんでいないのならそれは欲望の形として健全ではない気がするのである。

職業が技術者だろうがなんだろうが他者という得体のしれない存在に思いを馳せることからは逃れられないのだと思う。人には素晴らしい面もあるだろうが、そうでない面も多々ある。というか、世の中というのは正直よくわかんなくてどうでもいい他者だらけなのではないだろうか。では自分が別段素晴らしいとも思っていない人にかろうじて受け入れられることの意味はなんだろうか？

こんな疑問を仮に持ったのだとしても、世界に永く残り続けて欲しいとか、大事にしたいと思えることがいくらかはあるだろう。それを追求していれば、いつかは最初作り上げたいと思っていた価値にたどり着くのではないかと思う。この追求は実際には拙い悪あがきみたいなものかもしれないが、むしろほとんどの物事が忘却される儚い環境の中で足掻き続ける胆力と信念こそが生きる上で大事なのではないか。ここでいう大事というのは他者ではなく自分にとってである。いかなる成果も最後には自分のためになっていなければならない。


久しぶりにあまりまとまりのない文章を書いた。

2023

転職することにしました。

これまでやってきたこと

計算機の先端技術を社会で実用化することを社是とする会社に10年弱勤めていました。働き始めたときは30人程度だったメンバーが気づいたら10倍程度になっていて、会社が始まってから中規模程度の組織へ成長する期間を一緒に過ごした、と言えるかもしれません。

現職に勤めるきっかけとなったのは学生の頃にインターンで2ヶ月ほど研究開発系のプロジェクトに関わり、会社、というよりそこにいる人達への魅力を感じたことが大きかったように思います。少人数の技術者集団でありつつも自分たちの培った技術を見知らぬ人たちへ貪欲に売り込んでいく姿勢に触れて、こんなこともできるのかと驚きがあったのです。

在籍中は色々なチームに関わる機会がありました。とりわけ長く携わったと言えるのは大企業を相手とするクライアントワークでした。お客さんが実現したい技術的課題を解決するためにどうすればよいかをソフトウェアエンジニアとして模索していました。研究開発をテーマとすることが多かったですがお客さんの持っている製品の改善に関わる機会もありました。プロトタイプの開発、資料作成、現場内で必要となるコミュニケーションが日々の仕事内容でした。ありがたいことができたかどうかはあまり自信がないですが、色々なことができたとは思います。また、直近ではクラウドサービスの開発や運用に携わることもできました。

これからの仕事人生に期待したいこと

入社してからの仕事は上で述べたようなクライアントワークが多かったのですが、実際にお客さんと話して解決したいことによく目を向けると、何かしらの先端技術を投入すれば解決できるような単純な話ばかりではなかったように思います。ビジネスという巨大な機構からすれば技術はほんの一要素に過ぎないのかもしれない、と。次第に初期の頃にあった技術への執着は薄れ、重要な問題をどんな手段をもってしてでもよいからクリアして、評価されるようになりたいと思うようになりました。もっとも、これは自分が遭遇した案件がたまたまそうで、アルゴリズムの性能や精度がクリティカルな案件にあたっていたら別にそうは思っていなかったのかもしれませんが、自分はそういう運命を辿ることとなりました。

困っていることや欲しいものがある人や組織はおそらく世の中にいくらでもいます。その中にはあまり筋の良くない欲求もまぁまぁ存在するのでしょうが、本当に大事なものもいくつかはあるでしょう。僕はそのようなものを世の中に見出して解決したり改善する立ち位置につきたいと感じました。その過程で何かしら頭や知恵を使わないとクリアできないことがあると嬉しいような、そんな気持ちです。

もうちょっと具体的に

直近で目に見えていることについて少しだけ述べます。世の中を生きる人たちは多かれ少なかれ何かを学び続ける必要があるのだろうと思います。学校のような閉じて守られた空間にいる間も、それを出た後も、ずっと。それは楽しみのためというよりも変動し続ける世の中にどうにかしがみついていくため、という方が確実なのかもしれません。そういうことが好きな人は自分一人で自由にできるのでいいでしょうが、そうできない人もおそらく多分たくさんいるでしょう。計算機にできることは限られているとしても、そういった人たちの助けになるものを作り出せるのだとしたら素敵なことなのかもしれない―

とりあえずはこのようなところです。なんだかあまり具体性がなくて言葉にするのも後ろめたいですが。

こういう考えも時間が経つとまた変わってくるのかもしれません。大事なのは世の中で何が実現できると素晴らしいか考えるのをやめないことだという気がしています。

ICPC2023横浜大会 準備記

ICPC2023横浜大会の準備に関わったので記録を書きます

G問題

n 枚のカードが並んでいる。 6面ダイスを振り、出た目を x として、左から x+6k 枚目にあるカード (k=0,1,2,...) をすべて除去するような操作を繰り返す。 最後の1枚になるまで繰り返す。各カードが生き残る確率は？

継子立てのように、なんらかの機械的な篩分けのプロセスを経て最後の1つが残るような設定を考えたいと思って作問を始めました。 継子立て自体は古典的な題材なので何か真新しいものをなんか考えようかなぁと思い、せっかくなのでサイコロ君に登場してもらうことにしました。ICPC名物要素です。

自明には状態数が O(n ^ 2) なのでなんか工夫しないといけないのかなぁと思ったのですがちょっと考えるとカードの枚数は操作回数に対して指数的に減衰していくから、必要な状態はそんなに多くなさそうということがなんとなく察せます。もうちょっと真面目に考えると普通にメモ化再帰すれば線形時間くらいになっているということが示せます。

で、この問題は結構ギャグっぽい感じがしました。よくわからないけどそれっぽくメモ化再帰するとなぜか速い、みたいな。なんか、ガチガチに計算量絞り込んで高速化するタイプとはちょっと違う感じがします。 問題文に黒いタロットカードを出してちょっとムーディーな感じを出せたので満足です。問題への個人的な思い入れ度合いは… 普通くらい。

K問題

インタラクティブ問題です。地区予選の恒例になるかどうかは定かでないですが、とりあえず2年目です。

自分が原案の問題ではありません。傍から見ると手でデバッグするのは辛そう、かつこの問題でハマって多くの時間を消費するのもなんだかなと思ったのでテスト用ツールを選手に配布できると良いのではと思い、そのように進めました。準備に協力いただいた方々に感謝です。たくさん解いてもらえたのもありがたかったです。

インタラクタ (ジャッジ用のプログラム) を書いていて一つ苦労した点として誤差の扱いがあります。円と線分の共通部分の計算には平方根が必要となるわけですが、平方根は原点付近で微分が急峻になる、つまり仮に誤差が1e-14くらいの超小さい数だとしても平方根を取ると1e-7くらいのまぁまぁでかい数になって結構やばいということに気づきました。ちょうどインタラクタをストレステストしていたときの頃です。レスポンスが0であるはずのクエリに対して正の実数を返してしまうことがあり、これはちょっと真面目にやらんとまずいと気づきました。というか、それまで平方根が及ぼす影響を甘く見すぎていました。幸いなことに今回の制約ではレスポンスが0であるかの判定は浮動小数点数無しで行えることがわかったのでそれを実装しました。

競プロまわりをめぐる情勢など

ついでなので。 世界的に権威ある大会であった Topcoder Open や Google Code Jam が今年で終幕し、さらに今年10月に予定されていた ICPC 世界大会が中東情勢のあれこれで延期するなど、結構波乱に満ちた年になった感じがします。 特に Topcoder にはもう記憶がはるか彼方ではあるものの自分が20代の頃かなりの時間を費やした場なのでこれが消滅していくのは寂しい気持ちがあります。

”寂しい”というと小さな感情に過ぎない感じがしますが、なんというか個人的にはそれ以上のものがあるような気がしています。 結局世の中にあるものは日々変遷として、古きものは消え去り、人々の記憶からもなくなる運命にきっとあるのでしょう。領土が異民族に侵略されればその土地の歴史などはすべて都合の良いように塗り替えられ、プラットフォームが消滅すればその上で培われたいかなる秀作や努力の結晶、良い思い出も跡形もなく消え去っていく、というように。 あるいは、なにがしかのデータがどこかのサーバーで残っていたしても、人々が新しいものだけに価値を感じ、古きものにはアクセスする方法も知らされないのなら、それは誰からも見られすらしないスクラップ同然であるというように。

しかし、優れたものはたとえ時を超えても継がれていく価値があるのではないだろうか？ 何百年前の文学作品であっても人間の普遍的な性質を描写したものであれば現代であってもそれは心を打つだろう。絵画にしても然り。数学も時代によって動機や関心が違うところがあるかもしれないけど、数理的に興味深いと思わせるような概念や問題には多分なにかしらの普遍性がありそう。まぁ分かりませんが。 プログラミングコンテストの問題は分かりませんが、しかし根本的には与えられた問題の構造をいかに数理的に解明し、それをどう機械的な手続きに落とし込むかというところにあって、コンピュータという複雑な装置は経るもののやってることはだいぶ根源的なのでは？

…とここまで書いて何が言いたいんだかわからなくなってきましたが。コンテストの問題でも古くても面白いものは面白いはずだし、それが時間とともにプラットフォームが終了したり大会が閉幕したりして見向きもされなくなるのは、いかに自分にとって前世のことだと言ってもやるせないなぁと思うのです。 そこには過去のいろんな人の情熱や感性が注がれているのです。その正体は注意深く見ないと、ただの無機質で形式的な言葉が並べられているだけにしか見えないわけですが。

とはいってもプログラミングコンテストに関して大会が存続していない限りはまぁ見向きもされなくなるのはやむを得ないでしょう。例えば75分3問形式のコンテストがもう廃れて同然なのにその過去問をわざわざ謎のプラットフォームを起動して解くというのはまぁ結構奇特かよほど熱心でない限りやらない気がします。(こんなこというとファンの方には不快かもしれませんが、すいません) 話にオチはありません。とりあえず今日はこれくらいで。そういえば AOJ-ICPC は旧 twitter にどっぷり依存したウェブサイトだったのですが、APIが使用不可になった影響で更新作業もできなくなりました。これも課題です。

Satisfactory に登場するパーツの感想

ちょっと前までですが Satisfactory というオートメーション系ゲームをずっと遊んでいました。クリア後もやり直したり高難易度 mod 入れたりしてずっと遊んでいたらプレイ時間がいつの間にか600時間を超えていたので、感想としてこのゲームに出てくるパーツについて思ったことを書いていきます。

↑このゲームではこういうふうにでかい機械を並べていろんなものを作っていきます。 何を作ってたのか思い出せません

↑プレイ時間650時間… 他にやることはなかったのだろうか？

以下はネタバレ全開で書いていくので未プレイの方は注意です

Tier 0

自然を破壊しつつコンベアなどを敷いていきます

  • 鉄鉱石、銅鉱石: オートメーション系ゲームにありがちな露天掘り(と言って良いのかわからないけど…)。資源が無限なのはこのゲームの良いところです

  • ポータブルマイナー: 鉄板とロッドから作れるとは思えないくらい高性能ですごい

  • 鉄のインゴット、銅のインゴット: 鉱石をそのまま溶かして鉄にしているので不純物いっぱい混ざってそうだがオートメーション系ゲームではそんなこと気にしていたら先に進めないので、気にしない。

  • 鉄板、鉄のロッド: 鉄の基本パーツ。特に言うことはない

  • ワイヤー: 銅製品… かと思いきやなぜか代替レシピで鉄からも作れる。電気伝導率とか大丈夫なんだろうか

  • ケーブル: いろんなところで要求される。なんか建てようとしたときに「クソ、ワイヤー足りないやんけ」とよくなる

  • ねじ: 基本的な産業用パーツっぽい割に意外と出番がない。このゲームのおかげでねじの製造方法を知りました。

  • 強化鉄板: 組み立て機を使う最初のパーツ。生産スピードがやや遅い

  • コンクリート: 土台建築に必須。とはいえこのゲームの石灰岩はやや供給過多気味にも思える

  • バイオマス: 草食動物のごはんみたいな見た目をしてる。ゲーム序盤だけ必要になる。発電機への供給が自動化できればもうちょっと出番があるような気がするが…

  • ゼノ・ザッパー: 初期武器。スタンガンみたいなものだが火力も連射も足りなすぎてあまりに弱い。。

Tier 1

  • コンベヤ分流機、合流機: ブループリントが導入されるまではこれをいちいち一つ一つ置いて機械に分配する必要があって面倒だった。鉄板とケーブルだけからできるとは思えないくらい高性能

Tier 2

夜に佇む軌道エレベータの景色が素敵です

  • 銅のシート: 薄べったく加工した銅… これ以上に言うことは何もない

  • ローター: モーターのうち回転する部分。すでにモーターを必要としそうな建築物がいっぱい出てきてる気がするけど気にしたらいけないのでしょう

  • モジュラーフレーム: 謎の骨組み。見た目に反して生産にかなり時間がかかるため苦戦ポイントの1つとなる

  • スマートプレート: 謎の薄べったい金属パーツ。何に使うんだろう？

  • 固形バイオ燃料: 森林伐採によって得られる。森林伐採のためのアイテムであるチェーンソーの燃料として使う。

  • ジャンプパッド、着地用ジェル: 何の役にも立たない… 誰得？

Tier 3

パイプを眺めて喜んでいます

  • 石炭: 露天掘りの資源。黒いけどテカテカ光ってる。すごく炭素です

  • 鋼鉄のインゴット: 鉄に炭素を入れて強度を増しましたみたいな基本素材。良いパーツです

  • 鋼鉄のパイプ: パイプ状に加工しただけ、それ以上に言うことはない

  • 鋼梁: 建築専用パーツっぽい見た目だがコンベアとして使えてしまう。

  • 多目的フレームワーク: 知的玩具みたいな見た目の変なパーツ。産業用途で役に立つようにはあまり見えないが、とりあえず本社に送り付ける

  • ゼノ・バッシャー: 強い剣。これがあればエイリアンとの戦闘は大体なんとかなる

  • パイプライン: 流体はこのゲームの面白さの1つだと思う。揚程の概念はちょっとむずかしい、というか wiki 見るまでよく分からなかった

Tier 4

Lizard Doggo が妙な位置にいます

  • コンクリート被覆型鋼梁: どう見ても建築専用素材に見えるのだが、やはりコンベアとしても使えてしまう。量産がやや大変

  • ステーター: モーターの回らない方。モーター以外にも謎用途で使われる

  • モーター: 動力機関の基本パーツ。ちゃんとローターとステーターを組み合わせて作る構成になってて良い

  • 自動ワイヤー: ステーターにケーブルをぐるぐる巻き付けてできる何か。何の役に立つのかわからないが、とにかく量産して本社に納品している。

  • ヘビーモジュラーフレーム: 作るのに手間がかかるモジュラーフレームをさらに作るのが大変にしたような素材。相変わらず何に使うのかはよくわからない。今後いろんなところで要求されることになり苦労することになる。モジュラーフレームを5つも要求する割に見た目はモジュラーフレームから大して変わっていない。

  • ブループリント・デザイナー: Update7 から入った便利機能。使い慣れるまでがやや難しい。生産したいパーツごとにブループリントを作るよりは、機械を並列化に並べてコンベアで繋いだブループリントを作っておくのが便利な使い方な気がする。

Tier 5

Satisfactory の公式 wiki を見ると副産物無しでパーツを生産する方法が乗っていたのでその通りに建設しました

  • 石油: 発電にも石油製品にも使える便利素材。このゲームでは石油はそこらへんの地表にそのまま出てきていて、機械はそれを吸い上げているように見える。地底深くを掘ったりはしてなさそう

  • プラスチック、ゴム: 石油といえばプラスチック、ゴム製品やろ！みたいなノリ？ここに来て副産物という概念が初めて出てくる

  • 重廃油: 副産物だけど紫色でなんかかっこいい？そういう分類の油があるのかと思っていたらどうも Satisfactory 固有の名前らしいです

  • 燃料: 石炭発電に比べて発電量がでかくて良い

  • 合成樹脂: ペレットみたいな素材。副産物だけど適当に sink したりすれば終わる

  • 石油コークス: かなり炭素な見た目をしてる。実在の物質のようですが、なんか奥が深そう。ゲーム内ではあまりお世話になったことがない。ターボ燃料を作るのに便利かもしれない程度だろうか？

  • 基盤回路: コンピュータを作るための部品。こういった基本パーツから組み立てていくのはこのゲームの楽しいところ。現実の回路の構成はさすがにもっと複雑そうだけど樹脂と銅がベースになっているのは概ね間違ってなさそう？

  • コンピュータ: 製造機が必要となる最初のパーツ。作るのが大変

  • モジュラーエンジン: 湯たんぽみたいな見た目をしている。これまでの納品パーツに比べるとまだ何のパーツなのかわかりやすい、ような気がする

  • 自律制御ユニット: 炊飯器みたいな見た目をしている。制御用コンピュータらしい。それ以上に言うことはあまり…

Tier 6

鉄道をなんとなく引いたりして結局うまくいかなくて挫折しました

  • カテリウム鉱石: 一応 Tier 6 でスキャナ更新が来るらしいけど、これはゲーム序盤で見つけておかないと電柱Mk.2がアンロックできなくて非常に苦労すると思う

  • 鉄道: 大量・高速輸送の手段ということになっているのですが、土地も電力も食うので使いどころがかなり難しい気がします。未だに使いこなせていません

Tier 7

  • ボーキサイト: ゲーム終盤の主人公的な存在。アルミなんて世の中いくらでもあるのになんでこんな精錬させるの大変なんだろうと思って歴史を見てみると結構面白かったり。アルミが天然に存在するのは酸化物としてであってこれを還元するのはかなり大変で、アルミが量産できるようになったのはこの100-200年くらいのことらしいのですね。

  • 未加工石英: Tier 7 で一応スキャナがアンロックされるみたいですが、これはゲーム序盤で見つけてブレードランナーをさっさと開放したいところ

  • アルミナ溶液、アルミのスクラップ、アルミのインゴット: アルミの精錬プロセスで出てくる奴ら、まぁまぁ大変。シリカが副産物として出てくるのは精錬プロセスの大変さを多少リアルにするため？

  • アルクラッド・アルミニウムシート: なにその長い名前？と思っていたがアルクラッドは実在する素材らしい。ゲームでは主に最速コンベアとして利用することになる。

  • アルミ筐体: アルミをケース状にしたもの… これ以上言うことはない

  • 無線制御ユニット: 先端部品だが、名前に反してあまり無線通信が必要とは思えない用途でよく使用される

  • 硫黄: これもそこらへんの土地の地表からそのまま採掘する形になっている。現実世界だと火山の火口付近から取れるらしいです。毒ガスが蔓延しているので採掘する人は命がけとか…

  • 硫酸: wikipedia によると硫黄から硫酸を作るには、まず硫黄を酸化して SO2 にして水に反応させることで製造できる、らしい。硫黄自体は水には溶けにくいので、精錬機では途中の化学反応も込めてやっていることになる

  • バッテリー: アルミのケースに硫酸とアルミな溶液を詰めてできる何か… 現実とはだいぶ乖離してそうな気がする

  • スーパーコンピュータ: 「スーパーコンピュータはコンピュータの次世代バージョンだ」という説明が大胆すぎる

  • 組立指揮システム: 多分このゲームで作るのに一番手間が掛かるパーツ。最終フェーズで大量生産が必要とされ苦戦することになる。見た目がかっこいい

  • ヨウ素注入フィルター: 放射線避けとして重要なアイテム。ゲームにヨウ素は登場しないのでクイックワイヤーとアルミ筐体で代用している。しかしクイックワイヤーはともかくとして、アルミ筐体を使うのはかなり謎

  • ホバーパック: 便利！！

Tier 8

現地住民の反発を乗り切り、原発の建設を敢行しました

配線をミスったせいで本来発生しないはずの放射性廃棄物が溢れかえってピンチになっています

  • ウラン鉱石: 危険物質なこともあり比較的世界の奥地に存在する。これによって作られる原子力発電所は多大の電力を供給するかわりに処理が困難な放射性廃棄物を無限に生産することになり、今世の電力問題に疑問を投げかける形になっている…？

  • 被覆型ウラン･セル: ウランをちょっと加工したもの… それ以上特に言うことはない

  • 電磁制御棒: 制御棒という名前ではあるけどこの棒自体に制御装置をつける必要はあるのだろうか？

  • ウラン燃料棒: 原子力発電所の燃料。作るのにめちゃくちゃ時間がかかるため、ちゃんと想定通りのスループットで作れてるかどうか確認するのが大変

  • ウラン廃棄物: 危険物質。見た目がすでにヤバい。捨てることができない仕様なのが良い。加工して非分裂性ウランにすると多少マシになる

  • 磁界発生装置: 産業用パーツっぽさはあるがプロジェクトパーツなので相変わらず何に使うのかはよくわからない。

  • 窒素ガス: 地中を破砕法で加圧して窒素を回収するということらしいのだが、この惑星の見た目からして窒素は大気中に十分あるのでは？という感じなのでだいぶ謎な感じの回収プロセスになっている

  • ヒートシンク: よくあるヒートシンク… それ以上に言うことはない

  • 冷却システム: ヒートシンクに窒素ガスを加工してこれになるのだろうか？

  • 溶融モジュラー・フレーム: あの面倒なヘビーモジュラーフレームに窒素ガスを必要とすることでさらに製造が大変になったパーツ。採掘機Mk.3で必要となるためそれなりに量産しておく必要がある

  • ターボモーター: 「普通のモーターより複雑で強力」というややヤケクソ感のある説明。作るのが非常に大変

  • 熱推進型ロケット：いかにも何かを稼働させそうなパーツを組み合わせてできる機械。見た目がかっこいい

  • 硝酸: 窒素と水をまぜまぜして硝酸ができるみたいな風になっているが冷静に考えてそんな化学反応は起きないので混合機の中でかなり複雑な製造プロセスを行っていることになるのでは？と思って Bing に聞いてみると以下のような回答が得られた

窒素と水から硝酸を製造するプロセスは、アンモニアを製造するハーバー・ボッシュ法で作られたアンモニアに、空気中の酸素を反応させることで生成されます。この反応によって、一酸化窒素と水が生成されます。この一酸化窒素は、再び空気中の酸素と反応して二酸化窒素になります。そして、二酸化窒素は水と反応して硝酸になります

  • 非分裂性ウラン: ウランの同位体で天然ウランの大部分を占めるもの… らしい

  • プルトニウム・ペレット、被覆型プルトニウム・セル、プルトニウム燃料棒: ウラン廃棄物を加工するとこれになる。とても手間がかかる

  • プルトニウム廃棄物: プルトニウムを燃料として使っちゃった場合の最終形。絶望的な見た目をしている。とにかく世界の端まで持って行って貯蔵し続ける以外に選択肢は無い。

  • 銅粉: 核パスタの製造のために銅を粉々にした素材。重量がすごそう

  • 圧力変換キューブ: 核パスタを封じ込められるすごいキューブ。しかしなぜ無線制御ユニットが必要なのだろう？

  • 原子核パスタ: 中性子星内部にあるヤバい物質をなんと地上で保管できてしまう。こんなものを何に使うのか謎だがそんなことは気にせず納品するとゲームクリアになる

MAM

  • 鉄筋ガン: 架空の武器。割と手軽に作れる割には強い

  • AIリミッター: まだコンピュータも作ってない段階で突然AIを制御する機械が出てくる流れがなかなかクールで気に入っています。見た目もカテリウムと銅を組み合わせただけとは思えないくらいちゃんとしている

  • パワースラッグ: なめくじ探しはこのゲームの醍醐味の1つです

  • 水晶発振器: 実在する産業用パーツであることを知った。本体は円盤ではなくマイクロチップみたいなやつの方。というかこの円盤はなんだろう

  • エクスプローラ: 長距離移動で重宝する。Update 8 からなんか操作がおかしくなっている気がするがどうなってしまうのだろうか

  • レーダータワー: 便利、というかこれがないと後半やってられない

  • 黒色火薬: 架空の何かだと思っていたのだが実在する物質らしい。硝石が爆発のためのキーになるらしいのだがそれが含まれないのがやや片手落ちか

  • 無煙火薬: これも実在の物質らしい。現実には黒色火薬を加工して作られるわけではないらしい。石油が材料になっているのはそれなりに現実に即しているとも言える…？

  • 圧縮石炭: 貴重な硫黄を消費する割にあまり役に立たない。石油が有効になるまでの石炭の代替品として使えるかも、くらい？

  • ターボ燃料: 使ったことはない。燃料発電所でのエネルギー効率が良いので、ゲーム後半で原子力発電所を作らずに、ターボ燃料を主な発電材料にするのは有りかもしれない。

  • 爆砕鉄筋: インチキすぎる火力をしています。製造の手軽さを見ても、コスパ面から最強の武器だと思う

おわりに

Satisfactory は探索とか生産が楽しいのもあるんですが、それぞれのパーツを見ても現実に沿ってるところもあればそうでもないところもあって楽しいと思いました。 あとははやく Update 8 が experimental から main にマージされてほしいです。

ICPC国内予選 2023 準備記

ICPCというプログラミングコンテストの予選が今日(といってももう日付変わりましたが)の夕方にありました。50チーム程度が選抜されるようです。

これまでこの大会の準備側の記録はほとんどなかったように思いますが、準備に興味を持つ人を増やす意図もややあり個人的な記録を残します。 今年は C, F 問題の原案を作成していたのでそれについて記そうと思います。

C 問題原案

問題文

教室でNxNの席が並べられている。
席替えを行い、以前前後または左右で隣り合っていた生徒同士は、
席替え後には少なくともマンハッタン距離が floor(N/2) 以上になるようにしたい。
そのような席替え案を求めよ。2 ≤ N ≤ 50

中～序盤向けの問題を作ることを念頭において作題していました。最初は2次元ではなく1次元のものを考えていました。問題を思いついてすぐには答えは分からなかったのですが少し考えて、半分くらいのステップ幅で行ったり来たりを繰り返すと大体距離 N/2 が達成できる事がわかりました。 しかしこれを問題にすると、1次元だと実装もほとんどなくてあまりに味気ないため、2次元に拡張してみたのがこの問題になります。2次元でも1次元の考え方が適用できます。

予選だと1次元のバージョンを介さずいきなり2次元のものを解くことになるので結構面食らった選手の方は多かったかもしれません。実際自分が選手だったらどう手を付けるといいか分からず結構途方に暮れたのでは？という気がします。N/2というのはなんだかマジックナンバーっぽくてよくわからないし、偶奇の場合分けでハマりそうな点があります。

ちなみに提案時には気づかなかったのですが、次のようにしても解くことができます。NxNの席を市松模様に塗り、片方の色で塗られた生徒の位置は変えず、もう片方の色で塗られた生徒は前後と左右方向に N/2 だけずらすと、距離として大体 N-(小さい定数) が達成でき、問題で要求されているよりも良い結果が得られます。こちらで解いたチームもいくらかいたのかもしれません。

F 問題原案

問題文

2次元上の非凸多角形で、内側を塗りつぶされたものを考える。
この多角形の有限個のコピーを、拡大縮小や回転を行わずにいくつか張り合わせて、
凸集合を作りたい。そのようなことは可能か判定せよ。

年始頃だったか、風呂に入っているときにミンコフスキー和についてぼんやりと考えていました。

ミンコフスキー和の引数となる点集合のうち片方は入力で与えられ、もう片方は自由自在に構成して良いとしたとき、これらのミンコフスキー和がなにか”いい性質”を持つようにできるだろうか？といった問いから確かスタートしました。 ”いい性質”というのはなんでもよかったのですが、とりあえずは定番的な性質である非空な凸集合ということで探索を始めました。 これはある意味で自明に解けてしまいます。もし入力で与えられる集合が連結ならば、もう片方を適当なサイズの凸集合にすればミンコフスキー和も凸になります。つまり任意の入力に対して可能であるというのが答えです。 これでは面白くないので、自分で構成する方の集合に何か制約を課した方がいいのではないだろうかと至ります。 例えば凸集合は面積を持つので、面積を持たないような集合に制限するとどうだろうかと考えたのですがこれも適当なサイズの円周を取れば良いということになってやはり自明な問題になってします。 それなら有限集合、つまり点列に限定するとどうだろうかと考えてみたところ、なんだかいい感じに複雑な必要十分条件が得られたので、問題として完成させたものがこちらになります。 考えていた証明は公式解説とほぼ同じです。

問題文自体はシンプルで、実装はそれほど複雑になりきらないながらも幾何に対する実装の慣れはある程度必要で、考察の過程が面白いので個人的に気に入っています。

おわりに

準備サイドは自分で創作したアイデアを多くの人、それも適当な群衆に対してではなく志の高い強豪達を含む選手たちに対して披露できる貴重な場であると思っています。 自分は準備中もコンテスト中も楽しめたので満足しました。地区予選に出られる方はお会いしましょう (問題文とかジャッジシステム上で。。)

熱力学 (カルノーの定理)

読書記録

前の記事からの続き。田崎先生著の熱力学を読んでいる。相変わらず自分用のメモとしてしか書いていないので、他の人が見て読んでわかるものになっているか定かでない。

熱をエネルギーの形態として認める

古典力学ではエネルギーとして運動エネルギー、ポテンシャルエネルギー、熱エネルギーの3種類があったように思われる。もしある力学的な系に保存力と呼ばれるクラスの力だけが作用しているのであれば、その系では運動エネルギーとポテンシャルエネルギーの和は常に一定に保存されることが言える。このことは運動方程式から導かれる。現実には保存力だけが存在するわけではなく、摩擦力などにより運動エネルギーとポテンシャルエネルギーの総和が減少することがある。このときは摩擦により接触面に熱エネルギーが発生しているものとみなし、結局全体ではエネルギーの総和は一定なのだと考えていた。

熱力学でも同様にこれら3種類の総和は一定であるという見方を取る。この前提は他の本だと熱力学第一法則と呼ばれることが多いようである。熱は状態量とは見なせないため、エネルギー保存則はある時点と別の時点でのエネルギーの差分に着目した式で書かれることになる。ある熱力学的な系で、系が外界にする仕事を $W$、内部エネルギーの変化量を \Delta U = U(T; X) - U(T; X')、外部から受け取ったエネルギーを $Q$ とすると $W=\Delta U+Q$ が成り立つのだと記す。他の書とは違って本書ではこの式自体は熱 $Q$ の定義だと位置づけており、根本的な前提とはみなしていない。あくまでも原点は断熱過程のときに仮定したエネルギー保存則にあるという立場を取っているようである。

最大吸熱量によりヘルムホルツの自由エネルギーと内部エネルギーが繋がる

ヘルムホルツの自由エネルギー $F$ と内部エネルギー $U$ はそれぞれ異なる仮定の下で定義されていたため独立した存在のようになっていたが、最大級熱量を定義する際に初めてこの2つが繋がるように見える。

熱は状態量ではない。つまり操作の過程によって熱は変動するのであって $Q(T; X)$ などと記すことはできないのであった。しかし、系がある状態から別の状態へ遷移するときの吸熱量として取りうる最大値については定義することができるはずである。特にここでは等温操作を考え、状態 $(T; X)$ から $(T; X')$ へ移るときを考えると、熱 $Q$ が最大になるのは仕事 $W$ が最大になるときであり、これは等温操作における最大仕事の定義より $W_{\max} = F[T; X] - F[T; X']$ に等しい。
そこでこの吸熱量としてとりうる最大値を $Q_\max(T; X \rightarrow X')$ とおく。
$Q_\max$ を展開して記すと

  • $Q_\max(T; X \rightarrow X') = F[T; X] - F[T; X'] + U(T; X') - U(T; X)$

となる。

カルノーサイクルは効率最大の熱機関である

熱機関は高温から熱をもらうことで力学的エネルギーに変換する装置である。熱すべてが力学的エネルギーに変換できるわけではなく、いくらかは無駄な熱エネルギーに変わってしまう。

このときの効率は、高温からの熱エネルギーを $Q_H$、力学エネルギーを $W$、低温環境へ排出する熱エネルギーを $Q_L$ とすれば (効率=) $W/Q_H = 1-Q_L/Q_H$ となる。

ここで上に述べた最大吸熱量を解析する動機が生まれる。熱自体は状態量ではないので解析はできないが、一方で最大吸熱量の比については何か良い関係があるはずという期待ができる。ここで $Q_\max(T'; X'_0 \rightarrow X'_1) / Q_\max(T'; X_0 \rightarrow X_1)$ という比について考えることにする。4つの状態に何の関連性もないとやはり何も言えなそうなので、$X_i$ と $X'_i$ の間には断熱準静操作で行き来が可能であるという制約を設けることにする: $(T; X_i) \longleftrightarrow (T; X'_i)$ $(i=1,2)$. つまりカルノーサイクルを考え、そこでは2つのタイミングで吸熱が発生するのでそれを比という尺度で比較するというものである。

カルノーの定理が主張することは、この比は熱力学的な系の選択や示量変数 $X_0$ などには依存せず温度 $T, T'$ だけで決まり、特に温度目盛が絶対温度を0とする(普通の温度指標)なら $T'/T$ になるというものである。

$T'/T$ であることは理想気体を用いて単純に計算することで得られる。

カルノーの定理の中核となる前半部分の導出を簡単に説明する方法は大まかには次のようである。カルノーサイクルを思い浮かべると、それ自体は全体で等温操作にも断熱操作にもなっていない。しかしカルノーサイクルに対してちょうどそれと逆の動作をする逆カルノーサイクルを組み合わせた系を考えると、系全体は外部との熱のやり取りが熱のやり取りを0にキャンセルして行える。これを強引だが断熱準静操作と見なすことにすると、断熱準静操作では系のエネルギーは保存されるので1周の間にする力学仕事に関して等式を立てる比について所望の結果を得るという手順である。熱力学的な系に依存しないことを示したいため、系としては2つのカルノーサイクルの複合系を考えることになる。

元の熱機関の効率の話に戻ると、カルノーサイクルが効率最良の熱機関であることは上記のカルノーの定理の結果から得られる、というよりはその導出過程を改めてなぞることで得られるようである。ある熱機関があり、カルノーサイクルより効率がよいのだとする。これに対してカルノーサイクルの逆を行う系を追加する。カルノーサイクル自体には定数倍の自由度があるが、高温域へ提供する熱が、今考えている熱機関が吸収する熱と釣り合うようにする。すると結果として機関全体は低温から熱を吸い上げて力学仕事を行うような系になり、第二種永久機関が作れることになる。これは矛盾であるため、カルノーサイクルより効率の良い熱機関は作れないのだというのである。

実際にはこの”証明”には穴があるようで、厳密にはエントロピーの考えを取り入れて考察する方が見通しが良いようである。

カルノーという人

ところでこのカルノーという人はどんな人だったのだろうと wikipedia を見ると、36歳の若さで亡くなっており、生前は熱力学について重要な業績を残したにもかかわらず全く評価されなかったようである。悲しい。