深さ優先探索

AtCoder版！蟻本の深さ優先探索で類題としてあげられているARC031 BをPythonで解いていきます。 再帰関数を使用して解いています。 atcoder.jp AtCoder Regular Contest 031 B - 埋め立て 問題文 とある所に島国がありました。島国にはいくつかの島があります。このたび、この島国で埋め立て計画が立案されたのですが、どこを埋め立てるか決まっていません。できることなら埋め立てによって島を繋いで、1 つの島にしてしまいたいのですが、たくさん埋め立てるわけにもいきません。 10 マス × 10 マスのこの島国の地図が与えられるので、1 マスを埋め立てた時…

AtCoder版！蟻本の深さ優先探索で類題としてあげられているATC001 AをPythonで解いていきます。 深さ優先探索（DFS）は初めて見たとき難しく感じましたが、何問か解くとイメージがわいてきました。 理解しないと使いこなせないと思いますので頑張って取り組んでいきます。 atcoder.jp AtCoder Typical Contest 001 A - 深さ優先探索 問題文 高橋君の住む街は長方形の形をしており、格子状の区画に区切られています。 長方形の各辺は東西及び南北に並行です。 各区画は道または塀のどちらかであり、高橋君は道を東西南北に移動できますが斜めには移動できません。 ま…

新年あけましておめでとうございます！！（おそっ）今日も "初中級者が解くべき過去問精選 100 問" を解いていきたいと思います！ 精選100問って何？ 過去の記事についてはこちら！！ 全探索シリーズ 第１回：全列挙 第２回：工夫して通り数を減らす全列挙 第３回：ビット全探索 第４回：順列全探索 第５回：二分探索 深さ優先探索 24. Depth First Search 25. How Many Islands? 26. D - Ki 27. D - 薄氷渡り 最後に 精選100問って何？ 記事はこちら！ qiita.com こんなに丁寧にまとめてくださっている e869120 さんには本当…

はじめに 深さ優先探索とは 実装例 再帰を利用した深さ優先探索 おわりに 関連記事 参考 はじめに こんにちは．talosです．今回は深さ優先探索について説明します．初心者でもわかるように簡潔に書いているので，初心者中の初心者の方にもおすすめです．幅優先探索はこちら talosta.hatenablog.com 深さ優先探索とは 深さ優先探索はグラフの探索方法の1つです．できる限り奥まで探索して，行き止まりになったら分岐点まで戻って探索を繰り返す方法です．例えば，あなたが部屋でスマホをなくしたとします．ある隣の部屋からなるべく奥の部屋まで探して，見つからなければ最初の部屋に戻り，別の隣の部屋か…

◀︎ 前へ｜次へ ▶︎️ 配列A[1]，A[2]，…，A[n]で，A[1]を根とし，A[i]の左側の子をA[2i]，右側の子をA[2i+1]とみなすことによって，2分木を表現する。このとき，配列を先頭から順に調べていくことは，2分木の探索のどれに当たるか。 行きがけ順（先行順）深さ優先探索 帰りがけ順（後行順）深さ優先探索 通りがけ順（中間順）深さ優先探索 幅優先探索 // 解答 エ 解説 行きがけ順（先行順）深さ優先探索作成中 帰りがけ順（後行順）深さ優先探索作成中 通りがけ順（中間順）深さ優先探索作成中 幅優先探索作成中 // 参考情報 分野・分類 分野 テクノロジ系 大分類 基礎理論 中…

目的 Atcoderで上を目指すべく頑張っている中でABC198を解いたので、解説してみる pypy7.3を使って解いている A問題 atcoder.jp 考察 与えられる、整数Nに対し1~N-1まで数え上げれば良さそう N<=15 のため全探索しても計算量的に問題なさそう A君に1つ挙げた場合、B君にはN-1つあげることになるので、A君にあげる数に着目し数え上げれば良さそう 実装 N = int(input()) ans = 0 for n in range(1, N): ans += 1 print(ans) 結果 無事に解けた B問題 atcoder.jp 考察 回文かどうかは、文字の両…

47分2ペナ5完で271位でした。黄パフォ！AGCで溶かしたレートを取り返したぜ。 atcoder.jp A - Div Aくんが得るお菓子の個数が1個,2個,…,N-1個となるので、答えはN-1通りとなります。 B - Palindrome with leading zeros 先頭に0をつけることで回文にできる→末尾の0を削除することで回文にできる、という言い換えは典型っぽい。入力を反転して0の間文字を消去してできる文字列が回文かどうか判定すればいいです。 文字列の回文判定は反転した文字列が元のものと等しいかをチェックすればいいんですが、毎回忘れてて普通にfor文で前後から見てチェックしち…

