lp6m’s blog

いろいろかきます

ICPC2017国内予選に参加しました

久々にブログを書いた
1年前:
lp6m.hatenablog.com

2年前:
lp6m.hatenablog.com

去年と同じメンバーで出た。チーム名はfoldLeft.
特に練習もしていないので自分は簡単な問題を解こうとおもっていた。
自分はABを通してチームメイトがCDを解いた。D解けるのすごい。
46位/368チームでした 2桁になれたのはチームメイトのおかげ。

勉強しないとな~

UbuntuやElementary OSでスリープ後に画面の明るさが変更できないのを解消できた

先日気が狂ってmacOSを消した.
UbuntuベースのElementary OSというOSをインストールした.
なんかスリープ後に画面の明るさが調節できなくてつらかったのでググりまくった.
いろんな情報がでてきたけどどれもダメでつらいなあとおもっていたら,今日はやっとみつけることができた.

まずココに同じ問題が書かれてる.
MacBookAir6-2/Trusty - Community Help Wiki

Mac用にドライバを書いてくれた人がいるみたい.インストールしようとした.READMEにしたがってすすめていく.
make installで以下のようなエラーがでて失敗する.

- SSL error:02001002:system library:fopen:No such file or directory: bss_file.c:175
- SSL error:2006D080:BIO routines:BIO_new_file:no such file: bss_file.c:178
sign-file: certs/signing_key.pem: No such file or directory

つらいと思ってしらべたら、同じのがあった.
github.com
make installできないときは,checkinstallってのを使えばいいらしい.
sudo apt install checkinstall
mba6x_blのディレクトリ内でcheckinstallのコマンドを叩く. なんかパッケージの説明をかけとか言われるので「Macのがめんの明るさ設定する」って書いた.
そしたらディレクトリ内にdebが作成された.checkinstallってのはdebを生成するコマンドらしい?
最後にsudo -i dpkg ~.debでインストール.
READMEに書いてる最後の手順のsudo modprobe mba6x_bl をしたらちゃんと反映された.

たぶんいまのところ動いてるっぽいのでよかった.インターネットすばらしいしMacのドライバかけるのすごい.

おわり.

MagSafe2を修理した

結構がんばってキレイに直せた
MagSafeにはネジなんかなくて接着剤で固められてただけなので結束バンドしないと開いてくる。

Yahoo!ボックス からファイルを一括ダウンロードするスクリプト

Yahoo!ボックスとかいうオンラインストレージサービスがあるらしい。
info.box.yahoo.co.jp
アプリが終了してブラウザから1つ1つダウンロードするしかないらしい。助けてくれ!と友人に頼まれた。
しばらくChromeデベロッパーツールで眺めていると、ファイル情報をJSONでやりとりしているだけなようなので、書いた。

はじめはRuby の Mechanize を使って Yahoo! JAPAN にログインする - kaosfield blogを参考にしてログイン処理をしていたが、途中からログインできなくなった。Mechanizeだと今どのような状態なのかがわかりにくいので、Selenium-webdriverを使って再現してみると、文字認証を求められていた。
探してみるとrubyでYahoo Japanにログインする。Cookie発行してもらう - それマグで!のような情報がでてきたので、使わせていただいた。
(微妙にCAPCHAのURLの種類が違ったのでそのへんだけ書き換えたりした)
2016/12/30 Windows環境で動作させると,txt以外がファイルが壊れるとの指摘をいただきました。訂正しました。

#参考:http://takuya-1st.hatenablog.jp/entry/20121018/1350587902
#!/usr/bin/env ruby
#coding:utf-8
require 'rubygems'
require 'mechanize'
require 'open-uri'
require 'net/http'
require 'uri'

OpenSSL::SSL::VERIFY_PEER = OpenSSL::SSL::VERIFY_NONE

