season's quarterly

数学/物理/プログラミング

ICPC2022国内予選参加記[SOS Brigade]

7/8に開催されたICPC2022国内予選に参加しました。

去年の参加記 season1618.hatenablog.jp

チームはSOS Brigade(shobon + otoshigo + season)です。otoshigo君がメンバーの頭文字がSOSだと指摘していたので、自分がじゃあSOS団wと言ってそうなりました。

2022/Teams/List - ICPC OB/OG の会

今回もtraP内で何回か練習しました。

競技

今年は各々自宅からDiscordで繋いで参加しました。

まずAをotoshigo君、Bを自分、Cをshobon君が取り組みました。A, Cは直ぐにACされました。

B問題はババ抜きで終了までにカードを取る操作が何回行われるかという問題でした。「入力サイズが10000行以下」を「データセットの数が10000以下」と空目して、最初30分くらい分からん~となってました。誤読に気付いてからはやるだけだと分かったんですが、実装に手こずって結局90分かかってしまいました。

提出しようとしたときにたまたまネットワークの調子が悪くて、大会のサイトにアクセスできなかったり、Discordが一瞬落ちたりしてしまったので、コードだけ送ってshobon君に提出してもらいました。一発でACできたので良かったです。

その後は二人がD問題を考えていたようなので、自分はE, Fの問題を読んでましたが何も分かりませんでした。終盤になってDをACしたので凄いと思った。

結果

ABCD4完59位(学内4位)でした。二人のおかげで順位がかなり上がりました。:kansya:

ちなみにtonosamaが単独で全完して優勝してました。凄い。

trap.jp

2021年度の読書記録

『たのしいムーミン一家』

受験期に少しムーミンのアニメを見てたので本も読んでみたくなった。ミイが出てこなかったり、フローレンの名前が出てこなかったり、結構アニメと違った。

『コンピュータグラフィックスの歴史 3DCGというイマジネーション』

大学の図書館で初めて借りた本の一冊。アイヴァン・サザランドの研究室とかCG映画の歴史などの話があった。あんまり覚えてない。

『デザインの授業 目で見て学ぶデザインの構成術』

何故かデザインに興味を持った。デザインの本を読むのは初めてだった。テーマごとに色々なデザインの例が載っていて面白かった。

『科学革命の構造』トーマス・クーン

東工大立志プロジェクトの読書レポートの課題図書で一番面白そうなものを選んだ。科学的発見はある時点で起こると明確に言えるようなものではないこと、現代から見た過去の業績の評価は誤解されがちであること(共約不可能性)、科学の発展は断続的であることなど、なるほどーとなる話が色々あった。文系の本を読むきっかけの一つだったかもしれない。

『鉛筆スケッチ モチーフ作例事典』

何故か絵を描きたくなったので借りてみた。モチーフ作例事典だから説明が丁寧なわけではなかったので上級者向けだったのかもしれない。それまでちゃんと絵を描いたことが無かったけど、濃淡を付けると段々立体感が浮かび上がってくる感覚とか結構面白かった。

ゲーテ 自然と象徴』

詩人・小説家として知られるゲーテは自然科学に関する著作も残している。内容はあまり科学的ではないけど芸術方面では評価されていたらしい。色彩に関してはニュートンを徹底的に批判していて、露骨に嫌いなんだなあというのを感じた。

線形代数の世界 抽象数学への入り口』

確か入学前にいいねしていたこのツイートの人が東工大生で「おー」となって早速借りてみた。テンソルとかの話は分からなかったけど、線形回帰数列と定数係数線形常微分方程式の解のなす線形空間が同型で、その次元から解が基本解の線形結合に限るって話が「線形空間ってこういう風に使うのか」となって面白かった。物理とかだと特性方程式解いて終わりで、解がそれ以外にないのかもやもやしてたけど、これを読んですっきりした。基底の取り方に依らないというのが重要なんだなあと実感した。

『視覚系の情報処理 心理学・神経科学・情報工学からのアプローチ』

心理学のアプローチが少し分かった気がする。

グーテンベルクの銀河系 活字人間の形成』マーシャル・マクルーハン

『魔法の世紀』の中でアラン・ケイが『グーテンベルクの銀河系』を読み込んでいたという話が出てきたので気になっていた。活版印刷の登場による人間や文化の変化など。分厚い本で、全体の流れを見失いがちだったのでいつかまた読みたい。

『装飾とデザイン』山崎正和

デザインの観点から見た人類史のような感じ。

『数は科学の言葉』

グーテンベルクの銀河系』に引用されていた。数を数えることとか長さを測ることについての哲学的なこと。実数ってかなり人工的な概念なんじゃないかと思った。古代ギリシャ人は有理数しか知らなかったし、小数が発明されたのもずっと後だったから。

ハッカーと画家 コンピュータ時代の創造者たち』ポール・グレアム

エッセイを集めたもの。「ハッカーと画家」は章の一つで本全体のテーマではない。めっちゃLISPの話があった。

文化人類学のすすめ』

文化人類学がどういう学問なのか分かる。文化による人間の差異を見極めるために文明人と未開人の差を観察するというのがこの分野の基本的なアプローチらしい。

