[競プロ] 単調スタック(Monotonic Stack)の説明 - Qiita
単調スタック(Monotonic Stack)とは 単調スタックという単語は勝手に作りました。 英語ではMonotonic Stackというらしいのですがそれに相当する日本語がなさそうだったのでそれっぽいものを勝手に使用。 定義は下記になります。 実はこれは蟻本の「4-4 頻出テクニック２」の「スタックの利用」というセクションに説明されています。 なぜこれが便利なのか これは主に配列Aにおいてある要素A[i]の値よりも前(j<i)にあるより小さい最初の値(A[j])を効率的に見つけるときに使われる 例えば、下記配列Aの4よりも前にある小さい値は3。 このようにある要素よりも前にあるより小さい要素のインデクスの配列をPとするとPは下記のようになる。（存在しない場合は-1とする）
![[競プロ] 単調スタック(Monotonic Stack)の説明 - Qiita](https://cdn-ak-scissors.b.st-hatena.com/image/square/1a5b2cd9a36037e455f204cfe6af393969cbe8f2/height=288;version=1;width=512/https%3A%2F%2Fqiita-user-contents.imgix.net%2Fhttps%253A%252F%252Fcdn.qiita.com%252Fassets%252Fpublic%252Farticle-ogp-background-9f5428127621718a910c8b63951390ad.png%3Fixlib%3Drb-4.0.0%26w%3D1200%26mark64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTkxNiZoPTMzNiZ0eHQ9JTVCJUU3JUFCJUI2JUUzJTgzJTk3JUUzJTgzJUFEJTVEJTIwJUU1JThEJTk4JUU4JUFBJUJGJUUzJTgyJUI5JUUzJTgyJUJGJUUzJTgzJTgzJUUzJTgyJUFGJTI4TW9ub3RvbmljJTIwU3RhY2slMjklRTMlODElQUUlRTglQUElQUMlRTYlOTglOEUmdHh0LWNvbG9yPSUyMzIxMjEyMSZ0eHQtZm9udD1IaXJhZ2lubyUyMFNhbnMlMjBXNiZ0eHQtc2l6ZT01NiZ0eHQtY2xpcD1lbGxpcHNpcyZ0eHQtYWxpZ249bGVmdCUyQ3RvcCZzPTQwMDE3YTA2MGZmOTIzODE5MjQzNjhlYzI0Yjc3MGEx%26mark-x%3D142%26mark-y%3D112%26blend64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTcxNiZ0eHQ9JTQwYXdlc2FtJnR4dC1jb2xvcj0lMjMyMTIxMjEmdHh0LWZvbnQ9SGlyYWdpbm8lMjBTYW5zJTIwVzYmdHh0LXNpemU9MzImdHh0LWFsaWduPWxlZnQlMkN0b3Amcz0xMDkyOTc2MzliZTljMmRmMzVhMGYyOGYwOTViNjcxYg%26blend-x%3D142%26blend-y%3D491%26blend-mode%3Dnormal%26s%3D81342563fcd666e570efafaef34dd6c5)
t_wadaさんと「単体テストの使い方/考え方」の疑問点についてディスカッションしました - DeNA Testing Blog
こんにちは、SWETグループの田熊です。 現在SWETグループでは書籍「単体テストの使い方/考え方」の輪読会を実施しています。 輪読会ではメンバー同士で活発に意見が交わされていますが、著者の主張に疑問を感じる箇所もあり、一度グループ外の方とも意見を交換したいと考えていました。 そこで、t_wadaさんをお招きし「単体テストの使い方/考え方」についてディスカッションする機会を設けました。 本記事では、SWETメンバーとt_wadaさんとのやりとりを紹介したいと思います。 ディスカッションの流れ ディスカッションは事前にSWETグループのメンバーが書籍を読んで疑問に感じたテーマを挙げてもらい、t_wadaさんの意見を聞くという流れで行いました。 今回は次のテーマについて話をしました。 「退行に対する保護」があるテストとはなにか 「リファクタリングへの耐性」のトレードオフはあるのか 統合テストの
【緑色変】算数の教養がほとんどなかったプログラマがAtCoderを4年やって緑になれた話｜きりみんちゃんノート
こんばんみんみん。 バーチャル幼女プログラマーという肩書でインターネットをやっているきりみんちゃんというものです。 競技プログラミングのAtCoderというサービスに日々取り組んでいるんですが、この度めでたく緑レートになることが出来ました。 いわゆる色変エントリというやつです。 で、誰？3年前にこんなエントリを書いた者です。 VTuberをやったり絵を描いたりしてる社会人エンジニアです。 専門分野はAndroidでしたが、最近はフルスタックエンジニアを目指してフロントエンドやバックエンドなどをやっています。 現在のAtCoderコミュニティの中心層は理系の学生やもともと数学がかなり好きなタイプの人たちです。 一方きりみんちゃんはプログラマでありながら数学にコンプレックスがあり、それどころか小学2年までしか義務教育を受けていないため、中学、高校レベルの基礎的な数学の教養が全くありませんでした
ソフトウェア開発の真の問題点は、コードを書くことではなく、問題の複雑さの管理にある - YAMDAS現更新履歴
www.oreilly.com オライリー・メディアのコンテンツ戦略部門のバイスプレジデントであるマイク・ルキダスの文章だが、彼が数週間前、「コードを書くことが問題なのではない。複雑さをコントロールすることが問題なのだ」というツイートを見かけた話から始まる。彼はこれに感心したようで、これから何度も引用すると思うので、誰のツイートか思い出せればいいのにと書いている（ご存じの方は彼にご一報を）。 件のツイートは、プログラミング言語の構文の詳細や API が持つ多くの関数を覚えることは重要じゃなくて、解決しようとしている問題の複雑さを理解し、管理することこそが重要だと言ってるわけですね。 これは皆、覚えがある話だろう。アプリケーションやツールの多くは、最初はシンプルである。しかも、それでやりたいことの80％、いやもしかしたら90％をやれている。でも、それじゃ十分ではないと、バージョン1.1でいく
コード品質はやはりビジネスに影響を与える - mtx2s’s blog
私たちソフトウェアエンジニアは、コード品質についてしばしば論ずるけれども、ではコード品質の良し悪しがどれほどビジネスに影響するのかと問われると、回答に窮する。只々、「コード品質が悪いと変更により多くの時間がかかります」だとか、「欠陥の修正に追われて開発時間が奪われます」だとか、個人の経験やエンジニア的一般論に頼った定性的な説明に終始するしかない。ソフトウェアを繰り返し変更する頻度が高いほど、コード品質が開発時間に影響を与えるのは確かにそのとおりだと思えるが、はたしてそれは、どれほどのインパクトなのだろうか。 2022年の研究論文 "Code Red: The Business Impact of Code Quality – A Quantitative Study of 39 Proprietary Production Codebases" では、コード品質がビジネスに与えるインパクト
Rustの良質な学習リソースをまとめる - BioErrorLog Tech Blog
Rustの勉強に良さげな学習リソースをまとめます。 はじめに Rust学習リソースまとめ The Rust Programming Language Tour of Rust Rust by Example The Rust Reference The Cargo Book Crate docs Rust API Guidelines Rust Design Patterns The Rustonomicon Secure Rust Guidelines Command line apps in Rust おわりに 参考 はじめに こんにちは、@bioerrorlogです。 最近、Rustを触り始めました。 多様な領域で盛り上がりを見せているRustですが、私は最近ハマっているブロックチェーンのエコシステムでRustが使われることが直接の理由となり、Rustに入門しました。 Rustは学習
よわよわエンジニアがTAPL（型システム入門）を読んだら
こんにちは，sititou70です．私は社会人2年目のよわよわWebフロントエンドエンジニアであり，「数学」とか「証明」とは無縁の人生を送っています． そんな私ですが，がんばって型システム入門（通称：TAPL）という本を読み終えました．全32章，503ページ，牛乳パック1本分の重さがあり， 自立します． 自立する本は大抵やばいです． TAPLの序文を見ると，想定読者は プログラミング言語と型理論を専門とする大学院生および研究者 プログラミング言語の鍵となる概念に触れたい，計算機科学の全分野の大学院生および習熟度の高い学部生1 となっています．本記事では 「そんな本を，学生や専門家でない人間（私）が読んだらどうなるのか」 について書きます．専門的な用語は避けますので，TAPLの雰囲気だけでも感じ取ってもらえたら嬉しいです． どうなったのか 宇宙語が読めるようになった 「型安全」を説明できるよ
LOG関数で2を底とする対数(二進対数)とO(logN)の意味を知ることは情報処理の基本である【Excel】 - わえなび ワード＆エクセル問題集 waenavi
対数のlogを勉強するときにまず最初に習得するのは常用対数です。 【LOG・LOG10関数】Excelで10の累乗と常用対数が使えたら数値の桁数が計算できます 常用対数を習得したら次に習得するのが2の累乗と2を底とする対数です。学生の時に、2，4，8，16，32・・・と2の累乗を覚えた人もいるのではないでしょうか？ 大人であれば、2を10回かけたら1024（=約1000）になることを知っておいても損はないでしょう。携帯電話の「ギガ」はもともと2を30回かけると約10億＝1ギガの情報量になるところからきています。2の累乗と2を底とする対数を理解することは情報処理を理解する第一歩と言っても過言ではありません。 そこで、今回は、Excelで2の累乗と2を底とする対数を求める方法とその応用について解説します（2進数については深入りしません）。 目次 １．まずはExcelで２の累乗の性質を考えてみよ
記者に「プログラミングのスキル」って必要なの？ちなみにNHKニュースの画像生成も記者がコードを書いてます｜NHK取材ノート
記者に「プログラミングのスキル」って必要なの？ちなみにNHKニュースの画像生成も記者がコードを書いてます 新型コロナウイルスの新規感染者の数を示す日本地図に、毎日厳しい視線を送る男がいる。 コロナの感染拡大の今後が懸念されるが、地図がきちんと描画されているかも気になってしまう。 それはこの「新型コロナ感染者数マップ作画システム」をプログラミングしたのが彼だから。 ちなみに彼は技術部局のエンジニアではなく、いつもはテレビで解説している記者だったりする。 このシステム、記者が作りましたこんにちは、NHK解説委員の三輪誠司といいます。専門はITやサイバーセキュリティで、主に「シブ5時」や「くらし解説」などでニュースの解説を担当しています。 新型コロナウイルスの「感染者数マップ作画システム」は、1週間で作成しました。 言語はJava、地図はSVGで、ブラウザの画面をそのまま放送で使っています。SV
CS50 for Japanese: コンピュータサイエンスの入門 – 当ウェブサイトは、Creative Commons ライセンスに基づいて管理されています。
お知らせ: 2022/9/1 CS50 を活用した非営利／協賛企業による「コロナ学生支援」プロジェクトを実施中 ▼ 学生の方へ：CS50 の学習（履修証明書の取得）を一緒に取り組むプロジェクト CS50日本語版の翻訳コントリビューターである CODEGYM が主催する、非営利／無償のプロジェクト「CODEGYM Academy (外部リンク)」は、昨年に続き2022年度（春/秋）も、キャリア選択を控えた学生に対し、以下の企業の協賛により無償で17週間のプログラミング教育カリキュラムを提供します。 CODEGYM Academy 協賛企業（2022年） https://codegym.jp/academy/ 今年度のエントリーは締め切りました — ようこそ！ このページは、ハーバード大学 CS50 の日本語版翻訳プロジェクトのページです。当サイトのドメインに掲載されているコンテンツは、Cre
コードが読めるソフトウェア開発者 - As a Futurist...
僕はコードを読むのは得意な方だけど、それが過ぎてコードを書かなくてもシニアソフトウェア開発者になってしまった。実はコードをちゃんと読めるソフトウェア開発者って希少価値が高いのではないか、と思ったので自分がどんな感じでシニアになったのかをまとめてみた。似た様な人の参考になれば幸いだ。 同意。僕は未だ書く方はほとんど機会なく成果もないけど、コードを読み尽くして、負荷試験や本番で挙動を把握し続け、メトリクスでとことん確かめていった結果、Sr. Engineer になれた。 https://t.co/KXtMdEaRr8 — Ryosuke Iwanaga (@riywo) April 16, 2021 コードを書かなくてもシニアソフトウェア開発者になれた 僕は今 Amazon の Sr. Systems Development Engineer という職種で働いている。いわゆるソフトウェア開発職
Goの言語仕様書精読のススメ & 英語彙集
この記事について Go言語公式から提供されているThe Go Programming Language Specificationという文章があります。 実際のThe Go Programming Language Specificationのページ画面 この文章、個人的にはじっくり読んでみると結構得るものが大きいな、と感じるものです。本記事では The Go Programming Language Specificationって何が書いてあるの？ 読んだら何がわかるの？ 読むときにはどういうところに注目したらいいの？ 英語難しいから単語教えて！ という疑問に答えながら、The Go Programming Language Specification精読の布教を行います。 The Go Programming Language Specification とは？ The Go Prog
未知の道に突入せず、まずは半分知ってるくらいの状態になる - hitode909の日記
Perl製アプリケーションからGraphQLを喋ってみたい、ということがあって昨年末に2週間くらいでプロトタイピングしていた。 CPANにGraphQLというライブラリが公開されていて、社内の利用実績もあるので、これをいきなり使ってみても良かったのだけど、自分はGraphQLについては、耳では知っていて、GitHubのAPIを呼び出したことがある、くらいで、実際に実装したことはなかった。 このような状態で突き進むと、問題に遭遇したときに2パターンの怪しさが出てきて、切り分けていくことになる。未知のものが多すぎて、プロジェクトXの、トンネルを掘るだけで難しいのに現地の言葉はわからない、みたいな回をイメージしてください。 GraphQL自体への理解が間違っているパターン スキーマ、クエリの書き方が悪い、概念を勘違いしている、など PerlでのGraphQLライブラリの使い方が間違っているパター
Exercism
Get really good at programming. Develop fluency in 70 programming languages with our unique blend of learning, practice and mentoring. Exercism is fun, effective and 100% free, forever.
Nand2Tetris(コンピュータシステムの理論と実装)でCPUからOSまで一気通貫で作るのが最高に楽しかった話 - ( ꒪⌓꒪) ゆるよろ日記
どうも、しいたけです。 去年あたりからローレイヤー周りの知識を充実させようと思い、 低レイヤを知りたい人のためのCコンパイラ作成入門 を読んでCコンパイラを書いてみたりx86_64の勉強をしたりしていました。 今年に入ってから、よりローなレイヤー、具体的にはハードウェアやOSについてもう少し知りたいと思い始め、手頃な書籍を探していました。 CPUなどのハードウェア周りについては概要しか知らなくて手を動かしたことがないので、実際に何か作りながら学べるものとして、 O'Reilly Japan - コンピュータシステムの理論と実装 に挑戦することにしました。 O'Reilly Japan - コンピュータシステムの理論と実装 成果物は以下のリポジトリに置いてあります。 yuroyoro/nand2tetris 結論から言うと、やってみて大変楽しめました！ 特にハードウェア周りは今まで挑戦したこ
質とスピード（2020秋100分拡大版） / Quality and Speed 2020 Autumn Edition
質とスピード（2020秋100分拡大版） 2020/11/20 @ JaSST'20 Kyushu
ゼロから学ぶ C++
ホーム 1. C++ を始める 2. 基本構文 3. コンテナ 4. ファイル分割とスコープ 5. ストリーム操作 6. メモリの管理 7. クラス 8. キャスト 9. テンプレート 10. エラー処理 11. ビルドとライブラリ 12. メモリレイアウト 単体テスト デバッグ ビルド自動化 付録 このサイトは C++ について説明した学習サイトです。 本書を通じて C++ の開発環境や構文・単体テストの書き方などが 一通り学べるようになっています。 対象¶ C++ を初めて学ぶ人 プログラム言語を 1 つ以上経験したことのある人 関数やクラス・オブジェクト指向に対する知識をある程度前提にします。 C++ の特徴¶ C++ は ビャーネ・ストロヴストルップ により開発されたプログラミング言語です。 C++ には主に次のような特徴があります。 高パフォーマンス メモリ使用量が少ない 柔軟性
C++ の学習サイトを作りました - Qiita
はじめに C++ って他の言語に比べると勉強しづらくないですか？ 書籍や学習サイトの内容が古い、または少ないんですよね。ただでさえ言語仕様が複雑なのに、それを手助けする情報も少ないと初学者には辛いんじゃないかと思います。というか僕がそうでした。 そんなわけで、もう少し今風な学習サイトを作ろうと思って作成しました。 ゼロから学ぶ C++ ちゃんとスマホでも読めるようになっています。 C++11 をベースに作っているので、このサイトももはや古い方に入るかも知れませんが、C++20 が浸透してきたらアップデートしようと思います。 よかったらご活用下さい。 ゼロから学ぶ Python（姉妹サイト） 『ゼロから学ぶ Python』というサイトも作成しています。あわせてご活用下さい。 さいごに 上記のサイトはどちらも GitHub でソースコードを管理しています。 スターを付けてもらうと励みになります
Early Work
初期の作品 --- Early Work Paul Graham, October 2020 これは、Paul Graham： Early Work を、原著者の許可を得て翻訳・公開するものです。 <版権表示> 本和訳テキストの複製、変更、再配布は、この版権表示を残す限り、自由に行って結構です。 (「この版権表示」には上の文も含まれます。すなわち、再配布を禁止してはいけません)。 Copyright 2020 by Paul Graham 原文: http://www.paulgraham.com/early.html 日本語訳：Shiro Kawai (shiro ＠ acm.org) <版権表示終り> Paul Graham氏のエッセイをまとめた『ハッカーと画家』の 邦訳版が出版されました。 出版社の案内ページ Amazon.co.jp サポートページ 2020/10/20 翻訳公開
なぜ我々は頑なにforを避けるのか - Qiita
動機 前回の記事を投稿したことを某SNSで通知したところ、そのSNSでこんなコメントをいただいた。転記する許可を取ったわけでは無いので私なりに要約させていただくと、 なぜそんなトリッキーな書き方をしてまでforを使うのを避けるのか そんな書き方をして可読性を下げるくらいなら素直にforを使う方が良い ということだと理解している。 なるほど、一理ありそうだ。しかし一方で、前回貼ったStackOverflowのQ&Aはなかなかの人気記事（質問に1243ポイント、回答に最大で1559ポイント）なので「多少トリッキーなことをしてでもforを書きたくない！！」という意見をもつプログラマも一定以上いるのだろう。当然私もその1人だ。 ということで、この記事で「なぜそこまで意固地になってまでforを書きたくないのか」を説明することにする。 尚、今回は前回の記事つながりで言語はJavaScriptを使うが、
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
