K問題:Black and White Boxes

1. 概要 これは Competitive Programming (その2) Advent Calendar 2016 - Adventar の22日目の記事です.今年のACM-ICPC 2016アジア地区つくば大会のK問題で組合せゲーム理論に関する問題が出題されました.この問題を通して組合せゲーム理論の紹介をしま…

Tournamentの最小道被覆問題 (Minimum Path Cover Problem)

情報工学工房の問題で面白かったのでまとめます. POJ : 1776 -- Task Sequences 問題(意訳) 単純有向グラフ G=(V, A) が与えられる.ただし,Gの任意の2頂点 に対して, または を満たす(どちらも満たさない場合はない). Gの最小道被覆 (Minimum Path Cover…

デュアルブートの不具合:Ubuntu16.04とWindows10

WindowsとUbuntuをデュアルブートで利用しているのですが,Ubuntuが立ち上がらなくなるという不具合があったので対処しました. 環境 PC:Panasonic Let's note CF-SX4 OS:Windows10,Ubuntu16.04 パーティション: ・/dev/sda1:Microsoft Windows回復環境…

ABC #042,ARC #058

ARC#058に参加しました. ABC#042はA問題からD問題,ARC#058はC問題からF問題です. AtCoder Beginner Contest 042 - AtCoder Beginner Contest 042 | AtCoder AtCoder Regular Contest 058 - AtCoder Regular Contest 058 | AtCoder 公式解説:http://arc05…

Ubuntu 16.04 LTS 64bit インストール後設定

システムの設定 [外付けキーボード(HHK)] 「システム設定」→「テキスト入力」→「日本語」を選択して「-」をクリック→「+」をクリックして「英語(US)」を追加→「次のソースへ切り替え:」と「前のソースへの切り替え:」を選択してDelete [句読点の変換] Da…

TCO 2016 Round 1A Div1

寝過ごして参加できなかったので復習しました. Editorial:http://apps.topcoder.com/wiki/display/tc/TCO2016+-+Round+1A agwさんのtogetter:TCO16 Algorithm R1A - Togetterまとめ [Easy 250: EllysTimeMachine ] 問題 アナログ時計の現在の時刻が"HH:MM…

TopCoder Arenaで「セキュリティ設定によってブロックされたアプリケーション」の解決方法

UbuntuでTopCoderのArenaを実行させようとしたらできなかったので解決方法を載せときます. 実行環境 OS: Ubuntu 14.04.4 LTS Java: 9-ea Arenaの実行方法 $ javaws ContestAppletProd.jnlp エラー内容 実行すると次のように「セキュリティ設定によってブロ…

Dinkelbach algorithm

D: 食塩水 - AtCoder Beginner Contest 034 | AtCoderのD問題「食塩水」で分数計画問題(分数計画問題 - ORWiki)が出ました.分数計画問題のアルゴリズムについては次のブログに詳しく載っています. Dinkelbach algorithm - 週刊 spaghetti_source - TopCo…

TopCoder Arenaでの文字化け対処法

長年悩まされたArenaでの日本語の文字化けを直す方法が分かったので書きます. 問題点 TopCoderのArenaを次のコマンドを実行して立ち上げていました. $ javaws ContestAppletProd.jnlp このとき,「Chat Arena」で日本語表示・入力をしようとすると次のよう…

POJ 1087

情報工学工房で「1087 -- A Plug for UNIX」という問題を解いたのですが,他の人の解法を聞いてなるほどと思ったので記事を書きます.問題文は長いです.私の解法は最大流問題に帰着する方法です.なるほどと思った解法は二部グラフの最大マッチング問題に帰…

双方向ダイクストラ

・(追記)2015年11月3日:Mi_Sawaさんとtmaeharaさんのソースコードへのリンクとtmaeharaさんのプログラムとの比較 [概要] 双方向ダイクストラを初めて実装したので備忘録としてまとめておきます. 時間がないのでざっくりとしか書いてません. 双方向ダイ…

SRM 671 Div2 (練習)

[結果] SRM 671 Div2: xo- 練習で解きました.easyが落ちて笑えない. [Easy 250: BearPaints ] 問題 H行W列の格子上で面積がM以下で最大の矩形の面積を求めよ. 方針 矩形の縦または横の長さを固定すると,面積を最大にする片方の長さは簡単に求まります.…

SRM 671 Div1

結果 --- 1317 -> 1292 今回も1問も解けなかった. [Easy 300: BearCries ] 問題 ';'と'_'からなる長さNの文字列messageが与えられる. messageにはいくつかの悲しいを表す顔文字が含まれる. 悲しい顔文字は';'が両端に1文字づつあり,その間に1文字以上の…

CODE FESTIVAL 2015 予選A

結果は3完の447位でした(もうダメすぎる). 問題文は日本語なので省略します. Welcome to CODE FESTIVAL 2015 予選A - CODE FESTIVAL 2015 予選A | AtCoder [A: CODE FESTIVAL 2015 ] 方針 与えられた文字列の末尾には必ず"2014"という文字列があるので最…

SRM668 Div1

結果 oxx 1285 -> 1366Arenaの問題文が改行されずに表示されるというのが直らなくてツライです. easyは良く分からずに通ったので反省です.medは間違った方針を立ていて解けませんでした.hardは見ていません. medは他の人のを見て復習をしたのですが何故…

Marathon Match 87 "PopulationMapping"

2013年6月5日に初めてMarathonに参加して以来の2回目のMarathonです. 前回は,何をして良いのか分からずにただランダムに出力するということをしていました.今回は適当にしなかったので備忘録として書きます. (まだ,結果が出てないので復習等は書いてい…

SRM 565 Div2 (練習)

結果 oox (練習) Editorial: http://apps.topcoder.com/wiki/display/tc/SRM+565Hard問題で解いている途中で問題の解釈を変えていき(簡単な方へ)何故解けないんだという未知との遭遇に出くわしたので反省.HardはEditorialを見ました. [Easy: ValueHist…

SRM 650 Div2

結果 oox 1088 -> 1081Easyの計算量の見積もりを間違って全探索でいけないと思っておかしなことをしてしまった.久しぶりにEasyとMedでハマってしまった. [Easy: TaroJiroDividing ] 問題 dividing gameをプレイする.dividing gameとは与えられた正の数Xを…

TCO2015 Round2A Div1 Med FoxMeeting

本番で解けなかったので復習をしました. 問題文を誤読してました(the total total distance ?). まったく分からなかったのでsemiexpさんのソースコードを参考にしました. (これを本番で通せる人々は凄いな) [Med: FoxMeeting ] 問題 頂点数nの辺重み…

TCO2015 Round2A Div1 Easy ModModMod

結果 xxx 1286 -> 1275解けなかったです(unratedと言ったので喜んでいたのですがratedだったみたい). おおまかな方針は良かったのですが実装まで落とせませんでした. writerのソースコードを参考に復習をしました(writerのソースコードとまったく同じに…

CodeIQ: バイナリ・カウント

CodeIQに公開された川添さんの問題「バイナリ・カウント」を解きました. 挑戦者求む!数学の問題をプログラミングで解こう!二進数の1の個数を数えて下さい。 by @riverplus Kawazoe│CodeIQ 問題 10進数表記の整数nが与えられる.次で定義する を求めよ. …

木の上での最大重み独立集合問題

入力グラフを木に制限したときの最大重み独立集合問題を解きます. 最大重み独立集合問題はNP困難ですが木に制限すると多項式時間で解けます.参考元はアルゴリズムデザインのpp.511-513です.アルゴリズムデザイン作者: Jon Kleinberg,Eva Tardos,浅野孝夫,…

いんでぃーどなう(オープンコンテントA) D: Longest Path

Welcome to Indeedなう(オープンコンテスト) - Indeedなう(オープンコンテスト) | AtCoder のD問題です.方針の参考は, Indeednow finala 子から異なる2つを選ぶ感じの木DPを解くアレ - よすぽの日記 です.しかし,読んでも分からなかったのでgasinさ…

SRM 646 Div2 (練習)

結果 oox (練習) Editorial http://apps.topcoder.com/wiki/display/tc/SRM+646kmjpさんの解法(TopCoder SRM 646 Div2 Hard TheFootballDivTwo - kmjp's blog)を参考にしました.場合分けがすごい苦手だということが分かりました. [Easy: TheConsecutiv…

SRM自分の解法まとめ

ブログにまとめたSRM(Div2)解法へのリンク (参加したSRMのまとめはしっかり,復習はさっぱり書くつもり) SRM 647 Div2 - tatanaideyo's blog SRM 646 Div2 (練習) - tatanaideyo's blog SRM 643 Div2 - tatanaideyo's blog SRM 642 Div2 - tatanaideyo…

Facebook Hacker Cup 2015 Round1 40:Corporate Gifting

嘘解法で解いたらMLEして答えを提出できなかったので対策方法を書きます.公式の解法は Hacker Cup 2015 Round 1 Solutions に書いてあります. ここでは,嘘解法の説明とスタック領域の拡張方法について説明します. 計算環境は次の通りです. OS: Ubuntu 1…

SRM 647 Div2

結果 oox 1075 -> 1088大まかな方針が立ってから詳細を詰めるのが遅すぎる.バッファオーバーフロー恐い. 今回のmedがeasyよりも明らかだったので,見落としがあるのかコーナーケースが恐いのかで確かめるのに時間がかかった. [Easy: PeacefulLine ] 問題 …

Facebook Hacker Cup2015 Round1 25:Autocomplete

Facebook Hacker Cup2015 Round1に参加しました. 結果は10,25,25の60点ということでRound2には進出できませんでした orz公式の想定解法は Hacker Cup 2015 Round 1 Solutions に書いています.25:Autocompleteの想定解法はTrie木のようです. 他の方針で解…

SRM 637 Div2 ConnectingGameDiv2 (復習)

練習で解きました. http://apps.topcoder.com/wiki/display/tc/SRM+637点連結度を用いて解きましたが,Editorialでは最小カットについて一言でしか述べていなかったので備忘録として残しておきます. [Hard: ConnectingGameDiv2 ] 解法 次の3x3グリッドの具…

2015年の目標

2014年を振り返りながら来年の目標について考えてみます.今年の反省は色々手を出して全体的に中途半端になったことです. 能力が高くないので来年は反省してやるべきことを絞りたいと思います. 研究 SRMとオンサイトのある競技プログラミングコンテスト 研…

SRM 643 Div2

結果 oxx 1080 -> 1075今年最後のSRMはツライ結果だった. 来年も色を上げれるように頑張りたい. [Easy: TheKingsArmyDiv2 ] 解法 Happyなソルジャーの数が0なら隣り合う2人のソルジャーをHappyにする必要がある. Happyなソルジャーの隣り合う組が1つでも…

桁DP Typical DP Contest E 数

桁DPがいまいち理解出来ていないので考えました. 問題はE: 数 - Typical DP Contest | AtCoderです.次のページの解法を参考にしています. Typical DP Contest E 数 - simezi_tanの日記桁DPとは与えられた数字の桁に関するDP(動的計画法)です. 用語解説…

SRM 642 Div2

結果 oox 1037 -> 1080「値が大きいと二分探索」を100回唱えたい. 毎回,二分探索という解法を疑うのを忘れてしまうので反省. [Easy: ForgetfulAddition ] 問題 数字からなる文字列sが与えられる. sの任意の分割に対して, sの前半部分の数字 + sの後半部…

C++入力の速度測定

double型でも調べてみました 動機 Welcome To PKU JudgeOnline で想定解法が の問題(3873 -- Trick or Treat)をC++で解いた時に、標準入力に cin を使ってTLE(Time Limit Exceeded) となりました. この時の対策として scanf を使うか、 [cin 高速化] cin.…

SRM 636 Div2 Hard ChocolateDivid

SRM 636 Div2 Hard ChocolateDivid を本番で通せなかったので復習. 問題 長方形の格子状のチョコレートが与えられる. それぞれのマスには0から9の数値が割り当てられる. このチョコレートを水平に3カット,垂直に3カットして16個の領域に分割する. それ…

SRM 613 Div2

反省点 250と500を通して559.35pt (61 place). Rating 731 -> 870. 1000の解法を考える時間が短かったので,焦って無意味なことをしてしまった. [250 TaroString] 通した.なんか考え方が汚すぎる. (問題文) 大文字のアルファベットからなる文字列Sが与…

ICPC (チームメンバー募集中)

ICPCとはACM国際大学対抗プログラミングコンテストのことです. ACM国際大学対抗プログラミングコンテスト - Wikipedia 入学シーズンが近いというこでICPCを知ってもらうために書きました(裏のテーマとしてはチームメンバーの募集).内容は入門ということ…

SRM 611 Div2

反省点 Rating 699 -> 731 250の問題文を理解するのに時間がかかった. [250 InterestingNumber] 通った.問題文を理解するのと実装に手間取った. (問題文) それぞれの文字が'0'-'9'である文字列xが与えられる. 各文字の出現回数が0回または2回であり, か…

Emacsの設定ファイル

間違って消してしまうことが多々あるのでメモ. .emacs.d/init.el に次のファイルを記述."C-\"で日本語変換(mozc)をする. "C-\"を入力するとtoggle-input-method関数が実行されて,変数default-input-methodが指すinput methodをトグル切り替えをする. …

SRM608 Div2 (復習)

参加出来なかったので復習. 反省点 説明が上手くできない. 問題文の理解に時間がかかる・(向いていないかも・・・) [250 OneDimensionalRobotEasy] 通した. (問題文) 1次元の数直線上で[-A, B]の範囲をロボットが動く.初期位置は原点0. コマンドが文…

SRM609 Div2

Rating 778 -> 699 反省点 なんとなくで解いてはダメ なんとなくでチャレンジしてはダメ [250 MagicalStringDiv2] 通した. (問題文) 文字'>'と' Sを「magical strings」にするには最小で何文字変更しなければいけないか. 「magical strings」とは,ある整…

SRM605 DIV2

Rating 829 -> 777. 反省点 Arenaは開始5分前ぐらいに開くとサーバーに繋がらないので,前もって繋ぐ. 先入観をなくす. [250 AlienAndPassword] 通した. (問題) 文字列Sが与えられる.1文字を消去したときにできる, 異なる文字列の数を求める. (方…