『数学から創るジェネラティブアート Processingで学ぶかたちのデザイン』巴山竜来

読むだけで実装はしなかった。

『「いき」の構造』九鬼周造

日本人の精神を様々な感情間の関係の中で捉えて分析したもの。出てくる図は正に構造と言えるものだったので驚いた。

親族の基本構造クロード・レヴィ=ストロース

アンドレ・ヴェイユがムルンギン族の婚姻制度を群論を用いて解析した話は以前から知っていた。文化人類学に興味が出てきたので読んでみた。実際にオーストラリアの先住民族がアーベル群の構造になっていて、かなり上手く表現できるなあという感想。

『数について 連続性と数の本質』リヒャルト・デデキント

第一篇 連続性と無理数では切断を導入し実数を定義する。第二篇 数とは何か、何であるべきかではひたすら説明と定理を連ねて自然数を定義する。

『入門言語学ジーン・エイチソン

言語学も面白そうだと思った。あまり覚えていない。

『認識の分析』エルンスト・マッハ

マッハは物理学者・生理学者であり、哲学の研究も行っていた。認識について考えさせられる。

『数学デッサン教室 描いて楽しむ数学のかたち』

たまにTwitterで目にした本。自分もいくつか描いてみた。楽しかった。

『色彩のメッセージ 三原色と補色の絵画史』

錐体細胞の発見より前に光の三原色が提唱されてるのはどういうことなのかと思ったりして、また色に興味が出てきた。

特定の色を基本色に据えることは昔から行われていて、アリストテレスやアルベルティなども考えていた。絵具を混ぜると色が変わることから、できるだけ少ない色数でより多くの色を生み出す組合せを探すのは当然の試みだったのかもしれない。17世紀には色の三原色として赤・青・黄がほぼ確立されていたらしい。

ヤングは色の三原色からヒントを得て三色説を提唱した。ヘルムホルツは更に定量的な分析を行い、1868年には各錐体の分光感度を求めている。この辺りの推論にどの程度根拠があるかまでは分からなかった。

『色彩の科学』金子隆芳

色覚の学説の発展が詳しく書かれてとても良かった。特にアダムスの段階説が面白かった。ヤング=ヘルムホルツの三色説とへリングの反対色説を矛盾なく説明することができる。ヤングの頃は赤外線や紫外線が発見されて、人間に知覚できないものが意識された時代だったような気がする。

『人体観の歴史』

三原色の話がそうだったように、顕微鏡が発達する前から人類は人体についてかなり多くのことを知っていたのだなあという印象を受けた。

人体の解剖は紀元前3世紀には既に行われていて、動物体からの類推も合わさって人体の構造もある程度分かっていた。古代で運動神経と感覚神経、動脈と静脈を区別していたらしいが、なぜそんなことができたのかは書かれていなかった。18,19世紀頃の博物学についてさらに興味が湧いた。

解剖図と印刷の歴史についてそこそこのページが割かれていた。

『現代心理学 認知理論の展開』ジャン・ピアジェ

知能に関心があったので読んでみた。心理学というのがどういう学問なのか少し分かった。メディアで紹介されるような心理学はかなり実体とずれるような気がしていて、実際には脳を開かずに表面的な反応から知性を探ろうという試みなんだろうなあと思った。人間の知性については古くから議論されていて、哲学では認識論という分野だったけど、実証的にやろうということで19世紀に心理学に分化したということらしい。

『日本思想史』子安宣邦

全然覚えてない。

『表情分析入門 表情に隠された意味を探る』ポール・エクマン、フリーセン

中学の時『ノーゲームノーライフ』を読んでいたらポール・エクマンが出てきたので面白かった記憶がある。空の表情を読み取るスキルは実際にできる人もいるらしい。いくつかの感情について特徴的な表情や見分け方について解説されている。

『観察者の系譜 視覚空間の変容とモダニティ』ジョナサン・クレーリー

表象文化論Aの先生が紹介してた。人間の視覚に対する理解の歴史みたいな感じ。視覚の主観性について考えさせられた。結構面白かった。

『天体と軌道の力学』木下宙

天体力学はずっと前から勉強したいと思っていた。天体力学って多分物理系ではやらないけど地惑ではやるんですかね。ケプラー方程式の解や三体問題の平衡点、惑星方程式など。pdfも書いた。

https://github.com/season1618/PDFs/tree/main/Celestial-Mechanics

『天体力学のパイオニアたち カオスと安定性とめぐる人物史(上)』

カオスの発見された経緯など。下は借りなかった。

天文学史』桜井邦朋

天体力学のpdfを書くにあたってちゃんとした天文学の歴史を知りたいと思った。これもその時代の観測技術でどこまでのことが分かっていたのかかなり興味深い。

コペルニクス革命 科学思想史序説』トーマス・クーン

