DFSの基本ということですがまだ理解が追い付いていません。 もう少し勉強します。 問題 https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_11_B 考察 最初に訪問した時間とその頂点に戻ってきた時間を記録する，ということですが戻ってきた時間をどう記録し…

問題 C - 収集王 検討 10^6*10^6と非常に大きな領域だけどデータセットは10^3以下なので必要なところだけ計算することを考えましたが，まだTLEします。また，飴のあるマスは縦横に二重にカウントしているので，その部分を調整することを考えました。しかしWA…

問題 https://www.ioi-jp.org/joi/2007/2008-ho-prob_and_sol/2008-ho.pdf#page=6 ダーツを４本まで投げ上限Mを超えない得点の最大値を求めます。 得点はP[N]でN 考察 普通にループを回すのでは1000^4=１兆になりとても間に合いません。 二分探索のパワーを…

問題 D - 射撃王非常に難しくて詰まりました。この手の特殊な関数を立てて二分探索する問題をたまに見ますが，二分探索の応用範囲の広さを感じます。 解説AC 解説見てもなかなか理解できませんでしたが，他の人の提出コードを参照しながら概ね理解できました…

問題 数列Tに含まれる要素の中で数列Sに含まれる要素の個数を出力する問題です。http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=ja 考察 基本通りの二分探索で実装しあっさりACしました。 #include <bits/stdc++.h> using namespace std; int bi</bits/stdc++.h>…

問題 チェス盤に互いに干渉しないように８つのクイーンを配置する問題です。有名な問題のようです。すでにいくつかクイーンが置かれている入力に対し，１通りだけ配置可能な組み合わせがあります。http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id…

問題 考察 ACしたコード 問題 C - Count Order 考察 辞書順で出力するのにどうしようか悩みましたがnext_permutationがそもそも辞書順で次の順列を出力する関数なので心配無用でした。配列の比較がシンプルにできるのに改めて気づきました。 最初は要素を１…

問題と考察 WAしたコード 考察 ACしたコード 精選を順番に解いています。 bit全探索も大詰めに来ました。 問題と考察 色の違うビルが直線上に並んでいます。 うしろのビルは，前のビルよりも高くないと見えません。正面から見てK色以上の色が見えるようにす…

ほとんど解いたことがある問題ばかりでしたが精選７～１３をやりました。 ７ 最古の遺跡 12 派閥 13 おせんべい ７ 最古の遺跡 C - 最古の遺跡四角形ができるかの判別に幾何の知識が必要です。ABC108BのRuined Squareはこの問題からとってるのでしょうね。B …

atcoder.jp ARC106参戦記 2020年10月24日21:00-22:40に開催されたARC106に参戦しました。 １完１ペナ23:55秒でパフォーマンスは638。 レートは794から14下がって780になりました。Contest Result - AtCoder A問題 ３のA乗と５のB乗の和で10e18以下の数Nをつ…

はじめに 精選100問をちゃんと埋めることにしました。 以前やりかけり，すでに解いた問題が混じってますが，改めてやってみます。レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 - Qiita 問題 精選６ N文字（N…

問題 現在の満腹度はHです。 N日間の間，普通の食事をするとA円出費し満腹度がB増えます。 質素な食事をするとC円出費し満腹度がD増えます。 食事をしないと満腹度がE減ります。 満腹度を０以下にせずN日過ごす場合の最低の出費額を求めます。C - 節制 考察 …

はじめに 問題 考察 WAしたコード（デバッグ用出力入れてます） ACしたコード 考察 更に考察 はじめに しばらく使ってないと使い方を忘れてしまいそうなnext_permutationですがABCのC埋めで埋まっていない問題ででてきました。世間の解説記事にはnext_permut…

はじめに A問題 B問題 C問題 ACしたコード D問題 WAしたコード ACしたコード D問題の反省 E問題 記念提出してWAしたコード ACしたコード ２度目の色落ちしてみて はじめに 2020年10月17日20:00から開催されたABC180に参戦しました。結果は１５分０５秒ノーペ…

問題 https://www.ioi-jp.org/joi/2009/2010-ho-prob_and_sol/2010-ho.pdf#page=7N本のつららが一定のルール（隣のつららより長い場合に単位時間あたり１）で伸びてきて長さLに達したら折れます。すべてのつららが折れるまでの時間を出力します。 考察 とな…

はじめに A問題 提出コード B問題 ACしたコード C問題以下 まとめ はじめに 2020年10月11日22:30からARC105に出場しました。ABの２完 １ペナ 1593/3806位 パフォ979でレーティングは21あがって807に。 ４回ぶりに再入緑しhighestを更新しました。 A問題 ４つ…

はじめに A問題 提出コード B問題 提出コード C問題 ACしたコード D問題 まとめ はじめに 2020年10月10日21:00～HHKBプログラミングコンテスト2020に参加しました。結果は27;55 ノーペナルティ3完で2622/6097位。 パフォ843でレーティングは779から7あがって…

問題 D - トランプ挿入ソート数字のかかれたＮ枚のカードから１枚を抜き取り好きな場所に挿入するという操作を何回くりかえすと昇順にソートできますか、という問題です。 考察 いろいろ考えましたが思いつきませんでした。 最長の増加部分列がわかればその…

問題 検討 ACしたコード 問題 D - Leaping Tak 検討 解説ACです。 本番で解いているときは問題自体を誤読していました。問題を正しく理解したあとは、区間の和がたくさんでてくるので累積和を使うことは思い至りましたが、前計算で累積和を用意しておく普通…

問題 第８回日本情報オリンピック 本選（2009 オンライン） B ピザhttps://www.ioi-jp.org/joi/2008/2009-ho-prob_and_sol/2009-ho.pdf#page=4JOI難易度６を進めています。だいぶ難しい問題が増えてきました。 この問題はなんとか自力ACできました。 検討 円…

はじめに A問題 B問題 考察 TLEしたコード 更に考察 ACしたコード C問題 反省 はじめに ARC104は２完パフォ608で前回に続いて冷えてレート-18で新レート779になりました。 続けざまに冷えてちょっと悲しいですが冷える回こそ力をつける回です。一喜一憂せず…

問題 n種類の数aiがそれぞれmi個づつあります。 これらの中からいくつか選び，その総和をちょうどKとすることができるかを判定します。制約1 1 1 コード 今日はここまでの理解。途中 |= で論理和をとった結果で置き換えるのは+=とか-=と同じ書き方ですね。ど…

文字と文字コードの相互変換 ord() chr() 使用例 文字と文字コードの相互変換 ord() chr() 文字と文字コードの相互変換です。 ord(c)で文字cの文字コード（unicode)を返します。 chr(n)で文字コードnの文字を出力します。ord('A')=65 ord('a')=97 使用例 A -…