配列要素の回転

配列要素の回転 目的 配列の要素を循環させながらシフトさせたい。 例) a[10] = {0,1,2,3,4,5,6,7,8,9} 4だけシフト ▶︎{4,5,6,7,8,9,0,1,2,3} 解法 a : 配列の先頭から、シフト数分の要素の集合 b : a集合以外の要素の集合 とする。 例)arr[10] 4シフト a :…

CEDEC AI CHALLENGE 2014 まとめ(Part4 結果)

結果 予選2位で終わりでした。 得点がマイナス方向にいかなかったのはよかった。たまたまです。 戦略 多くの選手がモンテカルロによる方法を選択していることに驚いた。 全パターンを探索し、期待値が高い割当を行うという方法がセオリーかと思っていた。 …

CEDEC AI CHALLENGE 2014 まとめ(Part3 提出コード)

提出コード 環境 実装はC#で行った。 (とくに理由は無く、topcoderで最近お世話になっている為) 言い訳 予選コード、決勝コードともに1日で仕上げたため、 ほとんど直値でコメント無しという状態。 なのですぐ見て分かるように(自分が)以下に簡単な流れを示…

CEDEC AI CHALLENGE 2014 まとめ(Part2 戦略)

戦略 大まかな戦略 ・公開されている情報から相手の動きを予測する(期待値計算に使用)。 ・対戦サーバーに公開される対戦ログを参考にする。 ・熱狂度の配分により、目標値を設定する。 ・乱択アルゴリズム(モンテカルロ)に頼る。 ただし、予測や配分などに…

CEDEC AI CHALLENGE 2014 まとめ(Part1 ルール)

ルール概要 恋愛シミュレーションゲームのAI をつくる。 最も女の子に好かれるAIを作ることを目的とする。 ルール詳細 プレイヤーは4人、対象の女の子は8人。 プレイヤーはターン中にデートをすることにより女の子の"好感度"を上げていく。 ターン 1ゲー…

SRM629_DIV2_550

問題概要 アリスはクラスメート全員の為にアメを作る。 各クラスメートは飴を入れてもらう容器を提供し、 また各々は容器に入れてもらいたい重量を提示する。 アリスは一定の密度でアメを入れなければならない為、 各クラスメートの要望を聞き入れることがで…

SRM629_DIV2_250

SRM629 DIV2 250 問題概要 大きな穴がある(holeH×holeW)。 この穴を塞ぐための板がある(boardH×boardW)。 穴を板で塞ぐことができるか回答せよ。 塞ぐことができる場合は1を、できない場合は-1を返すこと。 ただし、穴と板の辺は平行でなければならない。 注…

Python練習(マージソート)

Pythonでマージソート マージソートは配列を二つに分け、各々でソートし、最後にマージしてソートする。 2つに分けた後のソートも同様な処理を再帰させて行うことができる。(分割統治法) マージソートは同じ値が存在した場合、配列の添字の順を維持すること…

はじめてのPython(9)

関数 #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練習(挿入ソート)

Pythonで挿入ソート 挿入ソートとは、ソート済みの要素に、順に要素を適切な位置へ挿入することで、 すべての要素をソートさせる考え方。計算量はO(N^2)。 ただし、バブルソートより高速であることが多い(値の入れ替え処理が少なく済むため) コード(Python) …

Python練習(選択ソート)

Python練習で選択ソート 選択ソートは要素の中で一番小さい値を探し出し、要素の先頭と入れ替える。 以後、決定した要素を除外し、繰り返す。 計算量はO(N^2)である。 コード(Python) #coding: UTF-8 #選択ソート x = [4,50,3,10,88,39,2,15] for i in range…

Python練習(バブルソート)

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 …

はじめてのPython(8)

繰り返し #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 "…

はじめてのPython(7)

辞書型 #coding: UTF-8 #ディクショナリー dict = {"one":1, "two":2} #{キー1:値1, ....} #キーに指定できるのは変更できないオブジェクトのみ #数値、オブジェクト、タプル #キーを指定して値を取得 value = dict["one"] print value #値の更新 dict = {"y…

はじめてのPython(6)

タプル #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 #…

はじめてのPython(5)

リストの使い方 #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[…

はじめてのPython(4)

条件分岐 #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…

はじめてのPython(3)

変数について #coding: UTF-8 msg = "Hello" print msg sum = 10 + 45 print sum #変数はオブジェクトの場所を知っているだけ 出力 Hello 55 参考文献 Python入門 http://www.pythonweb.jp/tutorial/

はじめてのPython(2)

数値 #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="…

はじめてのPython(1)

文字列関係 # 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…

Match627_DIV2_500