天動説は当時としては十分科学的だったという話があったので、その辺りの事情を把握しておきたいと思った。一般的には天動説に固執するキリスト教側と地動説を支持する近代的な科学者という構図で捉えている人が多いのだと思う。自分も小学校の図書室に置いてあったガリレオの伝記を読んだときはそういう印象を受けた。実際にはそう単純ではなく、両説の精度に大した違いはないとか、教会内での見解は様々だったとかいう話だった。

海王星の発見』

誤植が酷かった。2,3ページに一か所くらい。

『音声科学原論 言語の本質を考える』

音声信号処理で用いられるソースフィルタモデルやフォルマント周波数の話題など。

『わかる・身につく 歴史学の学び方』

面白い話が少しあった。

フェルメールと天才科学者 17世紀オランダの「光と視覚」の革命』

天才科学者というのはアントニ・ファン・レーウェンフックのこと。カメラ・オブスキュラを使って絵を描いていたとされるフェルメールと顕微鏡を発明したレーウェンフックを中心に、人間の視覚に対する認識の変化や、それについての科学と芸術を取り上げている。『観察者の系譜』と似た内容だった。

『日常礼賛 フェルメール時代のオランダ風俗画』

17世紀オランダ絵画について。

『世界の名著 ロック ヒューム』

ロック『人間知性論』『統治論』だけ読んだ。『統治論』では労働価値説とかの法哲学の話と国家体制をどうすべきかなどの政治哲学の話があって、この辺の分野の雰囲気が分かった。

『進化論物語 「進化」をめぐる六人の学者の功罪とその生涯』

社会進化論なるものがあることを知った。生物の進化は自明ではないから生物進化論を提唱することには意味があると思うが、社会が発展するのは当たり前に見えるから社会進化論が具体的に何を主張しているのかが分からなかった。この本では生物進化論と社会進化論を両方取り上げているので読んでみた。この本に拠れば社会進化論にはっきりした主張はないということだったが、やっぱり原典を読むのが一番良さそうとなった。

『文字の歴史 ヒエログリフから未来の「世界文字」まで』

アルファベットにはなぜ大文字と小文字の二種類あるのか気になっていた。初期の頃は大文字だけで書物体と筆記体の二種類があり、筆記体が後に小文字となったらしい。

『一般言語学講義』フェルディナンド・ソシュール

言語で重要なのは音と概念の二重分節とか、シニフィアンシニフィエの結びつきが恣意的であること、シニフィアンが線的であることなど。日本語で「示すもの」っていうと主語なのか目的語なのか分からないので分かりにくい。

記号論入門 記号概念の歴史と分析』ウンベルト・エーコ

記号とは何かを示すもの。それ以外のことは良く分からなかった。

『パースの思想 記号論認知言語学

良く分からなかった。

ようこそ実力至上主義の教室へ3』衣笠彰梧

自由が丘駅近くのブックオフに初めて行った時に買った。無人島でのサバイバル試験の回。最後の場面が好き。

精神分析学入門・上』ジグムント・フロイト

表象文化論Aの講義を聴いていて、無意識について考えるようになった。下は読まなかった。

『ゾウの時間ネズミの時間 サイズの生物学』

この頃は時間の問題を考えてた。時間は時計によって計られる。例えば振り子時計など。振り子の運動方程式を立てて、近似的に解いてやると調和振動になって振り子の周期が$T = 2\pi\sqrt{l/g}$となる。だけど、そもそも運動方程式に$t$が含まれているから一瞬悩んだ。結局これは問題ではないけど、今度は物理的時間と心理的時間の関係がどうなってるのかが気になって、体内時計とか生物の時間について調べるようになった。面白い話題が多かったけど、時間に関する章は一部だった気がする。

チャーチルの昼寝 人間の体内時計の探求』

時間や体内時計について幅広い視点から論じられている。関係ないけど、リンネの花時計というものが出てきて、アートっぽくてかなり感動した。

量子力学史Ⅰ』

量子化学の講義が始まったので、量子力学のpdfを書いたり歴史を調べたりした。熱放射の問題からプランクの公式が発見されるまでの経緯とか水素スペクトルの理論が整備されていった様子が分かる。物理学全体が量子論に取り掛かっていた中、重力の理論を考えていたのは本当にアインシュタインくらいだったのだろうなという印象を受けた。水素原子の理論では、ボーアの量子条件やそれを拡張したゾンマーフェルトの量子条件、天体力学のテクニックを持ち込んだりとかなり試行錯誤があったらしい。

ピカソ 二十世紀美術断層』

評論一般に言えることだけど、作者の動機を外部に求めすぎな気がした。

セザンヌ論 その発展の研究』

あまり覚えてない。

『絵画空間を考える』

遠近法的な絵画が近代に入ってどのように変化していったか。

『まなざしのレッスン2 西洋近代絵画』

ボードレールが主観的な美を提唱してから絵画の題材も手法も変化した。写真成立によって絵画そのものの存在が強調されていった。印象派から、象徴主義キュビスムなどを経て抽象絵画へと向かっていった。これも『観察者の系譜』と関連していて、『フェルメールと天才科学者』よりも美術に寄った内容だった。

量子力学史Ⅱ』

