(※2020/5/13 追記 リストの要素数を変更した場合について) 背景 先日のAtcoderでのABC167において、次の問題でTLEを連発しました。 ・ABC167D-Teleporter 順番に町をテレポートして、ループになった時点でやめ、残り回数は modを使って求めればいいということに気づいたのですが、 ループになる ⇔ 再び同じ町にたどりつく ⇔ 訪れた町のリストの中にすでにある と考えればいいと思い、PythonでX in listを使って処理しようとして時間がかかっていました。 結局代わりにX in setを用いればいいことに気づき通しましたが そんなに速度が変わるものなのか気になったので調べた結果をまとめました。 set型とは Pythonの公式ドキュメントより引用 set オブジェクトは、固有の hashable オブジェクトの順序なしコレクションです。通常の用途には
背景 Atcoderで茶色から進まなくなってきたので アルゴリズムの勉強を本格的に始めました。 幅優先探索(BFS)、深さ優先探索(DFS)について少し理解できたので 復習として、基本情報技術者試験の問題でも出題されている PERTでの最早結合点時刻、最遅結合点時刻、クリティカルパスを 求めてみることにしました。 目的 グラフの情報を入力することで、PERTにおける ・最早結合点時刻 ・最遅結合点時刻 ・クリティカルパス を計算するプログラムを実装します。 幅優先探索(BFS),深さ優先探索(DFS)について @drken様の記事が非常にわかりやすかったです。 ・DFS (深さ優先探索) 超入門! 〜 グラフ・アルゴリズムの世界への入口 〜【前編】 ・DFS (深さ優先探索) 超入門! 〜 グラフ・アルゴリズムの世界への入口 〜【後編】 ・BFS (幅優先探索) 超入門! 〜 キューを鮮や
皆様こんにちは。私は AIQuest 2020 に参加・修了した黒男(Twitter : @Black_Jack_2021) といいます。今年も AIQuest 2021 が開催されるということで、参加を迷っていらっしゃる方もいるかと思い、簡単ではありますが自分の意見を発信させて頂ければと思います。 1. そもそもあなたは誰? と思われる方もいらっしゃると思いますので簡単に自己紹介だけさせていただきます(興味がない方は飛ばしていただいて結構です。)。私は去年まで学生(経済学系の大学院生)で、今年から金融機関でデータサイエンティストとして勤務しているものです。したがって私が AIQuest に参加したとき、まだ学生でした。当時の自分のスペックは以下のようなイメージです。 1. 機械学習 全く専門といえるほどの知識はないが、大学の講義でかじったり簡単なテーブルコンペに出たりした経験が少しある程
プログラミング初心者の学生に「自習してね」と簡単に言うために,簡単にwebブラウザでプログラムを書いて実行できる環境が欲しい.いろいろあります. 高度なonline開発環境もありますが,それは別物. https://c9.io https://codeanywhere.com ここではユーザ登録などの面倒な手続きがなく,すぐにコードを書いて実行できるサイトを紹介します. ただし,書いて実行した自分のコードが,すぐに全世界に公開され共有される場合もあるので,それを理解してからこれらのサイトを使ってください Coding Ground at tutorialspoint (2021/4/16 update) 特徴 多数の言語あり(C, C++, Java, Python, latex, etc...) https://www.tutorialspoint.com/codingground.ht
文字列アルゴリズム ローリングハッシュ 文字列をハッシュ化をするもの 詳しくはこっち Suffix Array 接尾辞配列 全文探索、パターンマッチングに使える LCP ある2つの文字列について接頭語がどれだけ一致しているか 複数文字列があるとき、ある任意の2つのLCPを求めたい場合は、「1.文字列を昇順ソート」「2.隣り合う文字列でLCPを計算」「3.ある任意の2つの間のLCPの中で最小のLCPがその2つの文字列のLCP」参考 KMP KMP法 : 単一文字列のマッチングアルゴリズム KMP法の前処理の段階でできる配列を使うと、最短の周期が取得できる 出典 動的KMP?(変更可能なKMP?) Trie, Aho-Corasick Trie : 複数文字列から作った木 Aho-Corasick法 : 複数文字列のマッチングアルゴリズム 資料 Aho-Corasick法で作った木に対してDP
前回のブログ記事で、文字列マッチングをするためのSuffix Arrayという構造を構築した。このSuffix Arrayという構造だけでも、テキスト長をn、パターン長をmとして、の計算量で文字列マッチングできるようになった。 suffix arrayを一番簡単なアルゴリズムで実装する - アルゴリズム学習(その6) - $shibayu36->blog; suffix array構築のメモリ効率を良くする - アルゴリズム学習(その7) - $shibayu36->blog; しかし、前処理としてSuffix ArrayからLCP Array(Longest Common Prefix Array)という構造をさらに作っておくと、という計算量で文字列マッチングが出来るようになるらしい。そこで、今回はLCP Array(Longest Common Prefix Array)の構築を実装し
suffix arrayは知ってます。(当然) (知ったきっかけは何だったかな…高林さんのsaryかな) 以前、英辞書検索用のCLIツールを作る時などにも使いました。 でも今までずっと、文字列のポインタを1つずつずらした(文字列の長さ分の)char**配列を用意してqsortでstrcmp的なものを渡すような、愚直な(の)書き方しかしたことがありませんでした。 あまりそれで困るような場面に遭遇したことがなかったということでもありますが、 競プロで使うとなるとそういうわけにはいきません。 制約がとかだともう無理ですよね。 LCP(最長共通プレフィックス)array もそうです。 suffix arrayを作った後に、隣り合う項目同士の最長共通プレフィックスを求めておくやつです。 隣同士の最長共通プレフィックスのリストがあると、あとはRMQとか使えば任意の2つのサフィックスの共通プレフィックス
核ガンジーのインターネット・ミームの例 (はじめに彼等は無視し、次に笑い、そして挑みかかるだろう。[1]そして我々が核攻撃するだろう。そうして我々は勝つのだ。) 核ガンジー[2][3][4](かくガンジー、Nuclear Gandhi)は、コンピュータシミュレーションゲーム『シヴィライゼーション』に関するインターネット・ミームであり、都市伝説。ミームによれば、初代『シヴィライゼーション』(1991年)にはバグがあり、平和主義者の指導者であるマハトマ・ガンジーがパラメータの算術オーバーフローによって非常に攻撃的になり、核兵器を多用するようになるという[2][3]。 同シリーズのプレイヤー間でまことしやかに囁かれていたこのバグは、『シヴィライゼーションV』(2010年)にて、ジョーク、イースター・エッグとして初めて公式に実装された。『V』発売から2年後の2012年にインターネット・ミームとして
脳外科医 竹田くん @dr_takeda 【第1話】履歴書 - 脳外科医 竹田くん dr-takeda.hatenablog.com/entry/2023/01/… 病床数360床の赤池市民病院に竹田くんがやってきた。この物語は竹田くんと脳外科科長 古荒先生の出会いで始まる。竹田くんの履歴書には前の職場での執刀経験が乏しく執刀経験を積みたいと書かれていた。 #漫画 #医療事故 #脳神経外科 2023-04-08 22:41:10 リンク pixiv #医療系漫画 「脳外科医 竹田くん」1話~55話 - 竹田くんのマンガ - pixiv 前の職場で執刀させてもらえなかった脳外科医の竹田くんが、新天地の赤池市民病院で手術を次々に行うが、術後に嚥下機能障害や聴力障害が発生する患者が続出して行く。以下のページで最新連載を読めます。https 52 users 235
〈今回起きたことの概要〉 個人の原型師の方があるゲームのキャラのガレージキットをイベントとBOOTHで販売し、BOOTHの方が数十秒で完売する。 ↓ 即売するレベルの人気だったにも関わらず、購入のキャンセルがかなり発生する。→無在庫転売をしようとした人が後払いの方法で購入して入金しなかった可能性アリ※後述 ↓ キャンセル分を再販しようにも当日版権という許諾のシステムで販売しているためそれが叶わず、がっつり在庫を抱えてしまう。 歩瀬(ほせ) @josenoshin フリーランス商業原型師 I don't accept personal comission. 連絡先 jose.noshin@gmail.com josenoshin.booth.pm 歩瀬(ほせ) @josenoshin NIKKE-勝利の女神-よりバイパーが完成しました! 5/14,15開催のとなりのモケイフェスティバル @T
Liteプラン(無料)での予約投稿機能の提供を終了させていただくこととなりました。これにより、ご利用のお客様には追加の機能制限が発生いたします。お手数おかけいたしますが、今一度ご確認ください(2023/5/30 追加)。 いつもSocialDogをご利用いただきありがとうございます。 このたび、Twitter APIの有料化に伴い、SocialDogのLiteプラン(無料プラン)で利用できる機能を大幅に制限することにいたしましたので、お知らせいたします。 ご利用いただいていたみなさまには、突然のご連絡となってしまい、誠に申し訳ございません。 SocialDogでは、プロダクトミッションである「あらゆる人が主人公になれる世界を創る」という理念のもと、これまでLiteプランをご利用のみなさまにも多くの機能を提供してまいりました。しかしながら、有料化後のTwitter API利用料金が非常に高額
はじめに 当記事を開いてくださりありがとうございます。私は表題の通り、私は一般にメガベンチャーと呼ばれる自社開発企業で機械学習エンジニアとして勤務しはじめてからわずか半年で、鬱を発症し退職することになったものです。この会社は待遇も良く、社風としても労働者思いのとても素晴らしい会社であったと私自身振り返って思います。 そんな会社に運よく入社することができた私ですが、わずか半年で「鬱状態」と心療内科から診断を受け休職し、会社制度により退職することになりました。「え?そんなに素晴らしい環境なのにメンタル弱すぎでは?」と思われる方もいらっしゃることでしょう。返す言葉が全くありません。おっしゃる通りです。 しかし同時に、「何故鬱になったの?」と思われる方もいらっしゃるのではないでしょうか。本記事ではこの点について鬱を発症した本人の目線から「どうしてそんなことが起きてしまったのか」という点について考察
はじめに 非プログラミングエンジニアがPythonでdocstringを適切に運用するために情報をまとめた。 本内容では日本語記載を行うが、通常は推奨されない。 自身の関連記事 ・docstringのスタイルと書き方。(2021/01/30)←本記事 [Python] docstringのスタイルと書き方 ・VSCodeでのdocstring生成に関する機能拡張。(2021/02/01) [Python] VSCodeでのdocstring生成拡張 ・docstringを利用した関数テスト。(2021/02/07) [Python] 関数のテストとその手法概要(dcstest, unittest, pytest) docstringとは コード内で文字を記載する際の方法の一つ。 (#)をいれることでそれ以降がコメントとなる。コメントはコード内で無視される。 (""")で囲うことでdocst
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く