DFSを毎回自力で実装するのがめんどくさいのでAtcoder のKiの問題をclassで実装したのでメモとして残します 以下 利用したコード N,Q = map(int,input().split())Graph = [[]for _ in range(N)]operater = []for _ in range(N-1): a,b = map(int,input().split()) Graph[a-1].append(b-1) Graph[b-1].append(a-1)from collections import dequeq = deque()q.append(0)seen = [F…

AtCoder Beginners Selection，ABC196，ABC197に取り組み，全探索の問題を多く解くことが必要だと感じました．次は，これの「1-6. 「茶色コーダー」になるためのガイドライン」をやろうと思います：レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】 - Qiita AOJ 「Introduction To Programming I」 全探索 ABC144: B - 81 ABC150: B - Count ABC ABC122: B - ATCoder ABC136: B - Uneven Numbers ABC106:…

2021年4月3日開催のCodeforces Round #712 Div.2に参加した ABを解いた Cを復習する 問題へのリンク 解説へのリンク 問題概要 コンテスト中に考えたこと 解説の解法 提出

こんにちは、はじめまして。筑波大学附属駒場高等学校 3 年生（今年 4 月から東京大学に入学予定）の米田優峻（@e869120）と申します。私は競技プログラミング（競プロ）が趣味で、AtCoder・情報オリンピック・パソコン甲子園などの大会に出場しています。2021 年 3 月時点で、AtCoder では赤色（レッドコーダー）です。また、国際情報オリンピックの 2018 年／2019 年／2020 年大会で金メダルを獲得しています。*1 とはいえ、決して簡単にこの記録を手に入れられたわけではありません。何度も挫折と失敗を経験しながら自分のスキルを磨いた結果、競プロを始めてから 3 年後にはレッ…

- はじめに - Pythonのパッケージ管理ツールは、長らく乱世にあると言える。特にpip、pipenv、poetryというツールの登場シーン前後では、多くの変革がもたらされた。本記事は、Pythonパッケージ管理ツールであるpip、pipenv、poetryの3つに着目し、それぞれのツールに対してフラットな背景、技術的な説明を示しながら、所属企業内にてpoetry移行大臣として1年活動した上での経験、移行の意図について綴り、今後のPythonパッケージ管理の展望について妄想するものである。 注意：本記事はPythonパッケージ管理のベストプラクティスを主張する記事ではありません。背景を理解…

今週のタイムライン エネルギーを与えた出来事（幸せになった・安心した） 仲間の送別会をした（火曜日） MaxSATの勉強をした（火曜日） 経路探索アルゴリズムに興味が出た（木曜日） Search Inside Yourselfを読み始めた（木曜日） スクラムイベントの順番を変えてみた（木曜日） エネルギーを奪った出来事（悲しくなった・不幸になったなど） 低気圧がすごかった（日曜日） 感情によって自分の行動が変わってしまっていること（水曜日） 戸惑った出来事や疑問に思った出来事 Doneにならない前提でプランニング時にアイテムを取ることはどうなんだろうか？（木曜日） 話したいこと 感情によって自…

スタメンエンジニアの井本です。 普段の業務ではRuby on Railsを用いた機能開発を担当しています。 前職である電気回路の設計エンジニアからWebエンジニアに転身し、11月から働いています。 スタメンでは、エンジニアの技術力向上に力を入れており、社内勉強会を積極的に実施しています。 今回は、私が11月〜12月に参加した「みんなのコンピュータ・サイエンス勉強会」についての記事です。 当記事のトピックは大きく2つ。 1. 勉強会のレポート 2. 勉強会の中でRubyで実装したアルゴリズムについて 1においては、エンジニアとしてスタメンで働くことで、どのような環境でどう成長できるか？イメージす…

AtCoderの学習のためこちらの記事で紹介されている初中級者が解くべき過去問精選100 問に取り組みました。 レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 - Qiita問題数が多いため分野ごとに分けて記載した記事を紹介します。 目次 目次 全探索：全列挙 全探索：工夫して通り数を減らす全列挙 全探索：ビット全探索 全探索：順列全探索 二分探索 深さ優先探索（以下作成中です m(_ _)m） 幅優先探索 動的計画法：ナップザック DP 動的計画法：区間 DP 動的計画法：bit DP 動的計画法：その他 最短経路問題：ダイクストラ法 最短経…

2021/3/20に開催されたAtCoder Beginner Contest 196に参加しました。 atcoder.jp 前回のABCコンテストは3完という微妙な成績。今回は少なくとも4完以上を目指そうという気持ちで臨みます。 参加いたします。前回微妙な成績だったので、今度は4完以上目標。レートを落とさないよう頑張ります。AtCoder Beginner Contest 196 - AtCoder https://t.co/XoX7JZesIc— devgenjin77 (@devgenjin77) 2021年3月20日 今回の結果 で、今回の結果はノルマ達成の4完で終了でした。 ABC1…