行列力学波動力学が誕生してから数年で急速に量子力学の基礎が整備されていったことが分かる。これらの理論は、前期量子論にはなかったもので、零点エネルギーやシュタルク効果の説明などを含んでいた。ハイゼンベルクシュレーディンガーはかなり哲学の素養があった人で、黎明期から哲学的な議論が生まれていたらしい。既に意識に関する問題に言及していたのは意外だった。

『時間と空間』エルンスト・マッハ

空間をアプリオリな認識としてカントに対して、マッハは経験的な感覚とした。確かに人類は長い間非ユークリッド空間を知らなかった。こういった話から宇宙が非ユークリッド的である可能性にも言及していたのだけど、この考え方は一般相対性理論の基本的なアイディアだったので驚いた。アインシュタインはマッハに随分影響を受けたようだけど、かなり凄いことを言ってたので納得した。

『開眼!JavaScript 言語仕様から学ぶJavaScriptの本質』

ウェブアプリをjsで作ろうと思って一応借りた。

『コーディングを支える技術 成り立ちから学ぶプログラミング作法』

スコープや型などの多くのプログラミング言語に共通する概念の歴史。

エッシャー・マジック だまし絵の世界を数理で読み解く』

錯視やエッシャー風タイリングの自動生成について調べてた。

ベルグソン全集1 時間と自由/アリストテレスの場所論』

『時間と自由』は時間や空間、物体や数について、意識の問題。所々理解できる箇所はあったが、全体では良く理解できていない。

ショーペンハウアー全集1 根拠律の四つの根について/視覚と色彩について』

感性と悟性による視覚の描像が分かりやすく説明されていて、視覚の主観的な面が良く分かった。ショーペンハウアーは色彩を眼の内部で起こる現象として考察した。かなりカントを研究していたらしいが、一方でドイツ観念論の哲学者に対してはほぼ悪口を言ってた。

『楽しみながら実力が身に付く 風景デッサンの基本』

風景を描いてみたかったが、形が複雑で難しい。

『心の研究史

心理学の全体的な流れを追ったもの。知識が足りないため良く理解できなかった。

『探る表現 東大生のドローイングからみえてくる創造性』

二番目に出てきた学生の絵が結構好みだった。

『ヴィジュアル・コミュニケーションの歴史』ウィリアム・アイヴィンス

グーテンベルクの銀河系』に引用されていた気がする。内容も似ていて、学問の発展における図版の役割とか、版画の大量生産による経済や文化の変化など。

アインシュタインの世界』

久し振りに読み返した。昔は知らなかった哲学者や思想家の名前が出てきて面白かった。

FPGAの原理と構成』

情報科学の達人で買ってもらった本をずっと積読していたけど、論理合成が面白そうだったので読み始めた。FPGAの構成も多少理解した。

『講座心理学 4知覚』

心理学科の人はこういう本で勉強するんですかね。

『光学の原理I 電磁光学および幾何光学』マックス・ボルン、エミール・ウォルフ

幾何光学も以前から勉強したいと思ってた。思ったより難しかった。

『知能の心理学』ジャン・ピアジェ

ピアジェによる知能の発達の説明。

『歴史の終わり(上・下)』フランシス・フクヤマ

プラトンアリストテレスは政治体制は定期的に循環していくと考えていた。近代になって、国家体制には終点があり、あらゆる国家は最終的にはその唯一の体制へと収斂していくという主張がされ始めた。ヘーゲル進歩史観では近代自由主義であり、マルクスの場合は共産主義だったが、本書ではリベラルな民主主義がそのような終着点であると主張する。これを読むだけでヘーゲルマルクスの思想にも触れることができるのが良いと思った。後半は話が曖昧になった気がした。

ナショナリズムの歴史と現在』

政治学Aの期末レポートを近現代日本ナショナリズムというテーマで書く必要があったので、参考文献として読んだ。

『生成Deep Learning 絵を描き、物語や音楽を作り、ゲームをプレイする』

生成タスクに関する機械学習の本。画像生成の章を参考にVAEやGANなどを実装した。喩え話で説明してるんだけど分かりにくいと思う。

『やさしい顔と手の描き方 基礎から学ぶ頭部と手の描き方』

顔の立体感を意識しましょうってなった。

『明るい部屋:写真についての覚書』ロラン・バルト

明るい部屋(カメラ・ルシダ)。写真の評論。面白くなかった。

『ダブル・ジョーカー』柳広司

GYAOジョーカーゲームが無料配信されてたので丁度良い機会と思って読んだ。スパイ視点で思考が分かるのも良いが、別の人物の視点から書くのもミステリアスで良い。

『言語・思考・現実』ベンジャミン・ウォーフ

有名な言語相対論(サピア=ウォーフ仮説)の古典。漠然とした理解では物足りなくなったので本人の著作を読んでみた。

ウォーフは言語による表現の違いを指摘して、思考様式が異なると結論していた。ここには表現が異なれば思考も異なるという前提が含まれているような気がして同義反復に陥っていると感じた。編者解説にも全く同じ意見が出てきた。言語と思考の関係を実証する研究はほとんど無いらしいので、あまり強く主張できる説ではないなあと思った。

