これが現代の科学力……！ 「スーパーマリオメーカーはチューリング完全」はなぜたった1年半で証明されたのか
「マリオメーカー学会」というものをご存じでしょうか。自作ステージを作って遊べるゲーム「スーパーマリオメーカー」に斜め上過ぎる楽しみ方を見いだした“研究者”の集まりで、これまでには「クリアに20万年ほどかかるステージ」「ギミックを巧みに活用した計算機」などが開発されています。 話がぶっ飛んでいて何が何だか分からないかもしれませんが、きっとそれだけ研究が進んでいるということでしょう。今回は、5分間で数学を語るイベント「日曜数学会」から、同学会のハイレベルさが伝わる発表「スーパーマリオメーカーはチューリング完全」を書き起こしました。 拡大画像でスライドを見る スーパーマリオメーカーはチューリング完全 イベント：2019年6月29日開催の第15回「日曜数学会」（Twitter：@nichimath） 発表者：yos1upさん（Twitter：@yos1up） 発売から約2週間で、計算機になったスー
AVX-512を用いた、たぶん世界最速のBase64エンコード実装について - Qiita
この記事で紹介するのは高スループットなBase64エンコードの実装方法です。 Base64は、Webの世界を始めとして、世界中さまざまな箇所で使われているエンコード方式です。とてもよく使われるので、高速化についてもしばしば研究されてきたようです。 高速化の最新成果として、2019年10月に、Wojciech Muła, Daniel Lemireによる新しい論文がarxivに投稿されました。なかなか強烈なタイトルが付いています。 Base64 encoding and decoding at almost the speed of a memory copy 論文の主張としては、x86 CPUの持つ最新の命令群を駆使することで、非常に高効率なBase64エンコード・デコードが実現できたというものです。このQiita記事では論文の内容の一部を紹介します。 Base64は問題としては単純に見え
競プロでWAが出たときのランダム入力データ生成入門 - ARMERIA
概要 競技プログラミングで提出コードがWAになったとき、実際に不正解となるような入力データを入手できると役に立つ場合があります。ただ多くのコンテストサイトでは、コンテスト中には入力データを見ることはできません。 そのような時に、小さめの入力データを乱数で大量生成して、提出コードと愚直解法の結果を突き合わせ、答えが一致しないものを探すという方法があります。もちろんそのようなデータを確実に得られる保証はありませんが、もし見つかればデバッグの大きな助けになります。 今回の記事はその手順を紹介します。また、生成コードの例としてC++とPythonを扱います。 手順1：愚直解法コード作成 まずは問題に対する愚直解法のコードを書きます。小さな入力データで回すので、 だろうと だろうと気にせず書きましょう。これがバグっていると破綻するので計算量よりも正しさ優先です。 C++等の場合はコンパイル時に提出コ
競技プログラマのための抽象セグメント木実装のすすめ - beet's soil
午前起床！（素振り） はじめに 先にこっちを見て beet-aizu.hatenablog.com うし木（一点更新区間取得）について書きます おまけ なんだこれはたまげたなあ（わかる人にはわかる記事、わからない人にはわからない） beet-aizu.hatenablog.com 前提知識(C++) 厳密性や歴史的背景をガン無視しています。あんまりあてにしないでください。 雰囲気を掴むためと割り切って読んでもらえるといいと思います。 C++のバージョンは14を前提にしていますがそのうち17に上がりそう？ struct is 何 競技プログラマならpairやtupleくらいは使ったことがあると思いますが、自分でそういうのを作るための機能です。 たとえば struct Node{ int fi,se; }; Node v; v.fi=0;v.se=1; みたいな感じで使えます。 つまり、大きな
動的計画法によるDVDのディスク分割の改善
こんにちは。「家族アルバム みてね」の開発チームに所属している黒川と申します。今回は、その「みてね」の機能の1つで、写真や動画をDVDにして注文できる機能を動的計画法を使って改善した話をします。 「みてね」では家族の写真や動画をアップロードし、アプリ上で月ごとに振り返ることが可能になっています。一方、たとえば自宅のテレビやパソコンでまとめて振り返りたいという要望もあり、「みてね」では最長過去1年間の写真や動画をDVDにまとめて注文することができます。 このときに問題となるのがDVDのディスク分割です。1年分の写真や動画はともすると1枚のディスクに収まりきらず、複数のディスクに分割する必要があります。いままでは、動画を月ごとに分けて各ディスクに入れていく、というシンプルなアルゴリズムで分割を行っていました。しかし、ユーザーさんからは「1枚のディスクにすこしの動画しかないがどうなっているのか」
AtCoderで15万点分の問題を解いて見えたもの - 競プロ弱者の解答
競プロ大好きなsyunsukeです。 最近はwebアプリの勉強も好きです。 タイトルの通り、15万点分の問題を解きました。 10万点の時点がこれなので、 10万点⇒15万点までに 期間 ：5/18 ⇒ 10/23 約5カ月 AC数 ：633 ⇒ 881 約250問(点数のつかない問題も解いていますので、 単純に5万÷250問＝200点/問とはなりません) かかりました。 また、その間のレートの推移ですが、 10万点時点では1222で、15万点時点では1293なので、70増えました。 ただ、その過程はなかなか大変で、一気に1309(Highest)まで上がり、7連敗で1109まで落ち、そこから1293まで戻しています。 この間毎日精進を続け、解ける問題も増えていってたので、私の実力は向上していたはずなのですが・・ コンテストへの新規参加が増えた時期に、強い新人さんたちに抜か
エラーメッセージの読み方と対処，検索や質問の原則 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? プログラミングをしている限り，エラーメッセージに遭遇するのは避けられないことだ．そこで，あなたは周りのできる人に「エラーが出ました」と言って "答え" を聞こうとするだろう． でも，もし聞ける人が誰もいなかったら? もし，周りの誰にもわからないようなエラーにぶつかってしまったら? あなたが一人前のプログラマになるためには，自分でエラーメッセージを読んで，解決できるようにならなければならない． どういうエラーメッセージが出たときは何が原因で，どのように対処すれば解決するのか．その知識・経験の積み重ねこそがあなたを一人前のプログラマにするの
典型データ構造まとめ - beet's soil
なんか前回伸びたので 参考 hamayanhamayan.hatenablog.jp ei1333's page 宣伝 beet-aizu.hatenablog.com 以下とりあえず辞書順（そのうち典型度順にしたい） Binary Indexed Tree 一点加算、先頭からの区間和、k番目に大きい値が で可能 library/binaryindexedtree.cpp at master · beet-aizu/library · GitHub 容易に多次元に拡張が可能（実用上は2次元くらい？ library/binaryindexedtree2D.cpp at master · beet-aizu/library · GitHub Binary Trie 二進数を管理するTrie木 全体にXOR、k番目に大きい値、lower_bound等が で可能 library/binarytri
C++を知らないゲームプログラマ達 - Ideals and Reality
マルチプラットホームライブラリを作ってみた。 ※リンク先pdf 有名なSEGA本の著者、平山さんによる今年のCEDECでの講演内容である。 ゲームプログラマになる前に覚えておきたい技術 作者: 平山尚出版社/メーカー: 秀和システム発売日: 2008/11/14メディア: 単行本購入: 112人 クリック: 3,473回この商品を含むブログ (193件) を見る 内容的には十分読み応えのあるのだが、一部釈然としないところもある。 主に4.9章の「標準ライブラリや言語機能について」というところから。 何故標準が嫌なのか ゲームプログラマはなぜかC++標準ライブラリを使わない。 いや、使おうとする人もいるが何かと理由をつけて使わない。 その理由が大体困ったような内容が多い。 リンク先でも書かれているが、vectorにはpush_back()やerase()がある。 そしてこれは安全性と性能の両
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
minaminao on Twitter: "このコード、b=n, a=n*n にはならないんだな… C++罠が多すぎる https://t.co/nE0p07oe24"
Google Coding Interview With A Competitive Programmer