今朝起きたら、とんでもない論文を見つけました。 Othello is Solved ゲームの オセロが"解かれた(弱解決)" というのです。飛び起きました。それで、16時まで二度寝してから読みました。 注意すべきは、この論文が査読を経て公開されているわけではないこと、つまり形式上特にチェックを受けたものではないことです。ただ、タイトルからして非常に衝撃的ですので、個人的に読んでみました。この記事では、私がこの論文(およびソースコード)を読んでわかったことを、なるべくわかりやすくまとめます。随時更新します。 余談ですが、このタイトルはどうやら、チェッカーというゲームが以前弱解決された際の論文"Checkers Is Solved"のオマージュだろうという話です。 この記事には専門用語が出てくるので、最後の方に基礎知識として重要な用語や知識をまとめました。 お詫びと訂正 この記事の内容は、私が

1. 第3次AIブームの到来 米Google DeepMindが開発した人工知能（AI）の囲碁プログラム「AlphaGo」が世界トップレベルの実力を持つ韓国のプロ棋士、李世ドル（イ・セドル）九段に4勝1敗と大きく勝ち越したことが着火剤となり、2015年より第3次AIブームへと突入した。(ちなみにAIが誕生したのは1950～1960年代で第1次AIブームの到来) 1.1 余談になるがAlphaGo(4億円の知能)はなぜすごいのか？ AlphaGoがそれ以前のチェスや将棋のAIと異なるのは、 畳み込みニューラルネットワーク（CNN） を応用している点だ。このCNNはさらに強化学習を行い、自分自身と対局を数千万回も繰り返した。 間違っていたらすみません、、、、 1.2 ChatGPTによる生成AIのブーム ChatGPTに代表されるLLMは以前から開発競争が繰り広げられていた。 GPT1は201

ゴールデンウィークのはじめ（4月29日）に投稿された以下のツイートですが、5月7日20時において、1,938.8万件の表示ということで、非常に注目されていることが分かります。 我が名はアシタカ！スタバのFreeWi-Fiを使いながら会社の機密情報を扱う仕事をしてたら全部抜かれた。どうすればよい！ pic.twitter.com/e26L1Bj32Z — スタバでMacを開くエンジニア (@MacopeninSUTABA) April 29, 2023 これに対して、私は以下のようにツイートしましたが、 これ入社試験の問題にしようかな。『スタバのFreeWi-Fiを使いながら会社の機密情報を扱う仕事をしてたら全部抜かれた』と言う事象に至る現実的にありえる脅威を説明せよ。結構難しいと思いますよ。 https://t.co/LH21zphCTV — 徳丸 浩 (@ockeghem) April

はじめまして。mayocornです。 先日のABC281で青コーダーになりました！ 経歴 20代の主婦。旦那は競プロやってないです。 中学卒業→高校入学→高校中退→バイトを転々とする（ITに関してはSESで半年ほど働いた経験あり）→今の住所に引越してきてからは無職 趣味はゲームで、最近やっているタイトルはファイアーエムブレムエンゲージ、Splatoon3です。音ゲーやカードゲームに熱中してた時期もありました。CHUNITHMは旧レートでベスト枠15.3くらい。でものめりこむほどお金がかかるのでやめました。競技プログラミングは何問解いても無料なので続けられてます。 学力に関して話すと、高校数学は確率、論理と集合がちょっとわかるくらいで三角関数、微分積分、行列あたりは全然分かりません。青パフォーマンスをとるのにこのへんの知識が必要になったことはなかった気がします。（私が参加した回の中では） 競

オセロAIを作り始めた日のこと あれは2021年4月のこと、今思い返せば偶然が重なって起きた出来事でした。 第一の偶然は、ゲームAI(ゲームを自動プレイするAI)世界4連覇の方になぜかゲームAIの初歩的な話を30分程度教わっていたことです。 第二の偶然は、Twitterの知り合いが「オセロソフトRTA」なる競技をやっているのを目にしたことです。なんじゃそりゃ、と思った私はすぐに、その競技が 「オセロで遊ぶプラットフォームをどれだけ早く作るか」を競うものだとわかりました。 面白い、やってみよう。 YouTubeでライブ配信しながら、私はオセロソフトRTAをやってみました。その時のライブはこちら。3時間で完成できれば良いと思っていたのですが、思ったよりも早く終わってしまいました。 オセロAIでも作るか。 こうして私のオセロAI制作が開始しました。 何をしたら良いかわからなかった オセロAIを作

