AR# 50826 『ブロックRAM から OCM へのキャッシュ コヒーレントの CDMA 転送 』を試した
HW関連の研究室でZynq All Programmable SoCを触っています。
正直Xilinxのマニュアルは難しすぎてよくわからない・・・体系的に学べるといいのだけれど。
オンチップメモリ(OCM)への書き込みをテストするために調べていたら、以下のページが見つかった。
https://japan.xilinx.com/support/answers/50826.htmljapan.xilinx.com
今回はこれを試してみた。自分なりの解釈とかのメモを残す。
このアプリケーションは何か
このアプリケーションはBRAMの64箇所に0x01から0x40の値を、OCMの64箇所に0xCDの値をセットした後、CDMA(Central Direct Memory Access)を使用してBRAMからOCMへデータを送信する。送信後OCMの64箇所の値が0x01から0x40になっていれば成功。
BRAM
FPGA上に配置することができるRAM。BRAM Generator IPがBRAM本体で、データの送受信はBRAM Controllerで動作させる。
OCM
256KBのオンチップメモリがPS上のAPU内に存在する。ACPポートは直接ここにつながっている?(よくわかっていない)
手順(いつものやつ。この本とかに詳しく書いています。)
1. プロジェクトをダウンロードしてVivadoで開いてビットストリーム生成
2. Export HardwareしてSDK(SDSoC)起動
3. File -> New -> Application Projectを選択、Hello Worldプロジェクトを作成し、添付されているhello_axi_cdma.cの内容をhelloworld.cにコピペ
4. Xilinx Toolsを開いてProgrammable FPGAを選択してビットストリーム書き込み
5. Build Allして実行用のelfファイル作成。右クリックしてRun As -> Launch On Hardware (System Debugger)を選択。
6. TeraTermなどから出力を確認(ポートレート115200に設定)
これで動けばよかったのだけど動かなかった。OCMの値全てが0xCDのままになっていた。
修正箇所
結論から言えば、サンプルソースの53行目を
Xil_SetTlbAttributes(0xFFF00000,0x14c0e);
から
Xil_SetTlbAttributes(0xFFF00000,0x14de2);
に修正。
あるいは、Xil_SetTlbAttributes(0xFFF00000,0x14c0e);をコメントアウトし、
CDMAによる転送が終了した後の121行目などに、
Xil_DCacheInvalidateRange(dstCPU, 64*8);
を挿入。
Xil_SetTlbAttributesとは何か
色々調べてみると、TRM(テクニカルリファレンスマニュアル)UG585の73ページ図3-5にページエントリのフォーマットが書いてある。
またココによると図のSectionの欄が空欄になっているけどSuperSectionと同じらしい。
TEX[2:0], C, Bなどのビットが大切らしい。DomainとかXNとかnGは謎パラメタ・・・
Xil_SetTlbAttributesはキャッシュのポリシーなどを変更するための関数であるということがわかった。
0x14c0eは2進表記で0001_0100_1100_0000_1110 C=1 B=1 キャッシュ属性は「ライトバック、書き込み割り当てなし」
これだとキャッシュが有効になっているのでCDMAが成功していてもアプリケーションは古い値を参照してしまう。
0x14de2は2進表記で0001_0100_1101_1110_0010 C=0 B=0 キャッシュ属性は「キャッシュ不可」
キャッシュを切ることによってアプリケーションは正しい値を参照することができる。
CDMAやDMAを使用したとき、古い値を参照しないように気を付ける必要があるらしい。
DMAを使用したときは Xil_SetTlbAttributesなんて使っていなかったなと思って、Xil_DCacheInvalidateRangeを試したところ、これでもOKだった。
この関数だと、指定したアドレス範囲のデータに関してのみキャッシュが無効化され、新しい値が参照されるようになる。
その他
DMAを使用したときはVivadoでビットストリームを生成したときに出力されるドライバファイルxaxidma.h内で宣言される関数XAxiDma_SimpleTransferを使用してデータ送受信を行っていた。このサンプルアプリケーションにはそのような関数が含まれておらず、最初は意味がわからなかった。
CDMAのリファレンスを読んでみたところ解決した。
CDMAの制御レジスタを直接変更することでエラー割り込み、終了割り込みの有効化・送受信先アドレスの設定・データ転送開始を制御している。
また、ダウンロードしたサンプルのデザインを実行しても動かなかったので、手作業で回路を作り直した。
Vivado内でBRAMを配置した際にBRAMのサイズが変更できずに困っていたところ、以下のようなリンクを発見した。
https://forums.xilinx.com/t5/Design-Entry/how-to-edit-bram-controller-bram-memory-size/td-p/637284
BRAM GeneratorのWidthとDepthの欄はマスター側によって自動的に決まると書いてあった。
BRAMコントローラでBRAMのサイズを変更できないな~と思っていたら、Address EditorでBRAMコントローラに与えるアドレス範囲を変更することでBRAMのサイズが変更できる。
コード
Xilinxのサンプルコードを修正・コメント文を追加したものをおいておきます。
gist.github.com
分からないことも多いまま試行錯誤しているので、間違っているところなどあれば教えてください。
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のドライバかけるのすごい.
おわり.
Yahoo!ボックス からファイルを一括ダウンロードするスクリプト
Yahoo!ボックスとかいうオンラインストレージサービスがあるらしい。
info.box.yahoo.co.jp
アプリが終了してブラウザから1つ1つダウンロードするしかないらしい。助けてくれ!と友人に頼まれた。
しばらくChromeのデベロッパーツールで眺めていると、ファイル情報をJSONでやりとりしているだけなようなので、書いた。
はじめはRuby の Mechanize を使って Yahoo! JAPAN にログインする - kaosf’s diaryを参考にしてログイン処理をしていたが、途中からログインできなくなった。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万以上してびっくりした。
https://twitter.com/lp6m/status/755416445589164032
で、友達がもうちょっと7セグとかスイッチとか標準装備してるやつ買おうって言ったので便利そうだし買った。
https://twitter.com/lp6m/status/757829385953042432
試験が終わったら色々やってみたい。夏休みにどこまでいじれるかな。
Verilogのテストベンチ(bdfファイルとかRAMとかの話)
大学の学生実験でFPGAボード上で簡単なCPUを作っている(easyではない).
使っているツールはALTERA社のQuartusというツール.これでANDとかORとかDフリップフロップとかをぽちぽちして回路を作る.
ぽちぽちの回路はBlock Diagramというらしい〜
Quartusにはmodelsimというシミュレータもあるけど、とりあえず今回はicarus-verilog http://iverilog.icarus.com/を用いてテストをしてみました.
QuartusはWindowsとLinuxにはあるのにMacにはなくて悲しい.
Verilog HDLでつくったモジュールとBlock Diagramでつくったモジュールが混在した回路でも問題なくテストできました.
適当に回路を作る
3進カウンタをつくりました.ぽちぽち.
次にこれを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
テストを書く.
テストについては「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を使ったりします.
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; } }