読者です 読者をやめる 読者になる 読者になる

utsubo’s blog

競技プログラミングとか.

2016年振り返りと2017年目標

2017年に入りもう一月経ってしまった。 競技プログラミング レート変動 SRM 1165 -> 1373 CodeForces 1702 -> 1702(不参加) AtCoder ? -> 1574 topcoderでようやくDiv1に入れて嬉しい! 週に1問ぐらい解く習慣を付けていきたい。 英語 目標は達成できなかっ…

ACM-ICPC 2016 国内予選 D : ダルマ落とし

問題 配列の隣り合った2つ要素の差が1以下であれば,その2つ要素を消すことができる. この操作を繰り返す時,最適に消していくと,最大何個要素を消せるか.例:{1,3,2,1}が与えられたとき {1,3,2,1} -> {1,1} -> {} ⇐4個消せる {1,3,2,1} -> {1,3} ⇐先に右…

ICPC国内予選 参加記

ICPC国内予選に参加しました。 順位は、95位でした。今年はあんまり参加する気はなかったのですが、ICPCが近づくとやっぱり出たくなりました。 チームメンバー集めは、4月ぐらいから始めて、5月頃メンバーが決まって、それから週1ぐらいで過去問を解いて練習…

応用情報技術者試験 合格しました

合格しました 応用情報技術者試験についてはリンク参照. IPA 独立行政法人 情報処理推進機構:制度の概要:応用情報技術者試験 得点は,午前・午後共に8割程度で,割りと余裕がありました. 午前 自分は,情報系の学生であるものの,授業でやった基本的な部…

ビームサーチの練習用にパズドラAIを組んだ

大学の先輩がパズドラのコンボのAIの話をしていて,そういえば組んだことがないなぁと思い立ち. 目的 パズドラのパズルにおいて,コンボ数をできるだけ大きくするようなパズルのスライドのさせ方を出力する. 今回は,ダメージ等については考慮しません. …

グラフ理論系の好きな問題 5選

最近何もする気が起きないので,今までに見た数少ない問題の中で好きだった問題を紹介します(脚注にネタバレ). 1. TopCoder Single Round Match 642 Div.2 Hard Tall Shoes *1が好きなので好きです. https://community.topcoder.com/stat?c=problem_stat…

2016年の目標

競技プログラミング ・Topcoder/Codeforcesの問題を解く. ・Div1入り 英語 ・TOEIC 730点以上 ・単語帳やる その他 ・何か2つ作る課題を締切直前までやらずにいて痛い目を見たので,計画性を持って行動出来るようになりたい. 頑張る.

2015年振り返り