2023年AtCoder言語アップデートにより、Rustの環境は大きく変化しました。そのため、本記事はフリーズさせ、後日、2023年版に対応した記事を新規作成したいと思います。 筆者は、競プロのアルゴはPythonを使いつつ、マラソンはRustを使っております。前者は発想を短時間にコードにすることを重視し、後者はコーディングに時間をかけてでも高速性を確保したいからです。 その際、Pythonでできたアレを、Rustでどう書くんだっけ、と悩むことが多く、悩んだ結果を自分メモを兼ねてTipsにすることにしました。競プロに出てくるパターンを多く収録していますが、競プロ目的以外でも参考になるかと思います。とりありず、ざっと記述してみましたが、そのうち増やしたり、章立てを変えたりするかも知れません。 なお、参照がーとかトレイトがーとか、Rustそのものの入門には言及していませんので、適宜、別の記事や

0. アルゴリズムとは？ まず、アルゴリズムとは何かを説明します。（0 節の説明はスライド「50 分で学ぶアルゴリズム」 の説明を参考にして書きました） さて、次の問題を考えてみましょう。 問題： 1 + 2 + 3 + … + 100 の値を計算してください。 単純な方法として、式の通りに 1 つずつ足していく方法が考えられます。すると、以下の図のように答えが計算されることになります。 これで答え 5050 が正しく求まりました。これはれっきとした アルゴリズム であり、この問題を 99 回の足し算 で解いています。しかし、計算回数が多く、計算に時間がかかるのではないかと思った方もいると思います。 ここで、方法を変えて、「1 + 100」「2 + 99」「3 + 98」…「50 + 51」の合計を求めることで、1 + 2 + 3 + … + 100 の値を計算してみましょう。 50 個の

0. はじめに こんにちは、大学 1 年生になったばかりの E869120 です。本記事は、 アルゴリズム・AtCoder のための数学【前編：数学的知識編①】 アルゴリズム・AtCoder のための数学【中編：数学的知識編②】 からの続きです！！！ ※前編・中編を読んでいなくても理解できる、独立したトピックになっているので、ご安心ください。 後編から読む方へ 21 世紀も中盤に入り、情報化社会が急激に進行していく中、プログラミング的思考やアルゴリズムの知識、そしてアルゴリズムを用いた問題解決力が日々重要になっています。 しかし、アルゴリズム構築能力・競プロの実力は、単純にプログラミングの知識を学ぶだけでは身につきません。近年、数学的なスキルが重要になりつつあります。実際、私はこれまでの経験で「数学の壁で躓いた競プロ参加者」をたくさん見てきました。そこで本記事では、 AtCoder のコン

Register as a new user and use Qiita more conveniently You get articles that match your needsYou can efficiently read back useful informationYou can use dark themeWhat you can do with signing up

この記事でお題にするのはCPUレジスタ上の整数除算です。以下、単に除算とも書きます。 除算は非常に高コストな演算なため、コンパイラは最適化によって、できるだけ整数除算を別の計算に置き換えようとします。 最適化ができる場合の一つとして、割る数が定数である場合があります。頭のいいコンパイラは、除算を乗算とビットシフト等を駆使した演算に置き換えます。この記事では、そういった最適化の背景にある理屈を部分的に解説します。 計算機環境としてはモダンなx86 CPUを仮定します。したがってレジスタは32/64ビットであり、負数は2の補数表現になっています。ある程度は他の命令セットでも通用する話になっているかもしれません。 そもそも整数の除算とは プログラミングにおける整数の除算の定義について確認します。整数$n$を整数$d$で割るとき $$ n = q \times d + r $$ が成り立つように除

