utsubo’s blog

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

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

最近何もする気が起きないので,今までに見た数少ない問題の中で好きだった問題を紹介します(脚注にネタバレ).

1. TopCoder Single Round Match 642 Div.2 Hard Tall Shoes

*1が好きなので好きです.
https://community.topcoder.com/stat?c=problem_statement&pm=13523
TopCoder SRM 642 Div2 Hard TallShoes - kmjp's blog

2. Indeedなう A日程 D: Longest Path

全然わからなかったけど,解説を読んで実装するのが楽しかった.
D: Longest Path - Indeedなう(オープンコンテスト) | AtCoder
Indeedなう A日程 解説

4. CODE FESTIVAL 2015 決勝 I: 風船ツリー

これも実装が楽しい問題でした.
I: 風船ツリー - CODE FESTIVAL 2015 決勝(オープンコンテスト) | AtCoder
CODE FESTIVAL 2015 解説 - SSSSLIDE

まとめ

グラフ理論系の問題は実装が楽しいものが多くて好きです.
なんか最近の問題が多くて申し訳ない感じになりました.
手を付けてない組み合わせ系の問題に取り組みたい.






以下,問題の解法ネタバレ.

*1:二分探索

*2:最短経路問題

*3:フロー

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 入り ✕(まだだめそう)
  • オンサイト ◯(CodeFes出れて良かった)
  • 蟻本読了 ✕(目標自体を忘れてた)
  • CF出る △(5回しか出てない)

若干成長できたのかなぁ.正直,誤差の範囲だと思ってます.
達成率は40%ぐらい.

英語

目標

  • 洋書読む ✕(目標自体を忘れてた)
  • 洋楽聞く △(聞き流しは多少)

洋楽は前よりかは聞いたから,達成率は20%ぐらい.

その他

目標

  • 何かしらで2つ以上作る ◯(まだまだな部分もあるけど)
  • ラブライブの声優に1人以上会う ✕(こんなのも立てていた)
  • 大学の特待生制度で15万貰う △(だめです)

まずまず.

雑記
  • 某社ツアーが最高でした.ほんと感謝.
  • そろそろ分野絞ってやらないといけないと強く感じます.
  • 各方面に迷惑をかけまくった一年だった.

今年も大変お世話になりました.2016年目標に続きます.

ACするとLEDがピカピカ

作ったもの

AtCoderのコンテストでACするとLEDが点滅する奴を作ってみました.こんなの↓

構成

Pythonで提出状況を取ってきてパース,正誤をシリアル通信でArduinoに送っています.
ArduinoではACであれば点滅,それ以外であったら点灯するようにしました.(他の色があれば,色を状態によって変えたかったのですが,手持ちになかったので...)
f:id:utsubo_21:20151225223411p:plain

pythonはシリアル通信にpyserialとhtmlパーサーにbeautifulsoupを使用.
beautifulsoupがよく分かってないので適当.
procon_led.py · GitHub

Arduinoは基本的なコマンドのみ.
serial_test · GitHub

まとめ

PythonArduino便利!

CODE RUNNER 予選B

予選B問題

問題はこんな感じでした.

魔法の力を、ためて戦え!「Charge And Hit」
「Charge And Hit」は3人1部屋でゲームを行います。ユーザーは入室/攻撃APIをリクエストするとシステムにより各部屋に割り振られます。部屋には10匹の敵が並んでいて、ユーザーは任意のタイミングで一番前の敵を魔法で攻撃します。攻撃によって敵に与えるダメージは「魔法をためた時間」に応じて高くなります。ただし敵の体力を超えるダメージは切り捨てられて体力と等しい値になります。部屋内で与えたダメージの合計値が大きい順に室内順位がつけられ、その室内順位に応じてスコアを得ます。ユーザーは他のユーザーより多くのダメージを与えて、スコアを多く得ることを目指します。

序盤

最初はとりあえず,3秒に1回殴るプログラムを書いて動かしながら方針を考えてました.これだけでも,最序盤は2位ぐらいまでいっててビビる.

メンテナンス前(開始1時間ぐらいでメンテナンスがあった)

Info APIからjsonを貰ってくるのに悪戦苦闘してたら時間が結構経ってしまった.
敵を倒せるなら殴るに変えてたら,一気に50位ぐらいまで落ちた.HPが高い敵を狙う人のカモになっていると気づく.

メンテナンス後

以下が最終的な方針.

1. 残りの敵の中でHPが上位30%の敵をリストに入れる
2. リスト内の敵が全て倒されていたら,上と同様にリストを更新

リスト内の敵が目の前に来た時
3.1. パワーがHPの7割を超えていたら殴る.
3.2. friendsの最大パワーが敵のHPの7割を超えていて,自分のパワーが3e7より大きければ殴る.
1~3をInfoを0.2秒ごとに貰ってきて繰返していた.

書いたコード: qb2015.py · GitHub

結果

10位 (∩´∀`)∩ワーイ
Ranking: http://graph.coderunner.jp/max.html

初めて良い感じの順位を取れてめっちゃ嬉しい.
本戦もこの調子でいけると良いんだけどなぁ...

反省

1位の方が言っていた「必ずルーム1位なら倒す」を思い付いていれば,もう少し伸びそうだった.
「後ろに並んでるHPが高い敵を狙って目の前の敵を誰も殴らない現象」が頻発する前に上位に抜け出せたのが大きかった.

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

少し困ったので調べると
java - How to use the SceneBuilder with IntelliJ on Mac - Stack Overflow

IntelliJ IDEAでパスを設定
Preference -> Language & Frameworks -> JavaFX -> /Application/SceneBuilder.app

Finderから
Applications -> SceneBuilderを右クリック -> パッケージの内容を表示 --> Contents -> MacOS -> ファイル名を "SceneBuilder" から "scenebuilder-launcher.sh" に変更.

とりあえず起動した.

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

解法

dpらしい.div2Medだし貪欲だろうと高をくくっていたら駄目でした.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int dp[1<<21];
class OrderOfOperationsDiv2{
public:
	int minTime(vector<string> s){
		for(int i=0;i<(1<<20);i++)dp[i] = 1e9;
		vector<int> bit(s.size());
		int ok=0;
		for(int i=0;i<s.size();i++){
			int tmp = 0;
			for(int j=0;j<s[i].size();j++){
				tmp <<= 1;
				if(s[i][j] == '1')tmp += 1;
			}
			bit[i] = tmp;
			ok |= tmp;
		}
		
		dp[0] = 0;
		int n = s[0].size();
		for(int i=0;i<s.size();i++){
			for(int k=0;k<(1<<n);k++){
				if(dp[k] == 1e9)continue;
				for(int j=0;j<s.size();j++){
					int l = __builtin_popcount(~k & bit[j]);
					dp[( k | bit[j] )] = min( dp[(k | bit[j])], dp[k] + l*l );
				}
			}
		}
		
		int ret = 1e9;
		for(int i=0;i<(1<<n);i++){
			if( (i&ok) == ok){ 
				ret = min(ret,dp[i]);
			}
		}
			
		return ret;
	}
};