【yukicoder】No.37 遊園地のアトラクション
問題
週末yukicoder。ずっと動的計画法の練習です。
解法
おなじみ動的計画法で解きます。一度選んだアトラクションが再度選べるのとその際価値が前回の半分（切り捨て）になるところが、ちょっといつもの問題と違うところですね。
アトラクションの価値が元は]ですが、この配列に重複を含めた値も追加します。価値の最大は500なので、ずっと同じアトラクションに乗ることはなく、多くても９回です。
サンプル１でみると重複を含めたアトラクションの待ち時間と価値の配列は、
$$
\binom{c}{v}=\begin{pmatrix}
1 & 2 & 3 & 1 & 2\\
3 & 2 & 1 & 1 & 1 \\
\end{pmatrix}
$$
後ろ２列はアトラクション１の２回目、アトラクション２の２回目の待ち時間と価値です。
あとはこの重複を含めたアトラクションの配列を先頭から見ていって、の行列を作って解くだけです。
簡単な動的計画法の問題は【yukicoder】No.1 道のショートカットで解きましたのでそちらを参考ください。
Python3
コード
import math T=int(input()) N=int(input()) C=list(map(int,input().split())) V=list(map(int,input().split())) Z=list(zip(C,V)) Z2=Z[:] for z in Z: c=z[0] v=z[1] while True: v=math.floor(v/2) if v<=0: break Z2.append((c,v)) A=[[0]*(T+1) for i in range(len(Z2)+1)] for i in range(1,len(Z2)+1): for t in range(1,T+1): z=Z2[i-1] c=z[0] v=z[1] if t-c<0: A[i][t]=A[i-1][t] else: A[i][t]=max(A[i-1][t-c]+v,A[i-1][t]) print(max(list(map(max,A))))
【yukicoder】No.45 回転寿司
週末yukicoder。
問題
問題はこちら
解法
動的計画法です。
個のお寿司が手前に流れてきたときの美味しさの最大を
とします。この時
と定義しておきます。
の時はお寿司が１つだけなので、そのお寿司を取るしかないので、
の時について、場合を分けて考えてみます。
番目のお寿司をとった場合は、
となり、お寿司は２連続は取れないので自動的に
の関係になります。
番目のお寿司をとらなかった場合は、
となり、お寿司を３連続取らないと美味しさが損になるのでこの場合は
番目のお寿司をとった方がいいです。よって
となります。
したがって、番目のお寿司が流れてきたときの美味しさの最大は、
となります。
上の考えでを算出すればOKです。
Python3
コード
N=int(input()) V=list(map(int,input().split())) if N == 1: print(V[0]) else: A=[0]*(N+1) A[1]=V[0] for i in range(2,N+1): A[i] = max(A[i-1], A[i-2]+V[i-1]) print(A[N])
【yukicoder】No.1 道のショートカット
個の町々で目的の町を目指して、時間内にもっとも安い値段で辿り着く場合を求める問題です。
問題
問題はこちら
解法
動的計画法で解きます。
ちなみに動的計画法の参考記事では下記の記事がとてもわかりやすいです。
典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～ - Qiita
という行列を考えます。
問題のサンプル１では下記のような行列になります。（ここではコストの桁を１つ減らしています）
# 入力 3 10 3 1 2 1 2 3 3 1 9 1 10 10 50
$$
A=
\begin{pmatrix}
0 & N & N & N & N & N & N & N & N & N & N \\
N & 10 & N & N & N & N & N & N & N & N & N \\
N & 50 & N & N & N & N & N & N & N & N & 20 \\
\end{pmatrix}
$$
コストは０を含むので列は 列になるので注意です。
３行でもっともコストが低いのは20となり、これが答えです。
ただし行列の各値を計算する場合は、道順のスタートが 1,2,3, ... と若い順に見ていくように注意する必要があります。
Python3
コード
n=int(input()) c=int(input()) v=int(input()) S=list(map(int,input().split())) T=list(map(int,input().split())) Y=list(map(int,input().split())) M=list(map(int,input().split())) z=zip(S,T,Y,M) d=[[None]*(c+1) for i in range(n)] d[0][0] = 0 for s,t,y,m in sorted(z,key=lambda x:(x[0],x[1])): for j in range(c+1): a=d[s-1][j] if a is not None: q=y+j if c<q: break p=t-1 x=a+m if d[p][q] is None or x<d[p][q]: d[p][q]=x o=None for x in d[n-1]: if x is not None: if o is None or x<o: o=x print(-1 if o is None else o)
d=[[None]*(c+1) for i in range(n)]で 行
列の行列を各値
Noneで初期化しています。
for s,t,y,m in sorted(z,key=lambda x:(x[0],x[1])):で 1 → 2, 1 → 3, ... のように若い番号からの道順から計算するようにしています。d[0][0] = 0はスタート地点１の町は０時間かけて金額０円で行けることを意味します。
道順をループし到着する町 s の町、すなわち s-1 行目の列を見ていき、行列値 a の値が None でなければ、次の町 t へ行くまでにかかる時間を代入します。
このとき、金額の値（列数）が超えないようにするのと、経過時間が最小値になるように判定しておく必要があります。
【yukicoder】No.44 DPなすごろく
お馴染み yukicoder で勉強です。慣れてきたので簡単な問題はサクサクコードかけるようになってきました。
問題
問題はこちら
解法
動的計画法(DP: Dynamic Programming)です。中でも一番よく聞く簡単なフィボナッチ数列です。
]
数式にすると次の関係があります。
今回の問題では マス目に行くパターンの数を求めます。パターンの数を
とすると、
マス目に行くパターンは
マス目で１進む場合と、
マス目で２進む場合なので、
となります。
Python3
コード
n=int(input()) a=0 b=1 for i in range(n): t=a+b a=b b=t print(b)
【yukicoder】No.804 野菜が苦手
久々に競技プログラミングやります。やり方を忘れているので簡単な問題から徐々に思い出していきます。
問題
問題はこちら
解法
食べられる野菜の最大の数を とします。
すると問題分より下記の関係を満たす。
野菜の個数は最大 個
個の肉を食べる必要があるが、肉の個数は最大
個
野菜と肉を 個食べる必要があるが、合わせて最大
個までしか食べれない
したがって 、
、
を満たす最大の整数
を出力する。
Python3
Python久しぶりに書く。
コード
n=list(map(int,input().split())) x=n[3]//(n[2]+1) y=n[1]//n[2] a=x if x<y else y print(a if a<n[0] else n[0])
解法通りに各等式の右辺の商をとって、一番小さい商が答え。
再考
Pythonにminがあった（まぁ普通あるか）。これ使えば短く書ける。
n=list(map(int,input().split())) print(min(n[0], n[1] // n[2], n[3] // (n[2] + 1)))
2018年のことはじめ
2018年明けましたおめでとうございます。
以前の記事から今回の記事を書くまでに年が明けてしまいました。いろいろとあってあまり時間が取れなかったというのが言い訳で、「あまり」であって「全く」なかったわけでないので素直に反省すべきですね。
さて、以前から時間の合間を縫ってReact Nativeを勉強してきましたが、本格的にコードを書くことになりました。・・・なったのですが、アプリ側はある程度書けるようになってきているのでいいとして、サーバー側のシステムはRailsを利用していて、Railsの勉強をちゃんとやっておく方がいいのではと心積りをしています。
とりあえずはRails環境を立てて簡単なWEBページなりを作成することにしています。GithubリポジトリのWikiに勉強のまとめ書きをつけていっているが、記事にするかは分からない。ただ何某かの形で記事にしないと、冒頭の反省ができていないことになるのでなんとかしないといけないです。
React Native Elements を学ぶ (2)
前回に引き続き、React Native Elementsについて説明して行きます。
今回のコードの全体はこちらをご参照ください。
リストのクリック機能
さて、まずは下記画面のようにリストをクリックすると次の画面に遷移する機能について。
リスト項目にクリックイベントを設定するには、<ListItem>のonPressプロパティにクリック時のコールバック関数を渡すだけで実装することができます。リストを表示するコンポーネントのコードは下記のようになっています。
React Native Elementsの使い方(No.2)
リスト項目の作成は、前回説明した通りですが、今回はJSファイルにリストデータを分けて作成をしています。<ListItem>のonPressプロパティにreact-navigationのnavigate関数を設定して画面遷移の実装を行なっています。また、ここではリストデータにnavigateScreenプロパティを設けているリスト項目だけ画面遷移をさせるようにしています。
リストに表示されている「＞」のマークですが、こちらは<ListItem>の標準で表示されます。「＞」のマークを消したい場合は、hideChevron プロパティにtrueを設定すれは良いです。
今回は短いですがここまでにしておきます。次回はスイッチのあるリスト項目、またスライダーについて説明したいと思います。