昨年非常に盛り上がっていましたので作成させていただきました。 本番環境でやらかしちゃった人のアドベントカレンダーです。 例） 本番DB吹き飛ばした 本番サーバをデストロイした ネットワーク設定をミスって本番サーバにアクセス出来なくなり、サーバが世界から孤立した などなど... 以下の２点については必須項目なので、記述お願いします。 惨劇はなぜおこってしまったのか 二度と惨劇を起こさないためにどうしたのか もう二度とあの惨劇を繰り返さないために、みなで知見を共有しましょう。 過去 本番環境でやらかしちゃった人 Advent Calendar 2019

はじめに みなさん。Pythonで型書いてますか？最近は型の重要性を再認識しているので、皆さんにもぜひPythonで型を書いて頂きたいと思ってこの記事を書きました。 注意事項として今回の記事では下記の事項については言及しません。 型チェックツールの導入方法(mypy,pyrightなど) 今回の内容は以前の書いた記事の補足内容となっていますので、以前の記事ももしよければ参照ください。 実践！！Python型入門(Type Hints) そもそもPythonでなぜ型を書くのか？ Pythonは動的型付き言語なので、型を書かなくてもプログラムは動きます。型を書かないことで、コードの量は少なくなりますし、初学者にとっても習得しやすい言語となっていることはメリットかと思います。 ただし、ある程度の行数のコードを書く場合、プログラムを複数人でメンテナンスする場合、型がないと以下の様な問題が発生する。

はじめに 本投稿は『VSCodeが最強のエディタだ!!』などといったことを伝える記事ではありません。 数あるエディタの中の『VSCode』に焦点を当てて、作業効率化できるための使い方をまとめたものです。 いくつかのテーマに分けて、ご紹介させていただきますので、興味のあるところを拾い読みしていただければと思います。 (スクリーンショットについては、随時更新させていただきますが、古い場合があります。ご容赦ください。) 1.ショートカット ショートカットはかなりの数があるので、今回は『1日の作業の中で登場頻度が多そうな操作』に焦点をあてて、効率化を目指していきます。 ショートカットを覚えることで、ある程度の操作はマウスに触らずにできるようになります。 1つ1つの効果としては微々たるものですが、操作頻度の多いものであればあるほど、効果が期待できるので、覚えることをオススメします！ VSCodeを閉

概要 チームによる継続的開発を前提としたコーディングのガイドライン。 特定の言語を対象としたものではないが、主に静的型付けのオブジェクト指向言語を想定している。 サンプルコードは別段の定めがなければSwiftで記載。 ガイドラインの目的 生産性を高め、メンテナンスコストを下げる バグが生まれづらくする 開発メンバー（特に新規参加者）がコードを理解しやすくする 初心者プログラマーの教育 内容の説明 タイトルの頭についた【数字】は重要度。 高いほどシステムに与える影響が大きいが、低いものの方が影響が小さく改修しやすいものが多い。 【5】変数のスコープを小さくする 変わり得る値は複雑さを生み誤解やバグに繋がるため、プログラムは変数が少ないほど問題が生まれづらい。 プログラミングの大原則として、変数は必要最低限を心がけ、むやみに増やさないようにする。 また、変数はスコープや寿命が大きいほど悪影響が

はじめに これまでも「Setting Sync」という拡張を入れることで、複数のVisual Studio Codeの設定を同期することは可能でした。ただGithubやGistの設定がやや面倒な側面があり、初期設定が煩雑でした。 しかしVer.1.48でついに公式の設定同期機能「Settings Sync（紛らわしいですがこちらは複数形）」がリリースされました。以下の内容が同期可能です。 設定 キーボードショートカット ユーザースニペット 拡張機能 UIの状態（表示言語、アクティビティバー、パネル、画面レイアウト、コマンド履歴、同一通知の抑止） ここではその簡単な使い方と、何ができるのか簡単にまとめたいと思います。 なお公式ドキュメントはこちら。 https://code.visualstudio.com/docs/editor/settings-sync 事前準備 設定の同期を利用するた