こんな目標を立てていたらしい. 2015年の目標 - utsubo’s diary 競技プログラミング レート等 SRM (903 -> 1165) Marathon Match (? -> 864) CodeForces (1440 -> 1702) CODE FESTIVAL (138位 -> 91位) CODE RUNNER (65位 -> 46位) 目標 SRM Div1 入り ✕(…

ACするとLEDがピカピカ

作ったもの AtCoderのコンテストでACするとLEDが点滅する奴を作ってみました.こんなの↓ACするとLEDが光る奴 pic.twitter.com/Yn7RKoFe0D— うつぼ (@utsubo_21) 2015, 12月 25 構成 Pythonで提出状況を取ってきてパース,正誤をシリアル通信でArduinoに送っ…

CODE RUNNER 予選B

予選B問題 問題はこんな感じでした. 魔法の力を、ためて戦え!「Charge And Hit」 「Charge And Hit」は3人1部屋でゲームを行います。ユーザーは入室/攻撃APIをリクエストするとシステムにより各部屋に割り振られます。部屋には10匹の敵が並んでいて、ユー…

IntelliJ IDEAからSceneBuilderが開かない(Mac)

少し困ったので調べると java - How to use the SceneBuilder with IntelliJ on Mac - Stack OverflowIntelliJ IDEAでパスを設定 Preference -> Language & Frameworks -> JavaFX -> /Application/SceneBuilder.appFinderから Applications -> SceneBuilder…

100問マラソン 5問目 SRM 667 Div2 Med: OrderOfOperationsDiv2

問題 http://community.topcoder.com/stat?c=problem_statement&pm=13988&rd=16547 解法 dpらしい.div2Medだし貪欲だろうと高をくくっていたら駄目でした. #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstring> using namespace std; int dp[1<<21]; class </cstring></algorithm></vector></string></iostream>…

100問マラソン 4問目 SRM 663 Div2 Hard: CheeseRolling

問題 http://community.topcoder.com/stat?c=problem_statement&pm=13919 優勝するトーナメントのパターン云々 解法 kmjpさんのを見させて頂きました. TopCoder SRM 663 Div2 Hard CheeseRolling - kmjp's blog #include <bits/stdc++.h> using namespace std; class Chees</bits/stdc++.h>…

100問マラソン 3問目 SRM 664 Div2 Hard: BearSortsDiv2

問題 配列に対しマージソートを適用する. しかし,そのマージソートは大小比較部分が間違いがあり,数字の大小関係なしに,確率で大小を判定する. seqという配列が入力として渡されるので,先のマージソートを適用した時,その配列が1,2,...,Nとなるような…

100問マラソン 2問目 SRM 665 Div2 Hard: LuckySum

問題 LuckyNumberは全桁4,7で構成された数字のことを言う.LuckySumとはLuckyNumber2つの和である. '?'または0-9で構成された文字列(note)が渡されるので,それに一致するような最小のLuckySumを求める. 制約 noteの文字数 解法 下の桁から埋めるように全…

100問マラソン 1問目 SRM 666 Div2 Hard: CollectingTokens

問題 木の頂点に得点が設定されており,木の上をL回移動できる時の最高得点を求める. 一度取った頂点の得点を,もう一度取ることはできない. 制約 頂点数 L 解法 解けなかったので,Editorialの解法で書いた. http://apps.topcoder.com/wiki/display/tc/S…

宝探しページを作った

宝探しページを作りました。 宝探し! ページのどこかに隠されている合言葉を探し出すというものです。CTFっぽいの。 (まだ、5つしか合言葉はないです。) ほとんどPHP+MySQLで、 ユーザー管理部分は↓が大変参考になりました。 ユーザー管理をするWebサービス…

ICPC国内予選 2015

参加まで サークルのような活動をしていたのでそこにいた先輩2人とチームを組んで、コーチ・監督は研究室の先輩と先生にそれぞれお願いしました。 週1で練習会を開き、本番まで時間があまりなかったので、過去問を2014年〜順々にやっていってました。 感想 …

Square Route

AOJ

問題 Square Route | Aizu Online Judge 感想 ACM/ICPC国内予選突破の手引き で幾何と分類されているけど、幾何ではない気がする。 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> P; bool solve(){ int n,m; cin >> n >> m; if(n == 0</int,int></bits/stdc++.h>…

Problem F Gather the Maps!

問題 Gather the Maps! | Aizu Online Judge 感想 誰が誰の地図を持っているかsetで持たせました。 とても遅いし、怪しいところあるけど通ればいいよね。 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> P; int main(void){ int n; whi</int,int></bits/stdc++.h>…

NetworkXでグラフを描いた(最短経路他)

研究室の方でNetworkXを教えて頂いたので、試しに色々弄ってみました。 最短経路(ダイクストラ)・経路復元と最長経路(トポロジカルソート+DP)で書いてます。 最短経路・経路復元 # -*- coding: utf-8 -*- # Verify(Time Limit Exceeded) # http://judge.u-ai…

Indeedなう(オープンコンテストB)A~E

A - Counting on a Triangle それぞれの段の重みの合計を計算しておく。OEISで検索すると、a(n) = n^2*(n+1)/2と出てきた。 A002411 - OEIS http://indeednow-finalb-open.contest.atcoder.jp/submissions/376663 int main(void) { int A,B; cin >> A >> B; …

SRM654 Div2 Med / OneEntrance

問題 http://community.topcoder.com/stat?c=problem_statement&pm=13698 真姫の新しい家に家具をN個設置したい。部屋の隣接関係と入り口の部屋の番号が与えられ、部屋の隣接関係は木構造をしている。N個の家具を順番に部屋に設置していくが、家具を設置した…

SRM654 Div2 Easy / SquareScoresDiv2

問題 http://community.topcoder.com/stat?c=problem_statement&pm=13700 ある文字列の部分文字列の中で同じ文字が連続しているものをカウントする。 解法 全探索 class SquareScoresDiv2 { public: int getscore(string s) { int ret = 0; for(int i=0;i

SRM654 Div2 Hard / SuccessiveSubtraction2

問題 http://community.topcoder.com/stat?c=problem_statement&pm=13699 配列aが与えられ、それはa[0]-a[1]-...-a[n]という式を表す。この式の中に括弧を2組まで入れた時式の結果の最大値答える。 解法 Editorial一部改変。 http://apps.topcoder.com/wiki/…

yukicoder No.60 魔法少女

問題 No.60 魔法少女 - yukicoder 感想 二次元imos法で各座標に加わるダメージを計算する。 いもす法 - いもす研 (imos laboratory) #include <bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 1e9; const int MOD = 1e9+7; int main(void) { i</bits/stdc++.h>…

AtCoder Beginner Contest #008 D- 金塊ゲーム

問題 D: 金塊ゲーム - AtCoder Beginner Contest #008 | AtCoder 感想 AtCoder Beginner Contest 008 解説 解説スライドを見ながら解きました。 #include <bits/stdc++.h> using namespace std; int w,h; vector<int> x,y; map<tuple<int,int,int,int>,int> memo; int dfs(int l,int r,int u,int d){ int</tuple<int,int,int,int></int></bits/stdc++.h>…

yukicoder No.164 ちっちゃくないよ!!

問題 No.164 ちっちゃくないよ!! - yukicoder 感想 それぞれ、(含まれている数字の最大値+1)進数で最小。 str.to_i(n)で文字列をn進数にできてruby凄い。 n = gets.to_i a = [] for i in 1..n a.push(gets.to_s) end t = 0 dic = {} for s in "0123456789A…

yukicoder No.163 cAPSlOCK

問題 文字列の小文字は大文字に大文字は小文字にする。 感想 それぞれのxor 32をとると大文字・小文字が反対になる。 #include <bits/stdc++.h> using namespace std; int main(void) { string s; cin >> s; for(int i=0;i</bits/stdc++.h>

yukicoder No.67 よくある棒を切る問題(1)

問題 http://yukicoder.me/problems/145 感想 長さを二分探索したけど、で回すと大きい数の時、無限ループしてしまいました。 なので適当に100回ぐらいで打ち切った。 #include <bits/stdc++.h> using namespace std; typedef pair<int,int> P; typedef pair<int,pair<int,int>> PP; typedef long long </int,pair<int,int></int,int></bits/stdc++.h>…

yukicoder No.27 板の準備

問題 http://yukicoder.me/problems/32 感想 制約が小さいので全探索できそう。 A,B,Cのそれぞれの長さ、それぞれの使う枚数について回して30^6ぐらいだけど実際はもう少し小さいから間に合った。 #include <bits/stdc++.h> using namespace std; typedef pair<int,int> P; typedef p</int,int></bits/stdc++.h>…

Codeforces #294(Div.2)

1575->1516(-59) レートは下がっちゃったけど人が多いのは楽しいですね。 A,B:手間取った。 C:よくわからないので二分探索しようとしたけど、二分探索が書けなくて焦った。 D:累積和してどうするんだろう・・・ E:読めてない 二分探索きっちり書くの難しい。…

春休みにしたいこと

Qt,Cocos2d-x,OpenGL UML 蟻本,TLE本 ゲーム制作

Rubyで形態素解析してマルコフ連鎖

はじめに 形態素解析とマルコフ連鎖で面白いことできそうと聞き、調べてみると既に色んな人がやっていました。 Rubyで何か書きたいと思っていたので、参考にしながら試してみました。 [参考リンク] マルコフ連鎖でTwitter BOTを作る - FLYING [プログラミン…

yukicoder No.135 とりあえず1次元の問題

問題 N個の1次元の座標が与えられ、その中から同じ座標ではない2点を選ぶ。 最小距離を求めよ。 感想 星1だし制約を確認せずに全探索で大丈夫では思ったらTLE。unique使ってみた! STLのvectorから同一要素を削除 - minus9d's diary #include <bits/stdc++.h> #define MOD 1</bits/stdc++.h>…

yukicoder No.118 門松列(2)

問題 N本の竹がありそれぞれの高さはAiで与えられる。 門松列とは、選んだ「3つの竹の長さの降順で2番目が、左または右側になっているもの」、「3つの長さはすべて異なる」という条件も満たすものである。 門松列になるような竹の選び方の数を求めよ。 (竹…

yukicoder No.102 トランプを奪え

問題 2人でゲームをする。まず、一組トランプの中から何枚かをマークごとに分けて重ね山札にして置く。 2人交互に以下の操作を繰り返す。 ・4つ(♡♧♤♢)の山札から1つの山札を選びそこから1〜3枚カード引き手札に加える。 ・カード引いた時、そのマークの山札…

2015年の目標

競技プログラミング ・TopCoder SRM Div1入り・オンサイトのコンテストに1つ以上出る・蟻本を最後まで読む・CodeForcesに出る 英語 ・洋書読む ・洋楽聞く その他 ・何かしらで自分が満足できるぐらいのものを2つ以上作る ・ラブライブの声優に1人以上会う …

yukicoder No.23 技の選択

問題 体力Hの敵を必ず当たる通常攻撃と2/3の確率で当たる必殺技で倒したい。攻撃力は、通常攻撃はA、必殺技はDであたえられる。敵を倒すまでにかかる攻撃回数の期待値を求めよ。 感想 有効な手が出るまでの回数の期待値は、その有効な手が出る確率の逆数って…

2014年振り返り

競技プログラミング ・Code Formula(63位) ・CODE FESTIVAL(138位) ・CODE RUNNER(65位) 規模が大きかったおかげでオンサイトのコンテストに3つ出れた。結果は実力通りぐらい。競プロerの方々と知りあえてとても楽しいし、やる気が出た。来年も大規模のコン…

MySQLでENUM型が通らなかった話

dotinstallのMySQLをやっていてしょーもないところで躓いた。 MySQL入門 (全19回) - プログラミングならドットインストール レコードの挿入時にENUM型の部分でエラーが出ました。 ERROR 1064(42000): You have an error in your SQL syntax; check the manua…

SRM642 Div2

Easy(250) 数字をある桁で2分割した和の最小値を求める。 stoi書く必要なかったっぽい。 Middle(500) N個ライトとスイッチがあり、i番目のスイッチは、iの倍数の番号のライトに対応している。全てのライトをOFFにする最低何回スイッチを押さないといけないか…

ブログ新調

あんまり日にちを開けずに書いていきたい!