g++ の最適化オプションで "-O2" と "-O3" のどちらが良いのか分からなかったので調べました．結局，確信を持つことは出来ませんでしたが "-O2" をデフォルトで使用して，高速化をしたいときに両方を試すことにします．環境 OS : Ubuntu 16.04.4 LTS (Xenial…

AtCoder Beginner Contest 075 - AtCoder のD問題を解きました．平面上にn個の点と自然数kが与えられたときに，ある決められた幾何形状でk個以上の点を含むものの中で面積最小のものを見つける問題は k-enclosing problem と呼ばれています．一般に，幾何形…

OSでUbuntu16.04を使用しているパソコンをアクセスポイントとして使用する方法を紹介します．Ubuntu16.04から設定が簡単になっています． 用途 無線LAN内蔵でLANポートがあるノートPCをアクセスポイントとして利用できます． ホテルや家などで有線LANをノー…

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

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

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

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…

apt-get ではなく apt を使用 (2018年4月19日) システムの設定 [ 日本語入力 ] インストール後に一度，Mozcの入力モードを変更する必要がある 右上の「en」をクリックして「日本語(Mozc)」を選択 → 「入力モード」で「ひらがな」を選択 入力ソースの切り替え…

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ブログにまとめた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…

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

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