ACPC freshmen training

ACPC freshmen training内検索 / 「AOJ0202 At Boss's Expense」で検索した結果

• AOJ0202 At Boss's Expense
  AOJ0202 At Boss s Expense サイト http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0202 解説 上限金額が決まっていて、与えられた料理の金額を使ってそれぞれ0個以上用いて割り切れない最大の金額を求める。 「割り切れない」はすなわちその値が素数であることを示す。 「割り切れない」の意味が分かったので、取り敢えず「割り切れない」は横において、今度は問題の残りの部分の解釈に移る。 それぞれの料理を使う個数を決めて上限の金額を超えるまで全探索することはとてもできない。 添字が上限金額まで記憶可能なbool型の配列を用意して可能な合計金額をマーキングをしていこう。ある料理の値段を用いて新しくマークを付けるとき、既知のマークを始点としてある料理の金額分先にマーキングできる。初期条件としては合計金額が0円であ...
• Dynamic programming
  ...st Grader AOJ0202 At Boss s Expense BIT DP AOJ0120 Patisserie Various method Imos, Segtree, Fenwick AOJ2331 A Way to Invite Friends
• AOJ0120 Patisserie
  AOJ0120 Patisserie サイト http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0120 解説 n =12なのでビットDPができる。そこで以下の2つの解法を示す。 巡回セールスマン問題(TSP) BitDP + メモ化再帰 解法 TSP 2円が接して並んでいるとき、それぞれの中心から床に垂線を下ろして、垂線間の距離を取って円と円の幅のようなものを得る。図に描くと分かるが三平方の定理より √{(r1+r2)^2-(r1-r2)^2} で求まる。すべての2円間でこの距離を求めておき、あとは「うまく円を並べることにより距離の和が最小」になるようできれば与えられた直方体の幅と比較できる。この問いに答えれば解けるがどうすれば可能であるか。 円がA, B, C, D, Eと5つある時のことを考えよう。Aを固定して...
• Graph
  Graph Depth First Search Breadth First Search AOJ1166 Amazing Mazes Dijkstra AOJ1156 Twirling Robot Euler circuit UVa10129 Play on Words Traveling Salesman Problem AOJ0120 Patisserie
• AOJ0557 A First Grader
  AOJ0557 A First Grader サイト http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0557 参考サイト http //d.hatena.ne.jp/Respect2D/20110212/1297501157 https //speakerdeck.com/kagamiz/aoj-0557-a-first-grader-jie-shuo 解説 +と-の2択を選びつつ様々な制限の元ansに一致する場合数を列挙します。 2択で処理を進めるので全探索するとO(2^n)です。取りあえず再帰で全探索コードを考えてみましょう。 数列の今見ている項とそこまでの計算結果の2つの状態が必要です。 終了条件でansと計算結果が一致していれば場合の数が1つ生じます。以下のコード上では例外処理が省略されています。 int rec(...
• String processing and parsing
  String processing and parsing Recursive Descent Parsing AOJ1155 How can I satisfy thee? Let me count the ways... Tree AOJ1001 Binary Tree Intersection And Union String AOJ1188 Hierarchical Democracy AOJ2261 ［［iwi］］ UVa11151 Longest Palindrome
• AOJ1156 Twirling Robot
  AOJ1156 Twirling Robot サイト http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1156 解説 コストが0, 若しくはc0, c1, c2, c3 で与えられるのでダイクストラする BFSは一種のダイクストラで、普通各ノード間のコストが1のときをいう ここで座標x, y, 方向, スタート地点からのコストの4つの要素を状態として持つ以下の様な構造体Stateを考える struct State { int x, y, d, cost; State() {} State(int x, int y, int d, int cost) x(x), y(y), d(d), cost(cost) {} ... }; これをpriority_queueに入れて解く。 （今回のようにノードの情報の要...
• AOJ1155 How can I satisfy thee? Let me count the ways...
  AOJ1155 How can I satisfy thee? Let me count the ways... サイト http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1155 lang=jp 問題俯瞰 問題は与えられた式をある規則によって計算した結果が2となるときのP, Q, Rの組み合わせ数を答えるものです。 P, Q, Rは0, 1, 2とそれぞれ値が変化するので３重ループのfor文で回して27通り試しそのたびに構文解析をし直せばよいです。 Sample Inputが 2 であり、その結果 27 を返すものがあります。これはP, Q, Rがそれぞれいかなる値でも常に計算結果が2であるのでP, Q, Rの組み合わせ数は27通りということを示します。 解説 以下の与えられたBNF(*1)に従って再帰的下向き構文解析のコー...
• プラグイン/ニュース
  ニュース @wikiのwikiモードでは #news(興味のある単語) と入力することで、あるキーワードに関連するニュース一覧を表示することができます 詳しくはこちらをご覧ください。 ＝＞http //atwiki.jp/guide/17_174_ja.html たとえば、#news(wiki)と入力すると以下のように表示されます。 【クリスマス2021】高本彩花｜ひなこい - ひなこい攻略Wiki - Gamerch(ゲーマチ) 【カウンターサイド】リセマラ当たりランキング - カウサイ攻略Wiki - Gamerch(ゲーマチ) ウィキペディアを作ったiMacが箱付きで競売に登場。予想落札価格は約96万円！（ギズモード・ジャパン） - Yahoo!ニュース - Yahoo!ニュース 【テイルズオブルミナリア】リセマラ当たりランキング - TOル...
• @wiki全体から「AOJ0202 At Boss's Expense」で調べる

更新順にページ一覧表示 | 作成順にページ一覧表示 | ページ名順にページ一覧表示 | wiki内検索