この本で取り上げられているのは主に言語学の話だけど、自分が知りたいのは心理学的なもっと実証的な話だと思った。例えば、色を識別するときに出力となる語彙に従ってNNが変更されると言われれば、それはダイレクトに言語が知覚(思考)に影響を与えていると納得できる。

『現代微分幾何入門』

また微分幾何を勉強したくなってきたので借りてきた。pdfもかなり加筆修正した。抽象論で理解できてない部分もあるけど面白かった。

『曲線と曲面の微分幾何』小林昭七

有名なやつ。ガウス=ボネの定理の証明が『現代微分幾何入門』に載っていなかったので参考にした。3次元空間内の曲線や曲面については以前勉強していたので、割と早く読み終わった。

『言語が違えば、世界も違って見えるわけ』

色覚と色彩語彙に関する研究の歴史を詳細に追っている。20世紀には心理学実験も行われ、言語相対論の主張にも部分的には証拠が与えられている。主張の強い部分についてはかなり批判的なことを言ってるので、考えにバランスが取れるんじゃないかと思う。

『生物から見た世界』ヤーコプ・フォン・ユクスキュル、ゲオルク・クリサート

生物の感覚や時間空間に対する考察。思っていたよりもずっと認識論や哲学よりの本だった。

Web Speed Hackathon 2022 for Students 参加記

3/5-6の二日間にかけて Web Speed Hackathon 2022 for Students に参加しました。Web Speed HackathonというのはWebサイトのパフォーマンスをチューニングするコンテストです。学生限定なので参加者は40人とかだった。

www.cyberagent.co.jp https://github.com/CyberAgentHack/web-speed-hackathon-2022

準備

Herokeでデプロイ

まずリポジトリをforkする。なんも分からんのでREADME.mdにある通り取り敢えずHerokeでデプロイすることにする。下の記事を参考にした。 qiita.com ちなみに自動デプロイしようとしたけどなんか反映されなかったので手動デプロイでやっていた。URLが取得できたらlearderboardのissueから参加登録する。 初回計測がこれなんですけどなぜか高く出てしまって最後まで超えられませんでした(泣)。 f:id:season1618:20220306191825p:plain

手元で実行

リポジトリをcloneする。yarn installしようとしたら問題発生。

