再帰が現実的でないBASICで「盤面が与えられた時にどのぷよが消えるか」を計算するアルゴリズムが当時どうしても思いつかず「ぷよぷよ」にハマった時からずっと考えていました。 そしてある授業中に突然アルゴリズムがひらめきました。 以下がそのアルゴリズムのご紹介です。 フィールドが以下の様になっていると想定します。形だけ見ると「連鎖を作ろうとしてたけどやらかしちゃった」形ですね。 この場合、赤い「ぷよ」が消えることになります。 基本的な方針としては「左上から注目する場所（セル）を右下まで走査する」「注目したセルにある「ぷよ」がいくつつながっているか調べる」です。 1. まず、左上のセルに注目します。 2. 左上のセルには何も無かったので次のセルに注目します。 このセルには赤い「ぷよ」が居ました。 これ以降はこの赤い「ぷよ」がいくつつながっているか（=消せるか）をチェックします。 3.「この「ぷよ
こんにちは。「家族アルバム みてね」の開発チームに所属している黒川と申します。今回は、その「みてね」の機能の1つで、写真や動画をDVDにして注文できる機能を動的計画法を使って改善した話をします。 「みてね」では家族の写真や動画をアップロードし、アプリ上で月ごとに振り返ることが可能になっています。一方、たとえば自宅のテレビやパソコンでまとめて振り返りたいという要望もあり、「みてね」では最長過去1年間の写真や動画をDVDにまとめて注文することができます。 このときに問題となるのがDVDのディスク分割です。1年分の写真や動画はともすると1枚のディスクに収まりきらず、複数のディスクに分割する必要があります。いままでは、動画を月ごとに分けて各ディスクに入れていく、というシンプルなアルゴリズムで分割を行っていました。しかし、ユーザーさんからは「1枚のディスクにすこしの動画しかないがどうなっているのか」
先日、気持ちのいいジャンプを目指してというQiitaの記事を見かけました。記事中では、マリオのジャンプについても触れられています。マリオというと、マリオブラザースやスーパーマリオブラザース等々、色々あるのですが、これはおそらくスーパーマリオブラザースの事だと思われます。ジャンプアクションゲームといったらスーマリですね。 そのマリオのジャンプの仕組みは「マリオの速度ベクトルを保存しておいて座標を計算するんじゃなくて～」と書かれていて、別サイトのブログへのリンクが張られています。 マリオのジャンプ実装法とVerlet積分 ただ、この記述については不正確であるという別のブログもあったりします。 マリオの完コピvol.28 ジャンプの解析と修正 ホントのところはどうなんでしょうか？世界で最も有名なゲームのジャンプがどのように処理されているのか気になったので調べてみることにしました。 原典にあたる
0. はじめに AtCoderなどでは、グラフを扱った問題が多く出るが、その度に一から実装していると時間が掛かりすぎてしまうため、有名なものをあらかじめ持っておく必要がありそう。そこで、Pythonを用いて、ダイクストラ法、ベルマンフォード法、プリム法、クラスカル法、ワーシャルフロイド法を実装した。 コメント、意見等ある方は是非! お待ちしてます! 1. ダイクストラ法 1.1. ダイクストラ法(defaultdictで実装) defaultdictで実装すると、リストで実装するよりも、ノード数$N$が大きい際には高速に動作する。ただし、経路復元の関数は、うまく書けなかった......。 (2019/7/6 追記)結局できました。1.1.1. を参照してください。 import collections import heapq class Dijkstra: def __init__(se
自分がコーディング面接対策のために解いてよかった LeetCode の問題をコンセプトごとにまとめました。カバーするコンセプトは LinkedList Stack Heap, PriorityQueue HashMap Graph, BFS, DFS Tree, BT, BST Sort Dynamic Programming Binary search Recursion Sliding window Greedy + Backtracking です。 これらの問題が 30 分以内に実装できれば面接の準備は整ったと言っていいと思います。Easy と Medium で問題は構成されてます。進捗を管理するためにGoogle Spreadsheetを用意しました。コピペしてご自由にお使いください。 これらの問題は、LeetCode のリスト機能でも公開されています。クローンすれば自分がすでにど
ロサンゼルスから帰国し、時差ボケで今わたしは一体どの時間を生きているかがわからない中、朝5時から生まれた時間を利用して何を思ったのかNote第二弾を書いています。寝ても寝ても眠いです。 ところで、前回の記事（Luckin Coffeeは何がすごいのか）を途中で有料化したところ、同世代友だちからディスられたので、この記事はずっと無料です。同世代怖い。 ByteDance社は世界No.1の時価総額を誇る未上場企業ですし、TikTokが世界中のApp Storeで上位を独占しはじめており、すでにGlobal MAUは7億とも8億とも言われています。話題にならない日はもはやなく、この事実から目を背けるべきではありませんし私自身も大好きなサービスの1つです。 多分ですが、わたしは日本のIT企業社長の中でもっともTikTokを触っている & 投稿しているという自負があります。笑 そこでいろいろと感じ
情報科学科の卒業生やプログラマの中には、UberやNetflixのような新興企業や、 Amazon 、 Microsoft 、 Google のような大企業や、InfosysやLuxsoftのようなサービスを基本とする企業で、プログラミング、コーディング、ソフトウェア開発の仕事に就きたいと考える人が大勢います。しかし、実際にそういった企業で面接を受ける場合、大半の人が プログラミングに関してどのような質問をされるか 見当もつきません。 この記事では、 新卒生からプログラマになって1〜2年までの 経験値が異なる人たち向けに、それぞれの プログラミングの面接でよく聞かれる質問 をいくつか紹介していきます。 コーディングの面接では、主に データ構造とアルゴリズムに基づいた質問 がされますが、 一時変数を使わずにどのように2つの整数をスワップするのか 、というような論理的な質問もされるでしょう。
NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。 今回はソートについて記します。 0. はじめに データ構造とアルゴリズムを学ぶと一番最初に「線形探索」や「ソート」が出て来ます。これらのテーマは応用情報技術者試験などでも頻出のテーマであり、アルゴリズムの Hello World とも呼ぶべきものです。 特にソートは、 計算量の改善 ($O(n^2)$ から $O(n\log{n})$ へ) 分割統治法 ヒープ、バケットなどのデータ構造 乱択アルゴリズムの思想 といった様々なアルゴリズム技法を学ぶことができるため、大学の授業でも、アルゴリズム関連の入門書籍でも、何種類ものソートアルゴリズムが詳細に解説される傾向にあります。本記事でも、様々なソートアルゴリズムを一通り解説してみました。 しかしながら様々な種類のソートを勉強するのもよいが、「ソートの使い方」や
2016年の3月、DeepMindのAlphaGoが人類最強の囲碁棋士を破った最初のAIとなり、衝撃が走りました。この時のAlphaGoのバージョンであるAlphaGo Leeは世界中の最高の囲碁棋士の膨大な対局を学習に使っていました。数日前に発表された 新しい論文 によると、新しいニューラルネットワークの AlphaGo Zero は人間が囲碁の打ち方を教える必要がないそうです。今までの囲碁棋士より(人間、機械に関係なく)優れているだけでなく、たった3日間の学習で打ち方を学んでしまうのです。この記事では、これがどのようにして可能なのか、そしてなぜ可能なのかについて説明します。 モンテカルロ木探索 離散的で決定論的な完全情報ゲームをするボットを作成できるアルゴリズムは、モンテカルロ木探索(MCTS)でしょう。囲碁やチェスやチェッカーのようなゲームをするボットは次の一手を決める際に全ての選択
はじめに 皆さんはGoogleドキュメントやHackMDを使ったことはあるでしょうか。これらのツールは「ネット越しに同時に複数の人で1つのドキュメントを編集できる」という特徴を持っています。お互いの編集がリアルタイムに反映されるので、相手が何を書くのかを意識することなく、簡単にドキュメントを複数人で編集することができます。これを実現するためには、同時編集に参加しているユーザ全員の編集内容がネットワークの延滞に影響されることなく、それぞれの編集内容をうまい具合にマージして反映してくれるような賢いアルゴリズムが必要になります。今回はこのアルゴリズムに関して書きます。 編集内容のマージとは 編集内容をうまい具合にマージしなければいけないケースを考えてみます。 AさんとBさんが次のドキュメントを同時編集するとします。最初は、お互いブラウザ上では次のように見えています。当然、この状態ではお互いに見え
2001年の勉強会で発表した遺伝的アルゴリズムの紹介資料です。HDDをあさってたら見つけたので一応記録。ほんのさわりです。最近の研究ではどこまで進展したんでしょうね？遺伝的アルゴリズムって複雑系と人工生命の文脈で捕らえるのが面白いのに、研究だとただの探索アルゴリズムになっちゃうのが悲しかった。 はじめに 遺伝的アルゴリズム（Genetic Algorithm:GA）とは、生物進化（自然選択、突然変異）から着想を得た汎用的な探索手法です。探索というのは、たくさんの解の候補がある中から、最も良い解を探すことです。つまり、GAとは解の候補から最もよいものを探すのが目的と考えられます。 歴史的背景 GAは、1975年、Hollandによって初めて導入されました。当時は、「なぜ進化のような何十億年もかかるプロセスの真似をするのか？」という反応が多かったらしいです。しかし、その後のGoldbergの研
%matplotlib inline import numpy as np import matplotlib.pyplot as plt plt.style.use('ggplot') 経路のパターン数 まず、この問題は全パターンをごり押しで計算できるか考えてみます。機械的に全通りの経路を調べて、最適解を見つけられるならそれが一番です。都市数をNとして、何パターンの経路があるのかを計算してみます。 ある経路を選んだ時に、どこから出発するかでN通りの回り方がありますが、経路が同じであれば総移動コストは同じです。なので、重複して計算するのを避けるために、出発地は固定して考えます。出発地を決めると、最初に向かう都市の選択肢は(N-1)個、次の移動では(N-2)個、さらにその次の移動では(N-3)個、のようになります。つまり、(N-1)×(N-2)×(N-3)×...×1 = (N-1)! 通り
2. はじめに！ • 本講義では、ソースコードを扱います。 • 前面の資料だけでは見えづらいかもしれないので、 手元で閲覧できるようにしましょう。 • URLはこちらから – http://www.slideshare.net/chokudai/wap-atcoder2 – URLが打ちづらい場合は、Twitter: @chokudaiの最新発言 から飛べるようにしておきます。 • フォローもしてね！！！ 2014/3/16 2 3. ©AtCoder Inc. All rights reserved. 3 目次 1. 勉強会の流れ 2. 競技プログラミングって？ 3. シミュレーション問題 4. 全探索問題 5. 本日のまとめ 2014/3/16 3
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