最後に、17 章で PとNPに関する話題を解説し、世の中には「効率的に解くアルゴリズムを設計することができそうにない難問」が多数あることを見ます。18 章で、これらの難問に取り組むための方法論をまとめます。 競プロをやっている方向け 扱っている題材の難易度については、こんな感じのイメージです！ チーター本　<　本書　=　螺旋本　<　蟻本 難易度が近い螺旋本は、スタンスが異なる部分もありますので、よい形で共存できたら、という想いです。 螺旋本と比べると、「動的計画法」「貪欲法」「二分探索法」などの設計技法に関する話題をより重視しています 螺旋本は「ライブラリを揃えていく」という思想なので、設計技法よりもライブラリになるものを重視する立場です 本書では、紙面の都合で「計算幾何学」と「整数論」には触れられませんでしたが、これらは螺旋本には載っています 2-2. 本書の対象読者 本書は、「アルゴリ

とりあえず落ち着け。 みなさん、毎日なにかしらのコードを読み、開発する日々を送っていると思います。そんな中で、 糞コードは死ぬべきである！！絶対に直すべき！！ という感情に取りつかれてしまうことがあると思います。自分の技術力に自信のある人ほど、無理やりにでも直そうと試みると思います。それがどんな修羅の道か。そして、糞コード修正がどんな道を歩むのか。この記事では糞コード修正の罠とありがちなストーリーについて書きたいと思います。 ビジネスとしてのプログラムは本質的に糞である 例えば、「携帯電話の利用料金」のプログラムがあります。 「携帯電話　透明性高め料金値下げを」という記事もあるように世の中の携帯電話の料金プランはかなり複雑です。例えば、auだと「auでんき」といった電気料金とパックされた電話料金プランがあります。また、「auスマートバリュー」といったプランもあり、家のインターネット回線をa

レイアウトとは レイアウトとは、GUIの配置を決めるための仕組みです。 このレイアウトを使うことによって、Androidアプリの画面を簡単に作成することができます。 Android開発においては.xmlで記述してGUIを配置していきます。 流れとしては.xmlでセットしたView部品（後述）を.javaで制御していく形になります。 レイアウトを構成する要素 画面を構成する要素（パーツ）は大きくわけて２種類あります。 Wedget(ウィジェット） Layout(レイアウト） です。これらの要素をまとめてViewといいます。 これらのViewは.javaで記載されており継承することでCustomのViewも作ることができます。 WedgetとLayoutの違いを超わかりやすく説明します。 ざっくり言うと、Layoutの中（要素）にWedgetを配置していくイメージです。 枯山水で例えると一番親

軽い読み物としておもしろおかしく読んでください。 はじめて社外の人の仕事を見た 今まで社内の成果物しか目にしてこなかったのですが、ふとしたきっかけで外部ベンダーが作ったシステムを移行することになりました。 会社名を見て、よく知った会社でちょっと安心しました。 「ここなら設計書とかもきちんとしてるだろう、多少古臭くても堅実にやってるんじゃないかな」って思ってました。ええ。 実態は全然違った とんでもない量のExcelが設計書として渡されました。 さすがに設計が専門だけあって設計書の量はすごいなぁ。と思って読んでいるといろいろ察してきました。 正直、「オワコン大手SIer」と呼ぶしかありません。設計しかできないと思っていたのに、何もできないなんて・・・ 実際に自分が見た「オワコン大手SIer」のアンチパターンをご紹介していきます。 自分が多く当てはまっている場合は今すぐ直してください。移行する

どうも、浮動小数点数オタクのmod_poppoです。 昨日開催された ABC169 の C 問題が浮動小数点数の罠な問題だったらしいので、どこが罠なのか、そしてどうすれば罠を回避できるのかを解説してみます。 また、典型的な誤答に対しては、それを落とすためのテストケースも用意しました。 問題文（引用） まず最初に問題文を引用しておきます。 AtCoder Beginner Contest 169 | C - Multiplication 3 問題文 $A\times B$ の小数点以下を切り捨て、結果を整数として出力してください。 制約 $0\le A\le 10^{15}$ $0\le B<10$ $A$ は整数 $B$ は小数第 2 位まで与えられる 入力 入力は以下の形式で標準入力から与えられる。