PS C:\Programming\web-speed-hackathon-2022> yarn install
yarn : このシステムではスクリプトの実行が無効になっているため、ファイルC:\Users\user\AppData\Roaming\npm\yarn.ps1 を読み込むことができません。詳細については、「about_Execution_Policies 」(https://go.microsoft.com/fwlink/?LinkID=135170) を参照してください。
発生場所 行:1 文字:1
+ yarn add react-image
+ ~~~~
    + CategoryInfo          : セキュリティ エラー: (: ) []、PS 
SecurityE    xception
    + FullyQualifiedErrorId : UnauthorizedAccess

qiita.com 実行ポリシーがそのままだった。forkしたリポジトリだとこうなるぽい?Set-ExecutionPolicy -ExecutionPolicy RemoteSigned -Scope Processしたらできた。

ところがlocal hostにアクセスしたらUncaught ReferenceError: exports is not definedと出てしまいページが表示されない。Slackで別の学生が同じ報告をしていた。Windowsに起因する問題だったらしく、新しくpushされたもので実行できたら表示された。やっと競技開始です。

競技

コードを読んで取り敢えずReactが使われてることだけは分かった。

Reactコンポーネントを関数コンポーネントの外に置く

トップページ開いたらThe component styled.button with --- has been created dynamically.がたくさん出てきたので、定義を関数コンポーネントの外に置きました。改善にはなるけどスコアには大きく影響しないそうです。

画像の読み込みを何とかする

TrimmedImageの読み込みが遅かったので色々やろうとしたんですが上手くいきませんでした。サブピクセルレンダリングという言葉を覚えて整数座標にしたりしてた。

canvas の最適化 - Web API | MDN

HTML5 canvas のパフォーマンスを向上させる - HTML5 Rocks

それ以外

以下の記事を読んで試行錯誤したのですが、結局何もできませんでした。知識が浅いな~。

zenn.dev trap.jp

結果

次あったらもっと良い結果を出せるように頑張りたい。 f:id:season1618:20220306191038p:plain traPの先輩が上位に入っていて凄いなあと思った。

ICPC2021国内予選参加記[jss_tech]

国内予選 | ICPC 2021 Asia Yokohama Regional

東工大B1の jupytor + season + saiten / jss_tech で出場しました。

traP(東京工業大学デジタル創作同好会)内でチーム練習を3回やって、模擬国内予選にも出た。

本番は大学の講義室を借りてやりました。自分は講義室に辿り着くのに手間取ったので少し遅れてしまった。自分が来たときには saitenさんがA問題、jupytorさんがC問題に取り組んでいたので、自分はB問題をやることにした。考察は簡単で、グラフ作ってdfsして全ての頂点通ればYES、違ったらNOになる。1WAしてしまった。先にAを解き終えたsaitenさんがD問題に取り組んでいたのですが、もう難しそうなので自分もDを考えることにしました。C問題も実装がなかなか難しそうで、順位表を見てみるとCよりDの方が解かれてたのでjupytorさんも途中でDを考えたりしました。その後も二人はC,D,Eを行ったり来たりする一方、僕はずっとDを考えていたのですが、結局分かりませんでした。終了15分前くらいに、bi <= 50なのでそれぞれの数値をカウントしてdfsでできそうな気がして実装したけど間に合わず(結局間違ってた)。

結果はAB2完で121位でした。来年までに強くなりたい。

f:id:season1618:20211105193233p:plain

終了後に同学er何人かとエンカしました。多分全員初対面だった。

純LISPインタプリタを作る

C言語で純LISPインタプリタを作りました。 github.com

LISP

LISPLISPの方言で、ごく少数の基本的な関数やプリミティブからなる。コンパイラとかは作ったことなかったけど、純LISPなら記述が少なくて済むだろうなと思って作ってみた。

LISPには二種類のデータ型アトムとペアがある。ペアは二つのデータのペア。アトムはペアでないもの。真偽値はt,niltrue,falseに対応する。ABのペアを(A . B)と表す。またリスト(A B C)(A . (B . (C . nil)))という風に入れ子にしたペアの略記とみなす。純LISPの要素は人によって異なるが、今回は以下の関数

  • atom 値がアトムのときt
  • eq 二つの値が等しいときt
  • car ペアの左側
  • cdr ペアの右側
  • cons 二つの値のペア

と特殊形式

のみからなるとする。

データの表現

LISPのリストは以下のようなコンスセルで表現される。

リスト`(A B C)`
しかしこのままでは各要素がアトムなのかペアなのか判定できない。そこで隣接する二つのアドレスp, p + 1を用いてデータを表現し、pで表すことにした。アトムの場合はpにその値を格納し、p + 1に0を格納する。ペアの場合はpにcarのアドレス、p + 1にcdrのアドレスを格納した。C言語ではメモリ0番地に値を書き込むことは基本的にできないらしいので、多分これで識別できそう。アドレスはlongなのでポインタの型はlong*で統一した。例えば((A B) C) となる。ただしtには1,0をnilには0,0をそれぞれ格納する。つまりt = 1,nil = 0。またnilと空リスト()も等しい。(実際はどう割り当てるのが良いんだろう)

構文解析(parse.c)

まず全体をexprに渡す。空白と改行は無視して、(が来たらparentheses、それ以外の文字が来たらnumbersymbolに渡す。)が来て括弧の収支が合ったら終了。parenthesesでは括弧の収支が合うまでexprで読む。

long* parentheses(){
    long *begin = calloc(2, sizeof(long));
    long *p, *q; p = begin;
    int cnt = parentheses_count - 1;
    while(true){
        *p = (long)expr();
        if(eq(p, nil) == t){
            return begin;
        }else{
            q = calloc(2, sizeof(long));
            *(p + 1) = (long)q;
            p = q;
        }
        if(cnt == parentheses_count) return begin;
    }
}

long* expr(){
    char c;
    while(!feof(fp)){
        c = fgetc(fp);
        if(c == EOF) return nil;
        if(c == ' ') continue;
        if(c == '\n'){
            line_number++;
            continue;
        }
        if(c == '('){
            parentheses_count++;
            return parentheses();
        }else if(c == ')'){
            parentheses_count--;
            if(parentheses_count < 0){
                printf("error %d : parnetheses don't correspond.\n", line_number);
            }
            return (long*)0;
        }
        else if('0' <= c && c <= '9') return number(c - '0');
        else return symbol(c);
    }
}

評価(eval.c)

読み込んだ結果をevalに渡す。evalの中身を順番に見ていく。 まず文字列がt,nilに一致したらそれを返す。

    if(equal(p, "t")) return t;
    else if(equal(p, "nil")) return nil;

次に宣言された変数名に等しければその値を返す。varが変数名の配列、valueが値の配列となっている。

    for(int i = var_count - 1; i >= 0; i--){
        if(eq(p, var[i]) == t) return value[i];
    }

それ以外の場合は最初の要素が関数や特殊形式なので、関数名tokenと引数argsに分ける。

    long* token = car(p);
    long* args = cdr(p);

基本関数の評価。

    if(equal(token, "atom")) return atom(eval(car(args)));
    else if(equal(token, "eq")) return eq(eval(car(args)), eval(car(cdr(args))));
    else if(equal(token, "car")) return car(eval(car(args)));
    else if(equal(token, "cdr")) return cdr(eval(car(args)));
    else if(equal(token, "cons")) return cons(eval(car(args)), eval(car(cdr(args))));

特殊形式の評価。quoteについては引数をそのまま返す。lambdaは引数の組と処理の内容を返す。definevar,valueに変数を登録する。

    if(equal(token, "cond")){
        while(eq(args, nil) == nil){
            long* condition = car(car(args));
            long* expression = car(cdr(car(args)));
            if(eval(condition) == t) return eval(expression);
            args = cdr(args);
        }
        return nil;
    }
    else if(equal(token, "quote")){
        return car(args);
    }
    else if(equal(token, "lambda")){
        return args;
    }
    else if(equal(token, "define")){
        var[var_count] = car(args);
        value[var_count] = eval(car(cdr(args)));
        var_count++;
        return value[var_count - 1];
    }

最後にラムダ式の展開。tokenがそれ以前に登録したラムダ式の名前に一致するとき、引数を評価してvar,valueに加えた上で、ラムダ式の内容をevalで評価する(defineで定義した変数とラムダ式の引数は分けた方が良いかもしれない)。再帰呼び出しする場合は引数の名前を複数登録することになるが、evalの冒頭で新しい順に変数名を照合しているので問題ない。

        for(int i = var_count - 1; i >= 0; i--){
            if(eq(token, var[i]) == t){
                token = value[i];
                break;
            }
        }
        long* params = car(token);
        int n = 0;
        while(eq(params, nil) == nil){
            var[var_count] = car(params);
            value[var_count] = eval(car(args));
            var_count++;
            n++;
            params = cdr(params);
            args = cdr(args);
        }
        long* ret = eval(car(cdr(token)));
        for(int i = 0; i < n; i++){
            var_count--;
            var[var_count] = 0;
            value[var_count] = 0;
        }
        return ret;

テスト

バグってるかもしれないけど。sample.lisp

(quote 1)
(quote (1 2 3 4))
(atom (quote 1))
(atom (cons (quote 1) (quote 1)))
(eq (cons (quote 2) (quote 3)) (cons (quote 2) (quote 3)))
(car (cons (cons (quote 1) (quote 2)) (quote 3)))
(cdr (cons (cons (quote 1) (quote 2)) (quote 3)))
(cond
    ((eq (quote 1) (quote 1)) (quote 2))
    ((quote t) (quote 3))
)

(define inc (lambda (x) (cons (quote 1) x)))
(inc (quote (1 1)))

(define append
    (lambda (x y)
        (cond
            ((eq x nil) y)
            (t (cons (car x) (append (cdr x) y)))
        )
    )
)
(append (quote (1 2 3)) (quote (4 5 6 7)))

(define f (lambda (x) (cons x (quote 2))))
(define g (lambda (f x) (f x)))
(g f (quote 3))

に対して実行すると

> .\lisp sample.lisp
1
1 2 3 4 0
1
0
1
1 2
3
2
((120 0) 0) ((99 111 110 115 0) ((113 117 111 116 101 0) 1 0) (120 0) 0) 0
1 1 1 0
((120 0) (121 0) 0) ((99 111 110 100 0) (((101 113 0) (120 0) (110 105 108 0) 0) (121 0) 0) ((116 0) ((99 111 110 115 0) ((99 97 114 0) (120 0) 0) ((97 112 112 101 110 100 0) ((99 100 114 0) (120 0) 0) (121 0) 0) 0) 0) 0) 0
1 2 3 4 5 6 7 0
((120 0) 0) ((99 111 110 115 0) (120 0) ((113 117 111 116 101 0) 2 0) 0) 0       
((102 0) (120 0) 0) ((102 0) (120 0) 0) 0
3 2

となる。リスト末尾のnil(0)が表示されてる。ごちゃごちゃしてるのはdefineとかlambdaの返り値で、文字コードをそのまま出力している。

関連文献

簡易LISP処理系の実装例【各言語版まとめ】

簡易LISP処理系の実装例(C言語版)

ICTSC2021夏の陣参加記[osushi]

icttoracon.net 8/28,29に開催されたICTトラブルシューティングコンテストにanko氏, fomidtk氏, seasonの三人で参加しました。ネットワークとか分かるんですか??いいえ。本番二日前にあるよって言われたときは、「過去の自分、こんなものに手を挙げたのか」と思った。

一日目

最初は皆で14 Webサーバが立ち上がらないを読んだ。Pythonモジュールがないのでinstallするのかなあと分かった。偶然にもつい最近Pythonを始めたので「分かった。凄い」となった。この問題はfomidtkさんが回答を作成しました。

その後は三人で別々の問題を考えた。9 止まらないを見るも全然分からない。ankoさんの指示通りにMakefileのコマンドにオプション-t -iを付けるとなんか分からんけどできる。ところがankoさんもよく分からないそうなので自分が調べることに。ICTSCはトラブルを解決するだけではだめで、原因とか対策をちゃんと説明しないといけないのです。そもそもdockerが何か知らないのに分かるかーと思いつつググってみると次のページを見つけた。 docs.docker.jp qiita.com ふむふむ。普通にdocker runをやると標準入力が使えないけどこのオプションを付けると使えるようになる、と理解して次のような回答を作成した。

お世話になっております。チームosushiです。

この問題ではdockerの起動中に標準入力が機能しないことが原因でトラブルが発生したと>考えられました。

そのため、docker runのオプション

-t, --tty : 疑似ターミナルの追加

-i, --interactive : コンテナのstdinにアタッチ

を追加することで正しく動くことを確認いたしました。

確認のほどよろしくお願いします。

手順

1./home/user/test/Makefileの編集

変更前:docker run --rm -v $(PWD)/:/go/src/app -w /go/src/app -p 8080:8080 golang:latest go run main.go

変更後:docker run --rm -t -i -v $(PWD)/:/go/src/app -w /go/src/app -p 8080:8080 golang:latest go run main.go

20分後に見てみると無事50点を獲得。やったね。

その後も問題を考えたが何も分からず。もはや自分に分かる問題はなかった。 f:id:season1618:20210829155917p:plain f:id:season1618:20210829155853p:plain

二日目

問題は一日目と同じです。もう分かるやつがないのでその場でネットワークのお勉強を始めました。結果何も分かりませんでした。すみません... f:id:season1618:20210829162649p:plain f:id:season1618:20210829162232p:plain 一位と二位のチームだけずっと不動だったの凄い。

感想

コンテストは両日とも10:00-16:30の6時間30分でした。つらーい。大学入って初めての大会だった。

2020年度の読書記録

2020年1-3月も含む。全体的に内容を覚えていない。

シャーロック・ホームズの推理学』

ホームズがどういう風に推理してるかを分析してる。

Excelで分かるディープラーニング超入門』

この時期にN予備校の教材が公開されてて、機械学習のやつを読んでた。

『正多面体を解く』

多面体の話。

愚者のエンドロール米澤穂信

丁度この時期に『氷菓』の再放送がやってて、自分も二回目だけどアニメと並行して小説も読もうとなった。

生物と無生物のあいだ福岡伸一

動的平衡で知られてる人の本。

すべてがFになる森博嗣

文章や言葉選びから独特な思考が感じられて良かった。これ読んだ後にアニメをもう一回見た。

『生命の物理』

様々な生命現象の数理を扱っている。固体内の分子の運動、神経系のモデル、個体数の変動を扱うロトカ=ヴォルテラ方程式とか。チューリングの形態形成の研究とか正規表現オートマトンが対応するという話とか、情報科学の話も出てきて面白かった。

『熱・統計力学

印象に残った文をメモしておいた。

仕事と熱の区別がどの程度のスケールの自由度でされるかに依存せず、仕事と熱に関する一意的な法則が成立するのであって、この意味において熱力学的あるいは巨視的な法則も客観性をもつのである。

レオナルド・ダ・ヴィンチの世界』

高三の4,5月とはいえコロナで暇ができたので本読んでた。 レオナルドの仕事を解剖学・数学・天文学・土木・絵画など、色々な分野について分析している。それから手稿そのものを取り上げていたのが面白かった。レオナルドに限らず、昔の人間が何を知っていて何を知らなかったのかを知るのは面白い。

クドリャフカの順番米澤穂信

古典部」シリーズでは文化祭の話が一番好き。古典部4人の視点が次々と切り替わるの文化祭のごちゃごちゃ感があって良い。

ソードアートオンライン アインクラッド川原礫

SAOはアインクラッドが一番好き。命がけだからエモくなるんだよなあ。アニメ版とは構成が異なり、いくつかの話が2巻に回されている。

『情報トレーニング』

競プロっぽいパズルの問題があって面白かった。

化学の教科書

化学の教科書を通読した。時間の無駄だった気がする。

『古文の読解』

こんなの読んでる暇あったら古文単語を覚えような。

竹取物語

高畑勲監督の「かぐや姫の物語」が面白かったので読んでみた。

『物質と光』ルイ・ド・ブロイ

光学の歴史とか量子力学について。

『幕末思想集』

色々な人が開国・倒幕を主張した本をまとめたもの。

方丈記鴨長明

旅したいってなった。

岡潔 数学を志す人に』岡潔

『春宵十話』など。自分の思考を分析していたのが興味深い。理解はできなかったけど。

国家の品格藤原正彦

数学者である著者のベストセラー。

『色彩学概説』

眼の構造から色の物理的・心理的性質について。色を表現するための体系など。

レオナルド・ダ・ヴィンチの手記(上・下)』レオナルド・ダ・ヴィンチ

レオナルド・ダ・ヴィンチの世界』のほとんどの章でこの本が参考文献に挙げられてたので読んだ。遠近法の説明や絵の上達について。寓話をたくさん書いてたのが意外だった。それから地理や天文学の細かい記述があった。科学については、ガリレオ以前ということもありアリストテレスの影響を受けていたようだ。

奥の細道松尾芭蕉

平安より江戸の古文の方が読みやすい。

『日本人の美意識』ドナルド・キーン

幽玄の話とかだった気がする。

キノの旅 the Beautiful World時雨沢恵一

アニメを完走したので小説も読んだ。世界観が好き。

『絵画論』レオン・バッティスタ・アルベルティ

遠近法の解説など。

ようこそ実力至上主義の教室へ衣笠彰梧

綾小路の性格がアニメと違う。堀北のツンデレが良い。

星の王子さまアントワーヌ・ド・サン=テグジュペリ

読んだことなかったので。

冷たい密室と博士たち森博嗣

すべFの続編。

『魔法の世紀』落合陽一

再読。以前よりは理解して読めたのではないか。