問題概要 アリスはクラスメート全員の為にアメを作る。 各クラスメートは飴を入れてもらう容器を提供し、 また各々は容器に入れてもらいたい重量を提示する。 アリスは一定の密度でアメを入れなければならない為、 各クラスメートの要望を聞き入れることがで…
SRM629 DIV2 250 問題概要 大きな穴がある(holeH×holeW)。 この穴を塞ぐための板がある(boardH×boardW)。 穴を板で塞ぐことができるか回答せよ。 塞ぐことができる場合は1を、できない場合は-1を返すこと。 ただし、穴と板の辺は平行でなければならない。 注…
Pythonでマージソート マージソートは配列を二つに分け、各々でソートし、最後にマージしてソートする。 ２つに分けた後のソートも同様な処理を再帰させて行うことができる。(分割統治法) マージソートは同じ値が存在した場合、配列の添字の順を維持すること…
関数 #coding: UTF-8 #関数 def max(num1, num2): if num1 > num2 : ret = num1 else: ret = num2 return ret a = 10 b = 5 print max(a,b) #10 参考文献 Pythonを学ぼう 第24回 関数の基礎 http://www.isl.ne.jp/pcsp/python/python24.html
Pythonで挿入ソート 挿入ソートとは、ソート済みの要素に、順に要素を適切な位置へ挿入することで、 すべての要素をソートさせる考え方。計算量はO(N^2)。 ただし、バブルソートより高速であることが多い(値の入れ替え処理が少なく済むため) コード(Python) …
Python練習で選択ソート 選択ソートは要素の中で一番小さい値を探し出し、要素の先頭と入れ替える。 以後、決定した要素を除外し、繰り返す。 計算量はO(N^2)である。 コード(Python) #coding: UTF-8 #選択ソート x = [4,50,3,10,88,39,2,15] for i in range…
Python練習でバブルソート バブルソートは隣接するデータを比較していき、値の一番大きなものから順に値を決定 させていく。計算量はO(N^2)。 コード(Python) #coding: UTF-8 #バブルソート x = [4,50,3,10,88,39,2,15] i=len(x) while i > 0: j = 1 while j …
繰り返し #coding: UTF-8 #繰り返し #while num = 0 while num < 2: print "num = " + str(num) num += 1 print "End" #whileの条件が偽となって時に実行する処理 num = 0 while num < 2: print "num = " + str(num) num += 1 else: print "The End" print "…
辞書型 #coding: UTF-8 #ディクショナリー dict = {"one":1, "two":2} #{キー1:値1, ....} #キーに指定できるのは変更できないオブジェクトのみ #数値、オブジェクト、タプル #キーを指定して値を取得 value = dict["one"] print value #値の更新 dict = {"y…
タプル #coding: UTF-8 #タプルの作成 tpl = (2005, 2006, 2007, 2008) tpl2 = (2005,) print tpl print tpl2 #リストの要素を取得 print tpl[0] #2005 print tpl[1] #2006 #タプルはリストと異なり、別のオブジェクトの代入ができない # tpl[1] = "b" #NG #…
リストの使い方 #coding: UTF-8 #リストの使い方 list = ["test","test2",3,4] print list[0] #test print list[1] #test2 print str(list[2])#3 print str(list[3])#4 #スライスを使った参照 print "[1:2] " , list[1:2] #['test2'] print "[1:-1] ", list[…
条件分岐 #coding: UTF-8 x = 0 y = 0 z = 0 #if文 インデントによりブロックを生成する if x == 0: print "x=0" if y == 1: print "y=0" if z == 0: print "z=0" #True:真、False:偽を示す予約語 if True: print "Always True" if False: print "NotPrintMe…
変数について #coding: UTF-8 msg = "Hello" print msg sum = 10 + 45 print sum #変数はオブジェクトの場所を知っているだけ 出力 Hello 55 参考文献 Python入門 http://www.pythonweb.jp/tutorial/
数値 #coding: UTF-8 print "1+2=",1+2#加算 print "1+3.0=", 1+3.0#加算 print "10/3=", 10/3#除算 print "10.0/3=" ,10.0/3#除算 print "17/5=" ,17/5#除算(型の範囲以下は切り捨て) print "-17/5=",-17/5 #除算(型の範囲以下は切り捨て) print "10.0//3="…
文字列関係 # coding: UTF-8 print "Hello, World!" print "2nd Hello","World" #これはテストです #複数行をそのまま出力 print """ <html> <head><title>This is Test </title</head> <body></body> </html> """ #文字列の結合 print "test"+"Test" #繰り返し print "-"*40 #文字列長取得 print len("nanmojiarud…
問題概要 文字列が与えられる。 異なる文字(a~z)のペアを文字列から排除していき、最後に、ただ一種類の文字のみ が２個以上、残るか判定せよ。 文字が残る場合、その文字(HappyLetter)を出力し、残らない場合は'.'(ピリオド)を出力せよ。 提出コード(C#) cl…
問題概要 複数の長さが異なる棒が与えられる。 一辺が一つの棒からなる正方形をいくつ作ることができるか出力せよ。 提出コード(C#) class ManySquares { public int howManySquares (int[] sticks) { Dictionary<string, int> dic = new Dictionary<string, int> (); int ans = 0; for</string,></string,>…
プライオリティキュー 以下の名前空間を定義 using System.Collections.Generic; 例 SortedSet<string> test = new SortedSet<string> (); test.Add ("b"); test.Add ("c"); test.Add ("a"); test.Add ("g"); Console.WriteLine ("Max = " + test.Max.ToString ()); Console.</string></string>…
スタック 以下の名前空間を定義 using System.Collections.Generic; 例 Stack<string> test = new Stack<string> (); test.Push("one"); test.Push("two"); Console.WriteLine(test.Pop()); Console.WriteLine(test.Pop()); 使えそうなメソッド ・Pop 先頭にあるオブジェクト</string></string>…
問題を読む為の英単語 単語 意味 frequently しばしば、頻繁に amount 総計 問題概要 入力：ドル、セント 出力：与えられるフォーマットで整形されたドル、セントの合計(string)フォーマット用件 １. 先頭に"$"をつけること 2. 下桁より3桁おきに","をつける…
問題概要 重さと価値がそれぞれWi,Viであるようなn種類の品物がある。 これらの品物から重さの総和がWを超えないように選んだときの、 価値の総和の最大を求めろ。 ただし、同じ種類の品物を使ってよい。i番目までの品物から重さの総和がj以下となるように選…
問題概要 ２つの文字列t, sが与えられる。 これら２つの共通部分文字列の長さの最大値を求めよ。 共通部分文字列とは、互いに共有する文字列であり、連続で一致している必要は無いが、 順序は等しくなければならない。 例示 s = "abcd" t = "becd"LCS = 3 (…
問題概要 フィボナッチ数列の総和を返す 解法 1.メモ化 /* メモfb[]はあらかじめ-1(メモ無し)で初期化する */ fib(int a){ /* メモ化チェック */ if(fb[a] != -1 ) return fb[a]; if( a == 0 ) ret = 0; else if( a == 1 ) ret = 1; else ret = fib(a-1) + f…
問題概要 重さwと価値vがついた品物がn個ある。 これらの品物から、重さの総和がWを超えないように選んだときの 価値の総和の最大値を求めなさい。 問題解法 1.全探索 再帰的に、品物をチェックし入れた場合、入れなかった場合とで探索を繰り返す。 重さの総…
問題概要 とても長い板からN個の板を切り出す。 切り出す板はL1,L2,...Lnであり、元の板の合計となっている。 板を切断する際に、その板の長さだけコストがかかる。 例えば２１の板を１３と８に分けた場合、コストは13+8である。 最小コストで板を切り出した…
サイコロの期待値 期待値 期待値は「確率で重み付けした値の和」。*1 例題*2 アリスがa面サイコロ、ボブがb面サイコロを持っている。 単純に出た目が多い方が勝ちというゲームを行う。 アリスが勝つことを知っているとき、アリスが出す出目の期待値を求めよ…
問題概要 入力：整数集合 出力：整数値 整数集合の冪集合を抽出し、その合計値を算出せよ。 ただし、冪集合は隣り合う値でのみ採用する。 {1, 2, 3} ▶︎{ 1 }, { 2 }, { 3 }, {1, 2}, {2, 3}, { 1, 2, 3} ▶︎1, 2 ,3, 3, 5, 6 ▶︎20 class SumOfPower { public …
演算 商を求める double d = (double)a / (double)b; 型を変換しないとint型として出力されてしまうことに注意する。 配列操作 初期値付き配列宣言 int[] score = new int[6]{0, 0, 0, 0, 0, 0}; 配列内をソート int[] array = new int[3]{3,1,2} Array.sort…
問題概要 入力：N文字の文字列S、長さ０の文字列T 以下の操作を行い、辞書順比較でできるだけ小さい文字列Tを作れ。 ・Sの先頭を１文字削除し、Tの末尾に追加 ・Sの末尾を１文字削除し、Tの末尾に追加 問題考察 貪欲法を使う。 先頭の文字が小さければ小さい…
問題を読む為の英単語 単語 意味 keycaps キー配置 decipher 解読する 問題概要 入力：タイプ文字列とキースイッチ キースイッチは{"A:B","C:D"}というような形式で与えられ、 例えば始めのキースイッチが押された場合、 タイプ文字列にAがあればBに、Bがあ…
