裏紙

ほぼ競プロ、たまに日記

AOJ

AOJ 2608 - Minus One

問題 Minus One | Aizu Online Judge 問題概要 頂点辺の無向グラフと頂点番号が与えられる。この無向グラフに辺を1つ足すことによって、もとのグラフにおけるからへの最短経路長よりも1だけ短くすることができるようなは何通りあるか。 からへはたどり着ける…

AOJ 0537 - Bingo

問題 Bingo | Aizu Online Judge 問題概要 ビンゴカードは正方形となっているが,実際これは1次元配列として考えても差し支えがない. つまり,「要素数がで,各要素の値が以上以下で,全ての要素の合計がであるような厳密に単調増加する数列として考えられ…

AOJ 2022 - Princess, a Cryptanalyst

問題 Princess, a Cryptanalyst | Aizu Online Judge 問題概要 個の文字列が与えられる.この個の文字列に対してSSS(Shortest Secret String)を求めたい.SSSとは,個の文字列を全て部分文字列として含み,なおかつその長さが最小であるような文字列のことを…

AOJ 2386 - Sightseeing Tour

問題 Sightseeing Tour | Aizu Online Judge 問題概要 はじめ、頂点数の完全無向グラフが与えられる。これらの無向辺をすべて、有効辺に置き換えることにした(頂点と頂点の間の辺は→か→のどちらかのみが張られる)。そのときのコストがで与えられる。全ての頂…

AOJ 1237 - Shredding Company

問題 Shredding Company | Aizu Online Judge 概要 6桁以下の数が書かれた紙がある。それを切って、いくつかの整数を作る。その整数の和がt以下になるもので、最大になる切り方を求め、その整数の組合せとその和を出力せよ。 ただし特殊な例として、どんな切…

AOJ 2321 - Butterfly

問題 Butterfly | Aizu Online Judge 概要 n人の男とのデート予定がある。 デート予定は1時間区切りで6~22時の間で、複数の区間になることもある。 (例だとAdamは10~12,14~16でBobは12~13,18~20) それぞれの男からは全てのデート予定をこなすと満足度Liを得…

AOJ 2199 - Differential Pulse Code Modulation

・問題 Differential Pulse Code Modulation | Aizu Online Judge元の数列x(size y_0=128から始めて、y_1=y_0+C[k_1], ... , y_n=y_n-1+C[k_n]という容量で数列yを決定する。この過程で、yの値が0未満になるときは0、255より大きくなるときは255にyの値をそ…

AOJ DPL1_E - Edit Distance (Levenshtein Distance)

・問題 Edit Distance (Levenshtein Distance) | Aizu Online Judge 前期の授業でやったレーベンシュタイン距離。・アイデア 空の文字列の状態から考えて、s1のi文字目までの部分列とs2のj文字目までの部分列に対して、挿入・削除・置換のいずれかの操作を行…

AOJ DPL1_C - Knapsack Problem

・問題 Knapsack Problem | Aizu Online Judge前の問題から若干問題を変えて、1つの商品を何個でも入れることができるという制約に変わった。・考え方 前の問題に倣い、 dp[i][j]:=品物1~iの中から選び、ナップサックの大きさがjの時に入れられる商品の価値…

AOJ DPL1_B - 0-1 Knapsack Problem

・問題 0-1 Knapsack Problem | Aizu Online Judgeいわゆる普通のナップサック問題。制約とかも普通。・考え方 dp[i][j]:=品物(i-1)まで入れるかどうか決まっていて、その時の重さがjの時の価値合計の最大値と定義して、全てやり終わった後にdp[N][i]の列をi…

AOJ DPL1_A - Coin Changing Problem

DP力を高めるためにせっかくいい問題集があるのだから使ってみるという試み。今日からこれをやっていこうと思う。2日後にはコンテストなわけだが。。。・問題 Coin Changing Problem | Aizu Online Judgec1,c2, ... ,cm円というm種類のコインを使い、n円を支…

AOJ 1275 - And Then There Was One

AOJ

And Then There Was One | Aizu Online Judgeどうやら割と有名な問題らしい(ヨセフスの問題 - Wikipedia)。 考え方が印象に残ったのでざっくりメモ。n人で構成された輪があり,はじめの基準位置の人(ここではNo.0と呼ぶ)からk-1だけ先にいる人(つまりNo.k-1)…

AOJ 2104 - Country Road

Country Road | Aizu Online Judge・概要 n個の家に対してk個の発電機を設置してできるだけ電線を短くしよう (n,k・アイデア 各家に対して,どの発電機から電気をもらうのがベストかといえば,一番近いやつだよな n個のものをk組に分ける方法を考えてその端…

AOJ 0179 - Mysterious Worm

・内容 Mysterious Worm | Aizu Online Judge赤青緑の3色あって, 文字列の隣り合う2色が違うとき,そのどちらの色でもない色に変化しうる。 そのとき与えられた文字列が1色になるまでにかかる最短時間は?・アイデア 問題文に貼り付けられた図を見てうわっむ…

AOJ 1045 - Split Up!

Split Up! | Aizu Online Judge・概要 n個の正の整数が与えられた時,それらを2つのグループに分けてそれぞれのグループの整数の和をとったとき,それらの差が最小となるときの値を求める(n 各々の整数は1000000未満・アイデア n個の整数の合計sumとして,su…

AOJ 0529 - Darts

Darts | Aizu Online Judge・概要 与えられた値から重複を許して4個以下の値をn種類の中から選び,m以下となる最大の和を求める。 n m・アイデアあれ?これdpでできんじゃね?→コメント部のようなメモ化再起を書く→できないどうやら最大の値を選んでしまって…

AOJ 1335 - Equal Sum Sets

・概要以下の自然数を個使って和がになる組み合わせの数を求めよ。(ただし個の数は互いにすべて異なる)・アイデアー ループは書けないからDFSしようー そのままだと多すぎて間に合わない,ー だからメモ化しよう...今何個目を足しているか,和からすでに足…