問題概要 文字列が与えられる。 異なる文字(a~z)のペアを文字列から排除していき、最後に、ただ一種類の文字のみ が2個以上、残るか判定せよ。 文字が残る場合、その文字(HappyLetter)を出力し、残らない場合は'.'(ピリオド)を出力せよ。 提出コード(C#) cl…

Match627 DIV2 250

問題概要 複数の長さが異なる棒が与えられる。 一辺が一つの棒からなる正方形をいくつ作ることができるか出力せよ。 提出コード(C#) class ManySquares { public int howManySquares (int[] sticks) { Dictionary<string, int> dic = new Dictionary<string, int> (); int ans = 0; for</string,></string,>…

C# よく使いそうなコード3

C#

プライオリティキュー 以下の名前空間を定義 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>…

C# よく使いそうなコード2

C#

スタック 以下の名前空間を定義 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>…

SRM 149 DIV2 250

問題を読む為の英単語 単語 意味 frequently しばしば、頻繁に amount 総計 問題概要 入力:ドル、セント 出力:与えられるフォーマットで整形されたドル、セントの合計(string)フォーマット用件 1. 先頭に"$"をつけること 2. 下桁より3桁おきに","をつける…

動的計画法part4(個数制限なしナップサック問題)

問題概要 重さと価値がそれぞれWi,Viであるようなn種類の品物がある。 これらの品物から重さの総和がWを超えないように選んだときの、 価値の総和の最大を求めろ。 ただし、同じ種類の品物を使ってよい。i番目までの品物から重さの総和がj以下となるように選…

動的計画法part3(最長共通部分列問題)

問題概要 2つの文字列t, sが与えられる。 これら2つの共通部分文字列の長さの最大値を求めよ。 共通部分文字列とは、互いに共有する文字列であり、連続で一致している必要は無いが、 順序は等しくなければならない。 例示 s = "abcd" t = "becd"LCS = 3 (…

動的計画法part2(フィボナッチ数列)

問題概要 フィボナッチ数列の総和を返す 解法 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…

動的計画法part1(ナップザック問題)

問題概要 重さwと価値vがついた品物がn個ある。 これらの品物から、重さの総和がWを超えないように選んだときの 価値の総和の最大値を求めなさい。 問題解法 1.全探索 再帰的に、品物をチェックし入れた場合、入れなかった場合とで探索を繰り返す。 重さの総…

FenceRepair

問題概要 とても長い板からN個の板を切り出す。 切り出す板はL1,L2,...Lnであり、元の板の合計となっている。 板を切断する際に、その板の長さだけコストがかかる。 例えば21の板を13と8に分けた場合、コストは13+8である。 最小コストで板を切り出した…

Match626 DIV2 500

サイコロの期待値 期待値 期待値は「確率で重み付けした値の和」。*1 例題*2 アリスがa面サイコロ、ボブがb面サイコロを持っている。 単純に出た目が多い方が勝ちというゲームを行う。 アリスが勝つことを知っているとき、アリスが出す出目の期待値を求めよ…

Match626_DIV2_250

問題概要 入力:整数集合 出力:整数値 整数集合の冪集合を抽出し、その合計値を算出せよ。 ただし、冪集合は隣り合う値でのみ採用する。 {1, 2, 3} ▶︎{ 1 }, { 2 }, { 3 }, {1, 2}, {2, 3}, { 1, 2, 3} ▶︎1, 2 ,3, 3, 5, 6 ▶︎20 class SumOfPower { public …

よく使いそうなコードまとめ(C#)

C#

演算 商を求める 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、長さ0の文字列T 以下の操作を行い、辞書順比較でできるだけ小さい文字列Tを作れ。 ・Sの先頭を1文字削除し、Tの末尾に追加 ・Sの末尾を1文字削除し、Tの末尾に追加 問題考察 貪欲法を使う。 先頭の文字が小さければ小さい…

SRM148 DIV2 600

問題を読む為の英単語 単語 意味 keycaps キー配置 decipher 解読する 問題概要 入力:タイプ文字列とキースイッチ キースイッチは{"A:B","C:D"}というような形式で与えられ、 例えば始めのキースイッチが押された場合、 タイプ文字列にAがあればBに、Bがあ…

SRM 148 DIV2 250

問題を読むための英単語 単語 意味 evenly 平に,平等に 問題概要 入力:数値 出力:個数入力される数値に含まれる数字の中で、入力される数値自身を割ったとき、 あまりが0になる個数を出力せよ。 ただし、同じ数値は出現する回数分可算し、また0では割っ…

三角形作れるか問題

問題概要 入力として与えられる辺の候補より、周長が最も長い三角形を作れ 入力:辺の長さ 出力:周長 ただし、三角形を作ることができなければ0を出力せよ。 基礎知識 三角形が作れる条件は、 \[ 三角形で一番長い辺 方法 あらかじめ辺の配列を長い順にソ…

SRM 147 DIV2 600

問題を読む為の英単語 単語 意味 male 男 fimale 女 direction 方向 arrange 配列する 問題概要 入力:男の人の数、女の人の数、削除パターンK 出力:男女の並び順 男女の並び順を作る。男女の並びはサークルになっている。 開始位置(先頭)から始めて、K番目…

SRM 147 DIV2 250

問題を読むための英単語 単語 意味 Julius Caesar シーザー(ローマ将軍) cryptography 暗号法 further さらに遠くに、さらに進んで 問題概要 Input:暗号文、シフト数 Output:復号文文字をアルファベット順である文字数分だけシフトする暗号がある。 例えば'A…

SRM 146 DIV2 500

問題を読む為の英単語 単語 意味 rectangular 長方形の 問題概要 入力:width, height 出力:長方形の個数以下のような四角形が与えられる。 __ __ __ |__|__|__| |__|__|__| |__|__|__| (width:3 height:3)与えられた四角形に存在する長方形の数を出力せよ…

SRM 146 DIV2 250

問題を読む為の英単語 単語 意味 scoring 採点法 Yahtzee ヤッツィー(ダイスゲーム) upward 上へ向かう considered 熟考したうえで instance 実例 end up 最後には、終わる 問題概要 サイコロをふって出た目のポイントで最大のものを出力せよ。 入力:5つダ…

プログラマの数学

尊敬する結城先生の著書で覚えておきたいことをまとめる。 論理(AならばB) AならBは以下のように記述する。 \[ A \Rightarrow B \] 「AならばB」の定義は以下の通りである。 A B A▶︎B ture true ture ture false false false ture true false false true プ…

練習(SRMs 1 145 DIV 2 500)

SRMs 1 145 DIV2 500 強くなりたい 問題を読む為の英単語 単語 意味 workout (計算を)解く exercise 演習 routine ルーチン(決まりきった仕事) whole 全体の lasts 最後に残った 問題概要 コンピュータが処理を行うとき、現在の進行度をパーセンテージで表示…

練習(SRMs 1 145 DIV 2 200)

SRMs 1 145 DIV2 200 英語難しい。 問題を読む為の英単語 単語 意味 dithering ディザリング ※1 determine 決心する upper 高い方 surround 取り巻く 問題概要 入力:ディザリング文字列 : スクリーン 出力:ディザリング文字の数スクリーン内のディザリング…

練習(SRMs 1 144 DIV 2 200)

SRMs 1 144 DIV2 200 どうやらDIV2の方が簡単らしい。 問題を読む為の英単語 単語 意味 tend 傾向がある represent 代表する particular 特有の、個々の midnight 真夜中 formatted 書式化された 問題概要 現在0時である。 与えられる秒数から、現在からの…

(アルゴリズム)バックトラック

バックトラック法 全数探索の総当たりを大きく改善したアプローチ。 問題の制約が違反するとわかった時点で、探索をあきらめる。 そして最後の有力な部分解まで戻り再検討を行う。

練習(SRMs 1 144 DIV 1 550)

問題を読む為の英単語 単語 意味 gamblers ギャンブラー variety 多様な wide variety 種類が豊富 lottery 運、くじ represent 代表する inclusive すべてを含んだ appear 出現する indicate 指し示す restriction 制限 descending 降下的な order 順序 like…

CodeIQ(チケットゴブル問題)

[CodeIQ]チケットゴブル問題 問題概要 国名と旅行日程が与えられる。 一年間でより多くの国へ行ける旅行プランをたてよ。 入力:国名 旅行期間(例:1/1-1/5) 出力:国名(アルファベット順にソート) 解法 この問題はスケジューリング問題に帰着する。 スケジ…

TopCoder(Practice_144_DIV_1_300)

[TopCoder]練習(SRMs 1 144 DIV 1 300) 問題を読む為の英単語 単語 意味 following 次の say 示す encrypt 暗号化・符号化 adjacent 隣接した above 上の particular 詳細 opposite 反対の 問題概要 ・入力 0〜3までの数列 ・出力 入力のコードを複合化し…

計算理論の基礎(チューリング機械)part2

[計算理論]チューリン機械part2 停止問題 停止問題(halting problem)とは、チューリング機械の結果が「受理・拒否」か「ループ」を 判定できるかという問題。 一般的に「停止性をアルゴリズム的に決定する方法は存在しない」。 万能チューリング機械 万能チ…