utsubo’s blog

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

最大フロー問題(循環フロー問題)の双対をとる

はじめに 近似アルゴリズム(V.V.ヴァジラーニ)の12章に最大フロー問題とその双対問題が載っているのだが、どのように変形したらその双対問題の式が得られるのか結構悩んだ。 そこで、未来の自分のために最大フロー問題から双対問題を導出する過程をまとめて…

「Linuxのしくみ」を読んで

はじめに gihyo.jp を読みました。 感想 低レイヤ寄りのことを知りたかったので読み始めました。 基本的な用語でも分かってないことがあったので為になりました。 この仕組みで複雑なアプリケーションが動いてるの凄すぎて気持ち悪い。7章ぐらいから飽きてき…

2017年振り返りと2018年の目標

はじめに 最近,何も書いていないなと思ったらもう年末だったので,振り返りでもしようと思います. 2017年の目標と達成度 年始にふんわり立てていた目標と達成度. 競プロ:週に1問 → 問題を解くどころかコンテストにもほぼ出ていない. 英語:TOEIC730点 →…

Q-Learningで迷路を解く

はじめに 強くなるロボティック・ゲームプレイヤーの作り方 プレミアムブックス版 ~実践で学ぶ強化学習~↑これを読みながら強化学習の基礎と雰囲気を学んでいるのですが, 読んでるだけで飽きてきたので,実際に実装してみました. chainerRLとか使えば簡単に…

IPアドレスを自動でGoogleスプレッドシートに書き込む(Windows10)

背景 学内や社内等のPCに接続したい時,IPアドレスが分からず困ることがしばしばあったので,*1 自動でIPアドレスがGoogleスプレッドシートに書き込まれるようにしました. 構成 Windows 10 → Google Apps Script → Googleスプレッドシート Google Apps Scri…

ICPC国内予選 2017 G 迷宮を一周

問題 迷路がN*Mのグリッドで与えられる.('.'が通路,'#'は通行不可) グリッド上の(0,0)地点をスタートとする. スタート以外の3隅の宝物を回収してスタート地点に戻ってきたい. しかし,一度通った通路は通れないとする. https://storage.googleapis.co…

ICPC国内予選参加記 2017

参加まで 忙しいし出なくて良いかーと思っていたのですが*1,先輩の後押しで参加することに. 今年で3回目の参加だったので,登録まではバタバタせずにすみました.(監督・コーチありがとうございました!)メンバーは去年と同じ同期のメンバーが1人と研究…

モナコインのマイニングソフトをDockerで動かす

モナコイン モナコインは,ブロックチェーン利用した仮想通貨で,同種で有名なものにはビットコインがあります. 詳しい説明は省きます. https://monacoin.org/ja/ 概要 単独で採掘するほどのリソースがないので,皆で掘って報酬を分割するマイニングプール…

Yandex Algorithm 2017 Marathon 感想

Yandex Algorithm 2017 Marathonの反省です. Marathon Roundは2017/5/6, 6:00~2017/5/8, 6:00の2日間で行われました. https://contest.yandex.com/algorithm2017/contest/4524/problems/ 問題 N×Mのグリッド上に生命の泉と魔法の泉がK個ある. このグリッ…

kaggleのDigit Recognizerへ初提出(Chainer)

はじめに kaggle -Digit Recognizer Digit Recognizer | Kaggle kaggle初提出までしたことをとりあえずまとめます. 初提出まで まずは軽くお勉強 ニューラルネットワークと深層学習 http://nnadl-ja.github.io/nnadl_site_ja/index.html さすがに何もわかっ…

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国内予選 参加記 2016

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>…