atcoder.jp 最長経路問題 トポロジカルソート DP この二つの組み合わせの問題だった.DPを実行するためにまず初めにトポロジカルソートをした.トポロジカルソートに関しては以前書いたので省く. トポロジカルソート 今回はトポロジカルソート済みとしてDPを行…

トポロジカルソートを書いてみたので記録しておく. ToplogocalSortとは. edgeをソートする方法の一種である。並び替えをします.ソートされた後の配列をみた時に配列の左から右向きのpathは存在するが右から左むきのpathは存在しないようにするということです…

atcoder.jp LCS(Longest Common Subsequence)最長経路問題です。 問題 文字列s , tが与えられた時に共通部分列で最長の物を求める. 最初全探索するのかと思ったが明らかに実行時間が間に合わない。それならばDPだろう.今回のDPの定義としては lcs[i][j] : 文…

atcoder.jp ナップザック問題のversion2.価値に制限がある場合.重さに制限がある場合と解き方が異なります. 提出 DPで解く ナップザック問題といえばおなじみのDPですが今回はDPの定義が難しい.いつもの重さに制限がある場合は dp[i][j] : i 個まで見た時の…

DP(1次元)と全探索の複合問題 abc099.contest.atcoder.jp この問題はこちらにも書いてある通りC問題にしては難しいです.しっかり理解したい方はこの記事読んだ方が100倍わかりやすいです。 提出コード 問題 1 , 6p , 9q のうちから好きな数を選び取り合計をn…

atcoder.jp 考察できるかの問題でした。数学できる人には簡単かもしれない。 問題文に翻弄されてはいけない 問題文では時刻iの時に右にも行けるし左に戻ることもできると示されている。しかし実際問題左に行く必要がなかったのだ。 左に行くくらいなら何もせ…

atcoder.jp ASCIIコードとCharコードを変換してときました。 それぞれの文字に共通して含まれるアルファベットを見つけなくてはならなかったので数字の方が扱いやすいと考えてアルファベットをASCIIコードに変換しました。 int number = ( int ) str . charA…

atcoder.jp class Pair を定義しようの回でした。(x,y）今回でいうと(出席番号,身長)の組みが与えられてその時に身長順でソートしようという問題です.絶対に(出席番号,身長)の組みを変えてはいけないということです。変えてしまうと自分の身長が他人お身長と…

atcoder.jp いもす法 いもす法聞いたことがあるだろうか。私はこの問題で初めてであった。多次元でもできるようが今回は一次元での問題なので理解することができた。 解説こちらのAtCoderの公式解説を見るのが一番わかりやすかった。(他のサイトも探したが次…

atcoder.jp まだまだC問題で苦戦してしまいます。脳筋で全探索だと考えてしまった。 この問題for分の4重ループで通ってしまうのです。 提出コード ABC074C 2WAしてしまいました。サンプルケースは通ったのでいけるかと思ったがダメでした。どこがダメかにら…

atcoder.jp C問題.苦戦しました. 考察 考察できませんでした。与えられたのが100とか出ていたので全探索するのかと思ったが解説を見て、全探索はダメですと言われて悲しくなった。 今回キーとなる考え方は、100点２問よりも200点２問といたほうがポイントが…

問題 これ本当にBですか?? 難しすぎてわからなかった 考察 500円玉先に与えて作ってから500円玉を100円玉*5枚など小さいコインに変換して行こうとした。コーそもかけずよくわからず 解放 他人の解答チラ見してきたら天下の全探索を行なっていました。 for(50…

問題 橋を切断する問題。 解放 新しいクラスを作り(a,b)をbについて昇順にソートする. そこからは (a,b)のbの小さい方から見てbの直前の橋を切断していくを繰り返しました。 今回重要なのは考え方もそうだが新しいクラスの定義が重要でした。 正直言うとまだ…

問題 DPの初歩的な問題でした。 解法 dp[i] : i本のマッチを使った時の最大桁数。 と定義してdp[N]を求めようと考えます.ここでは桁数だけを先に考えてあとで実際の数字になにが入るかを復元します。 dp[0] = 0 これが初期条件になる。マッチ０本を使って作…