Id       = 'XXXXXXXXXXXXXXXX'
Password = '****************'
cookie_jar_yaml_path = 'yahoo.yaml'
#Yahoo!ログイン
agent = Mechanize.new
agent.user_agent_alias = 'Windows IE 7'
agent.get('https://login.yahoo.co.jp/config/login?.src=www&.done=http://www.yahoo.co.jp')
agent.page.form_with(name: 'login_form') do |form|
	form.field_with(name: 'login').value = Id
	form.field_with(name: 'passwd').value = Password
	# agent.page.body =~ /\("\.albatross"\)\[0\]\.value = "(.*)"/
	# form.field_with(name: '.albatross').value = $1
	form.click_button
end

#CAPTHCA
str = agent.page.body.match( %r!"https://captcha.yahoo.co.jp:443/[^"]+!).to_s.gsub(/"/,"")
puts str
open(str) do |file|
  open("captcha#{Time.now.to_i}.jpg", "w+b") do |out|
    out.write(file.read)
  end
end
capthca = ''
$stdout.print 'enter captcha:'
captcha = $stdin.readline
puts "i got captcha#{captcha}"
agent.page.forms.first.fields_with(:type=>"text").first.value=captcha
agent.page.forms.first.submit

#CAPTHCA後の再ログイン
f=agent.page.forms[0]
f.fields_with( :name=>"login")[0].value=Id
f.fields_with( :name=>"passwd")[0].value=Password
f.submit


puts agent.page.body.to_s.toutf8

agent.cookie_jar.save_as(cookie_jar_yaml_path)
File.expand_path cookie_jar_yaml_path

これを実行すると、ログイン情報のクッキーがyahoo.yamlというファイルに出力される.

次に、Yahoo!ボックスからファイルを一括ダウンロードするスクリプトを実行する

#Yahoo! Box Downloader
require 'mechanize'
require 'nokogiri'
require 'kconv'
require 'scanf'
require 'date'
require 'uri'
require 'json'
require 'erb'
require 'net/http'
require 'open-uri'
include ERB::Util

cookie_jar_yaml_path = 'yahoo.yaml' #ログイン情報のクッキーを保存したファイル
filenum_of_page = 100 #一度に読み込むファイル数 20,50,100のどれか

#Yahoo!Boxへアクセス
agent = Mechanize.new
agent.user_agent_alias = 'Windows IE 7'
agent.cookie_jar.load(cookie_jar_yaml_path)
page = agent.get('https://box.yahoo.co.jp/user/viewer')	


#Javascriptの文字列からsid,uniqid,crumb,appidを取り出す
tmp_rst = page.search('script')[0]

user_parmsstr = tmp_rst.to_s.split("\n")[2].split(',')
crumb_parameter = tmp_rst.to_s.split("\n")[3].split(',')
appid_parameter = tmp_rst.to_s.split("\n")[4].split(',')

sid = user_parmsstr[0].scanf("    User  = {\'sid\':\"%s\"")[0].to_s
topuniqid = user_parmsstr[1].scanf(" \'uniqid\':\"%s\"},")[0].to_s
crumb = crumb_parameter[1].scanf("'bcrumb':\"%s")[0].to_s
appid = appid_parameter[0].scanf("\t\t'appid':\'%s")[0].to_s
puts appid
#scanfうまくいかないのでうしろの"を消す 正規表現ちゃんとかくべき^^;
sid = sid[0,topuniqid.index("\"",2)+1]
topuniqid = topuniqid[0,topuniqid.index("\"",2)]
crumb = crumb[0,crumb.index("\"",2)]
appid = appid[0,appid.index("'",2)]
puts "sid = #{sid}"
puts "uniqid = #{topuniqid}"
puts "crumb = #{crumb}"
puts "appid = #{appid}"

#ここから巡回してファイルをダウンロード	
folderList = Array.new
folderList.push(topuniqid)
#folderListが空になるまで巡回する
while folderList.size != 0 do
	#folderListから一つ取り出す
	nowuniqid = folderList.pop
	#そのフォルダ内のファイルのリストが書かれたJSONを取得する
	urlstr = "https://box.yahoo.co.jp/api/v1/filelist/" + sid + "/" + nowuniqid + "?_=" + DateTime.now.strftime('%Q').to_s + "&"
	urlstr << "results=#{filenum_of_page}&start=1&output=json&sort=%2Bname&filetype=both&meta=1&thumbnail=1&tree=1&sharemembercount=1&ownerinfo=1&boxcrumb="
	urlstr << url_encode(crumb)
	agent.get(urlstr)
	jsonstr = JSON.parse(agent.page.body.to_s)
	# 複数ページが存在する場合はまず全ページたどってファイル情報を入手
	filenum = jsonstr['ObjectList']['TotalResultsAvailable'].to_s
	unless jsonstr['ObjectList']['Object'] == nil
		jsonstr['ObjectList']['Object'].each do |object|
			type = object['Type'].to_s
			name = object['Name'].to_s
			uniqid = object['UniqId'].to_s
			dlurl = object['Url'].to_s
			path = "." + object['Path'].to_s #パスの先頭にドットをつけないとうまく相対パスにならない
			#ファイルかフォルダかで処理を分岐
			if(type == 'file') then
				dlurl << "?appid=#{appid}&error_redirect=1&done=https%3A%2F%2Fbox.yahoo.co.jp%2Ferror%2Fdownload_error&boxcrumb="
				dlurl << url_encode(crumb)
				#dlurlからリダイレクトされたURLを取得 これがダウンロードリンク
				agent.get(dlurl)
				redirect_link = agent.page.uri.to_s
				#ファイルを保存
				#File.write(path, Net::HTTP.get(URI.parse(redirect_link)))
				open(redirect_link) do |file|
					open(path, "w+b") do |out|
						out.write(file.read)
					end
				end
				puts "Download #{path}"
			elsif(type == 'dir') then
				#folderListに追加してあとで巡回
				folderList.push(uniqid)
				Dir.mkdir(path)
			end
		end
	end
end

詳しく解説してもたぶん需要なさそうなので、コードはりつけておしまい。
sleepをはさんで、負荷かけないようにしてつかいましょう。

一応gistこちらも修正しました[2016/12/30]

https://gist.github.com/lp6m/5913c1ef770f75825b00081a6ed7f671
https://gist.github.com/lp6m/a4e927963e218884e2a843e40e7a22b5

FPGAを買った。

計算機科学実験及演習3(ハードウェア)FPGAを触った。パイプライン処理くらいはつくったけどバグがでてしまってソートコンテスト出れなかった。
FPGA面白いな~と思って実験でつかってるボードが何円するのか調べたら10万以上してびっくりした。

これを買って組み立ててほんのすこしだけ触った。

で、友達がもうちょっと7セグとかスイッチとか標準装備してるやつ買おうって言ったので便利そうだし買った。

www.terasic.com.tw

試験が終わったら色々やってみたい。夏休みにどこまでいじれるかな。

Verilogのテストベンチ(bdfファイルとかRAMとかの話)

大学の学生実験でFPGAボード上で簡単なCPUを作っている(easyではない).

使っているツールはALTERA社のQuartusというツール.これでANDとかORとかDフリップフロップとかをぽちぽちして回路を作る.

ぽちぽちの回路はBlock Diagramというらしい〜

Quartusにはmodelsimというシミュレータもあるけど、とりあえず今回はicarus-verilog http://iverilog.icarus.com/を用いてテストをしてみました.

QuartusはWindowsLinuxにはあるのにMacにはなくて悲しい.

Verilog HDLでつくったモジュールとBlock Diagramでつくったモジュールが混在した回路でも問題なくテストできました.

適当に回路を作る

3進カウンタをつくりました.ぽちぽち.
f:id:lp6m:20160704042511p:plain
次にこれをVerilog HDLに書き出します.
メニューから File -> Create/Update -> Create HDL Design from Current File ... を選択してVerilog HDLを選んで,保存.
複数のモジュールを使用している際はすべてのモジュールをそれぞれ書き出します.
もちろんもともとVerilog HDLでモジュールをつくっている場合はそのままでOK.
書き出されたファイルは以下のようなものです.

// Copyright (C) 1991-2015 Altera Corporation. All rights reserved.
// Your use of Altera Corporation's design tools, logic functions 
// and other software and tools, and its AMPP partner logic 
// functions, and any output files from any of the foregoing 
// (including device programming or simulation files), and any 
// associated documentation or information are expressly subject 
// to the terms and conditions of the Altera Program License 
// Subscription Agreement, the Altera Quartus Prime License Agreement,
// the Altera MegaCore Function License Agreement, or other 
// applicable license agreement, including, without limitation, 
// that your use is for the sole purpose of programming logic 
// devices manufactured by Altera and sold by Altera or its 
// authorized distributors.  Please refer to the applicable 
// agreement for further details.

// PROGRAM		"Quartus Prime"
// VERSION		"Version 15.1.1 Build 189 12/02/2015 SJ Lite Edition"
// CREATED		"Mon Jul 04 04:11:37 2016"

module counter(
	clear,
	clock,
	Q1,
	Q2
);


input wire	clear;
input wire	clock;
output wire	Q1;
output wire	Q2;

wire	SYNTHESIZED_WIRE_0;
wire	SYNTHESIZED_WIRE_3;
reg	SYNTHESIZED_WIRE_4;
reg	DFF_inst1;

assign	Q1 = SYNTHESIZED_WIRE_4;
assign	Q2 = DFF_inst1;
assign	SYNTHESIZED_WIRE_3 = 1;




always@(posedge clock or negedge clear or negedge SYNTHESIZED_WIRE_3)
begin
if (!clear)
	begin
	SYNTHESIZED_WIRE_4 <= 0;
	end
else
if (!SYNTHESIZED_WIRE_3)
	begin
	SYNTHESIZED_WIRE_4 <= 1;
	end
else
	begin
	SYNTHESIZED_WIRE_4 <= SYNTHESIZED_WIRE_0;
	end
end


always@(posedge clock or negedge clear or negedge SYNTHESIZED_WIRE_3)
begin
if (!clear)
	begin
	DFF_inst1 <= 0;
	end
else
if (!SYNTHESIZED_WIRE_3)
	begin
	DFF_inst1 <= 1;
	end
else
	begin
	DFF_inst1 <= SYNTHESIZED_WIRE_4;
	end
end


assign	SYNTHESIZED_WIRE_0 = ~(SYNTHESIZED_WIRE_4 | DFF_inst1);


endmodule

icarus-verilogのインストール

Macだと

brew install icarus-verilog 

でおわり.

テストを書く.

テストについては「Verilog testbench」とかでしらべたら山のようにでてくるのでググる.
とりあえず上の回路に対応するベンチを書いてみました.

//counter_test.v
module counter_test;
//テストベンチの入力はreg
//テストベンチの出力はwire
//複数行にかいてもいい.バスのときはreg[15:0] Q;とか. 
reg clear, clock;
wire q2,q1;

parameter STEP = 100;

//常に実行される
always begin
	clear = 1'b1;
	#(STEP/2) clock = !clock;
end

//最初に一度だけ実行される
initial begin
	clear = 1'b0;
	clock = 1'b1;
	//monitorは引き数の値が1つでも変わった時に値を表示するように設定する.(alwaysにはかかないものらしい)
	$monitor("Counter: %b%b", q2, q1);
	#1000 $finish; //1000STEPで停止
end

//インスタンスの作成(回路の呼び出し)counter_instance はなんでもいい
//counter の部分は呼び出したいモジュールのVerilogファイルの1行目にあるモジュール名を入れる.
//引数はVerilogファイルの冒頭にあるinputの/outputにある順番にかく.
counter counterinstance(clear,clock,q1,q2);
endmodule

コンパイル

使用したモジュールすべてのVerilogファイルと、テストベンチのファイルをすべてまとめてコンパイルします.

iverilog -o counter counter.v counter_test.v 

たくさんある場合は

 iverilog -o simple2 simple2.v ./lib/phase/*.v ./lib/selector/*.v ./lib/other/*.v ./lib/component/*.v ./lib/calc/*.v ./lib/cable/*.v ./lib/7SEG/*.v dummy_ram.v simple2_test.v

こんなかんじ.

  • oの後に指定したファイル名でコンパイルされたファイルが出力されます.
vvp counter

または

./counter

と入力すればシミュレーションがはじまります.

Counter: 00
Counter: 01
Counter: 10
Counter: 00
Counter: 01
Counter: 10
Counter: 00
Counter: 01
Counter: 10
Counter: 00
Counter: 01

無事にシミュレーションできました.

ハマった点としては,ぽちぽちでカウンタを作る際に、DFFのpresetを1にしておけば,DFFの出力の初期値は0だと思っていたのですが、出力されたVerilogのコードを読んだところ,初期値については何もかかれておらず,テストするとxx(値不定)となってしまいました.
そのため上のテストベンチではinitialブロック内でclear = 0として一度クリアしています.
Verilog、入門のページみながら適当にかいたりしているけど難しい・・・・・・・・・・・・・・

RAMについて

CPUをつくる実験ではRAMを使ったりします.
f:id:lp6m:20160704101153p:plain
RAMはQuartus上ではVerilogに変換できないので,自分でダミーのVerilogファイルを書きます.

module ram(
    input [15:0] data,
    input wren,
    input wire [11:0] address,
    input clock,
    output reg [15:0] q
    );

    //16bit幅 4096word
    (* ram_style = "BLOCK" *) reg [15:0] bram[0:4095]; 
    
    initial begin
        bram[12'd0] = 16'b1000000000000001;
        bram[12'd1] = 16'b1000000100000011;
        bram[12'd2] = 16'b1100100000000000;
        bram[12'd3] = 16'b1100000011010000;
        bram[12'd4] = 16'b1000000100000101;
        bram[12'd5] = 16'b1100100000000000;
        bram[12'd6] = 16'b1100000011010000;
    end

    always @(posedge clock) begin
        if(wren)
            bram[address] <= data;
        else
            q <= bram[address];
    end

endmodule

こんなかんじでダミーのRAMをつくればOK.(説明が雑)
wrenが1のときにclockがはいったらdataの内容をbram[address]に書き込んで,wrenが0のときはbram[address]の内容をqに入れて出力というのをかいただけ.
とりあえずこれでデバッグできるようになったので嬉しいです〜〜〜
ぽちぽちのときは値不定なんてほとんどないと思うんだけどVerilogでかくとif文の条件分岐とかが足りてないと値不定になってしまってなるほどなあというかんじ.

ここ間違ってるとか表記おかしいとかあったら教えてください.

ICPC2016国内予選に参加しました

今年も参加しました.情報学科3人で.
2年前: 126位 LP6m メモ ICPC予選に参加してきました
1年前: 90位 ICPC2015国内予選に参加しました - lp6m’s blog

今年: 67位 3完
去年は「来年は4完するぞ」とか言ってたのにできなかった.
去年終わってから競プロの勉強をぜんぜんしてこなかったし,前日までHardware and Software Laboratory Project 3B (Software Part) に追われていたのが完全に悪い.それでもとりあえずいま自分ができる実力を発揮しようということで頑張った.

A問題 4分

2重forループ回しただけ.
チーム全員で問題を読んだ.自分は後ろでコードを眺めて指示したりした.2分でかいて4分でACしたっぽい.
ちなみにこの時点では15位でイエーイとか言ってた.

int main(){
	while(1){
		int n;
		cin >> n;
		if(n == 0) break;
		ll int a[1001];
		for(int i = 0; i < n; i++){
			cin >> a[i];
		}
		long long int res = 1000000000;
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(i == j) continue;
				res = min(res, abs(a[i] - a[j]));
			}
		}
		cout << res << endl;

	}
}

B問題 24分

自分はCを読んでいたので問題を見ていない.ちょっとだけハマったらしいけど焦ってたからだと思う.

int main(){
	while(1){
		int n;
		cin >> n;
		if(n == 0) break;
		map<char, int> m;
		for(int i = 0; i < 26; i++){
			m[i + 'A'] = 0;
		}
		char tmp[101];
		for(int i = 0; i < n; i++){
			cin >> tmp[i];
		}
		for(int i = 0; i < n; i++){
			char c = tmp[i];
			m[c]++;
			vector<pair<int, char> > result(26);
			for(int i = 0; i < 26; i++){
				result.push_back(make_pair(m['A' + i], 'A' + i));
			}
			sort(result.begin(), result.end());
			reverse(result.begin(), result.end());
			int sub = result[0].first - result[1].first;
			if(sub > n - i - 1){
				cout << result[0].second << " " << i + 1 << endl;
				break;
			}
			if(i == n - 1) cout << "TIE" << endl;
		}
	}
}

C問題 70分

自分はCをずっと眺めていたのにふるいすれば終わりに気がつかなかった。言われて実装したらなんかなかなか処理が終わらない.ぼくが無駄な処理してるところに気がついて直してAC

int oksize  = 7400000;
int main(){
	int n,m;
	bool ok[oksize];
	while(1){
		cin >> m >> n;
		if(n == 0 && m == 0) break;
		REP(i,oksize) ok[i] = true;
		REP(i,m) ok[i] = false;
		int cnt = 0;
		int tmp = m;
		REP(j,n){
			for(int i = 0; i * tmp < oksize; i++){
				if(i*tmp < m) continue;
				ok[i*tmp] = false;
			}
			FOR(i,tmp,oksize){
				if(ok[i]){
					tmp = i;
					break;
				}
			}
		}
		cout << tmp << endl;
	}
}

D問題 提出できず

C問題をACしてとりあえず去年と同じなのでホッとした.D問題を読んだ.ダルマのどこを崩すかって枝分かれしていくわけだからdfsを思いついたので一番競プロをまじめにやってるチームメイトに書いてもらった.サンプルが通ったので入力データをダウンロードして実行したが全然終わらない.とりあえずメモ化できるのでメモ化してみたんだけど、全然早くならなかった.
結局そのまま試合終了まで考えてもどうにもならなくて終わってしまった.
以下、遅いコード

int n;
int ans = 0;
map<vector<int> , int> m;

int solve(vector<int> v){
	// cout << v.size() << endl;
	if(m.find(v) != m.end()) return m[v];
	m[v] = n - (int)v.size();
	for(int i = 0; i < ((int)v.size() - 1); i++){
		//cout << "jhe" << v.size() <<" " <<  i << endl;
		if(abs(v[i] - v[i + 1]) <= 1){
			vector<int> newv = v;
			newv.erase(newv.begin() + i);
			newv.erase(newv.begin() + i);
			m[v] = max(solve(newv), m[v]);
		}
	}
	return m[v];
}
 
int main(){
	while(1){
		cin >> n;
		if(n == 0) break;
		vector<int> w;
		for(int i = 0; i < n; i++){
			int tmp;
			cin >> tmp;
			w.push_back(tmp);
		}
		ans = 0;
		m.clear();
		cout << solve(w) << endl;
	}
}

反省

Cはもっとはやくふるいで解けることに気がつくべきだった.まあ全然練習してないので雑魚なのは当然.
コンテストに出るたびにやっときゃよかったとか行ってるので少しくらいがんばってみるかなあという感じ.
今日は平安神宮に行った.精進しろと言われた.
f:id:lp6m:20160626150841j:plain


あとは全然関係ないのだけど前日まで追われていた実験でCっぽいSmallCのコンパイラを作ったのは面白かった.
文系の父親が大学生のときくらいにかいていたZ80アセンブラのコードを印刷したノートが家にあって、実験のことについてたくさん話せただろうなあとかおもってすこし寂しかった.