AOJ
問題 Identity Function | Aizu Online Judge 問題概要 1より大きい整数が与えられる。次のような関数を考える： この時、のについてが成り立つような最小のを求めよ。このようなが存在しない時は、-1を出力せよ。 アイデア まず、考察したこととしては、が…
問題 Traffic Tree | Aizu Online Judge 問題概要 頂点数の木が与えられる(番目の辺は頂点とを結ぶ)。 隣接する頂点に移動するコストを1であるとすると、各頂点について、その頂点をスタート地点とした時に全ての頂点を訪れるための最小コストを求めよ。 ア…
問題 Minus One | Aizu Online Judge 問題概要 頂点辺の無向グラフと頂点番号が与えられる。この無向グラフに辺を1つ足すことによって、もとのグラフにおけるからへの最短経路長よりも1だけ短くすることができるようなは何通りあるか。 からへはたどり着ける…
問題 Bingo | Aizu Online Judge 問題概要 ビンゴカードは正方形となっているが，実際これは1次元配列として考えても差し支えがない． つまり，「要素数がで，各要素の値が以上以下で，全ての要素の合計がであるような厳密に単調増加する数列として考えられ…
問題 Princess, a Cryptanalyst | Aizu Online Judge 問題概要 個の文字列が与えられる．この個の文字列に対してSSS(Shortest Secret String)を求めたい．SSSとは，個の文字列を全て部分文字列として含み，なおかつその長さが最小であるような文字列のことを…
問題 Sightseeing Tour | Aizu Online Judge 問題概要 はじめ、頂点数の完全無向グラフが与えられる。これらの無向辺をすべて、有効辺に置き換えることにした(頂点と頂点の間の辺は→か→のどちらかのみが張られる)。そのときのコストがで与えられる。全ての頂…
問題 Shredding Company | Aizu Online Judge 概要 6桁以下の数が書かれた紙がある。それを切って、いくつかの整数を作る。その整数の和がt以下になるもので、最大になる切り方を求め、その整数の組合せとその和を出力せよ。 ただし特殊な例として、どんな切…
問題 Butterfly | Aizu Online Judge 概要 n人の男とのデート予定がある。 デート予定は1時間区切りで6~22時の間で、複数の区間になることもある。 (例だとAdamは10~12,14~16でBobは12~13,18~20) それぞれの男からは全てのデート予定をこなすと満足度Liを得…
・問題 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の値をそ…
・問題 Edit Distance (Levenshtein Distance) | Aizu Online Judge 前期の授業でやったレーベンシュタイン距離。・アイデア 空の文字列の状態から考えて、s1のi文字目までの部分列とs2のj文字目までの部分列に対して、挿入・削除・置換のいずれかの操作を行…
・問題 Knapsack Problem | Aizu Online Judge前の問題から若干問題を変えて、１つの商品を何個でも入れることができるという制約に変わった。・考え方 前の問題に倣い、 dp[i][j]:=品物1~iの中から選び、ナップサックの大きさがjの時に入れられる商品の価値…
・問題 0-1 Knapsack Problem | Aizu Online Judgeいわゆる普通のナップサック問題。制約とかも普通。・考え方 dp[i][j]:=品物(i-1)まで入れるかどうか決まっていて、その時の重さがjの時の価値合計の最大値と定義して、全てやり終わった後にdp[N][i]の列をi…
DP力を高めるためにせっかくいい問題集があるのだから使ってみるという試み。今日からこれをやっていこうと思う。2日後にはコンテストなわけだが。。。・問題 Coin Changing Problem | Aizu Online Judgec1,c2, ... ,cm円というm種類のコインを使い、n円を支…
And Then There Was One | Aizu Online Judgeどうやら割と有名な問題らしい(ヨセフスの問題 - Wikipedia)。 考え方が印象に残ったのでざっくりメモ。n人で構成された輪があり，はじめの基準位置の人(ここではNo.0と呼ぶ)からk-1だけ先にいる人(つまりNo.k-1)…
Country Road | Aizu Online Judge・概要 n個の家に対してk個の発電機を設置してできるだけ電線を短くしよう (n,k・アイデア 各家に対して，どの発電機から電気をもらうのがベストかといえば，一番近いやつだよな n個のものをk組に分ける方法を考えてその端…
・内容 Mysterious Worm | Aizu Online Judge赤青緑の3色あって， 文字列の隣り合う2色が違うとき，そのどちらの色でもない色に変化しうる。 そのとき与えられた文字列が1色になるまでにかかる最短時間は?・アイデア 問題文に貼り付けられた図を見てうわっむ…
Split Up! | Aizu Online Judge・概要 n個の正の整数が与えられた時，それらを2つのグループに分けてそれぞれのグループの整数の和をとったとき，それらの差が最小となるときの値を求める(n 各々の整数は1000000未満・アイデア n個の整数の合計sumとして，su…
Darts | Aizu Online Judge・概要 与えられた値から重複を許して4個以下の値をn種類の中から選び，m以下となる最大の和を求める。 n m・アイデアあれ？これdpでできんじゃね？→コメント部のようなメモ化再起を書く→できないどうやら最大の値を選んでしまって…
・概要以下の自然数を個使って和がになる組み合わせの数を求めよ。（ただし個の数は互いにすべて異なる）・アイデアー ループは書けないからDFSしようー そのままだと多すぎて間に合わない，ー だからメモ化しよう...今何個目を足しているか，和からすでに足…
