utsubo’s blog

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

最大フロー問題(循環フロー問題)の双対をとる

はじめに

近似アルゴリズム(V.V.ヴァジラーニ)の12章に最大フロー問題とその双対問題が載っているのだが、どのように変形したらその双対問題の式が得られるのか結構悩んだ。
そこで、未来の自分のために最大フロー問題から双対問題を導出する過程をまとめておく。

最大フロー問題と双対問題

最大フロー問題についてはリンク最大フロー問題 - Wikipediaを参照。

まず、近似アルゴリズム(V.V.ヴァジラーニ)では下記のように定式化されている。
一般的な最大フロー問題に、 tから始点 sへ容量が無限大の仮想的な辺を加え、循環フロー問題として考えている。
そうすることで、 sでもフロー保存則が成り立つ.また、このとき目的関数では、仮想的な辺を流れるフロー f_{ts}を最大にすることになる.

f:id:utsubo_21:20180518230556p:plain:w600

制約式の意味は

  1. 辺を流れるフロー量が容量を超えない。
  2. フロー保存則(頂点に入ってくるフロー量より出ていく量の方が大きい)

これの双対を取ると下式になるとのこと。

f:id:utsubo_21:20180518230853p:plain:w600


実際に主問題を式変形をして、双対問題を得てみる。

双対をとる

まず、双対問題とは主(最大化)問題の上界を求める問題といえる(詳しくは後述)。
主問題の制約式の1つ目の両辺に d_{ij}、2つ目の両辺に p_iを掛ける。

f:id:utsubo_21:20180518231614p:plain:w600

(3a)と(3b)の和は、 d_{ij} p_iの設定によっては、主問題の上界となる。
この上界を d_{ij} p_iを上手く設定して最小化するのが、双対問題である。
(4) = (3a) + (3b)

f:id:utsubo_21:20180520120544p:plain:w600

上式が上界になる条件は「(4)左辺の f_{ij}の係数の和が、主問題の目的関数の f_{ij}の係数より大きい」であり、これが双対問題の制約式となる。

(4)(=(3a)+(3b))の左辺の f_{i,j}の係数について考える。

(3a)で f_{ij}は、 d_{ij}f_{ij}がある。

(3b)では、頂点 iと頂点 jについての不等式で必ず現れる(元はフロー保存則を表す式なので)。
頂点 jには、フロー f_{ij}が流れこむはずなので、 p_j f_{ij}が必ず存在し、
頂点 iには、フロー f_{ij}が出ていくはずなので、 -p_i f_{ij}がある。

よって、双対問題の制約式は、
f:id:utsubo_21:20180518233809p:plain:w300
となる。(主問題の目的関数に f_{ts} + \sum{0 f_{ij}}があると考えれば右辺はわかる。)

目的関数は(4)の右辺を最小化することであり、制約式は(5)なので整理すると、
f:id:utsubo_21:20180518234427p:plain:w600

ここで、目的関数では、 c_{ts} d_{ts}が出てくるが、
 c_{ts}は無限の容量を持つと定義したので、 d_{ts}は0以外の値を取れないことが自明にわかる。
そのため、最初に出てきた双対問題の式とこの式は一致する。

双対問題は主問題の下界(上界)を求める問題

例えば、下記の最大化問題で考える。
f:id:utsubo_21:20180520124631p:plain:w400


この問題の制約式の和を取れば、
f:id:utsubo_21:20180520130419p:plain:w300

上式の左辺は、係数の関係から最大化問題の目的関数より大きい。( x_iは非負なため)
f:id:utsubo_21:20180520130603p:plain:w250

よって、制約式の関係から、解が 20で上から抑えられることがわかった。

もう少し一般化して考え、制約式の両辺にそれぞれ非負な数 y_1,y_2を掛けた和を取る。
f:id:utsubo_21:20180520125315p:plain

 12y_1 + 8y_2が上界になるのは、 x_iの係数の関係により、下式を満たすときである。
f:id:utsubo_21:20180520125606p:plain:w150

この条件を満たした上で y_iを調整することで、 12y_1 + 8y_2を最小化すれば、上界を最適解に近づけることができる。(実際は最適解と一致する)
それが双対問題である。
f:id:utsubo_21:20180520130042p:plain:w300

あとがき

間違っているところ多そうなので突っ込み貰えると嬉しいです。
双対の取り方とその意味がやっとわかりました。
いちいちLaTeXiTで数式の画像を生成して貼って、さらにサイズ調整とか面倒だったので、LaTeXで全部書いてpdfで上げればよかったと思いました。

「Linuxのしくみ」を読んで

はじめに

gihyo.jp
を読みました。

感想

低レイヤ寄りのことを知りたかったので読み始めました。
基本的な用語でも分かってないことがあったので為になりました。
この仕組みで複雑なアプリケーションが動いてるの凄すぎて気持ち悪い。

7章ぐらいから飽きてきてあんまりきちんと読めていないので、そのうち読み直します。
次は、OSの作り方でも読もうかと思います。

メモ

ただのメモ。

1,2章
3章 プロセス管理
4章 プロセススケジューラ
  • スループットとレイテンシ
  • プロセスのスケジューリング(niceで優先度設定ができる)
5章 メモリ管理
  • taskset(cpu指定(それ以外にも色々機能がありそう)),time,ps(時間計測,ユーザ/カーネルモード)
  • OOM killer(Out Of Memory)(メモリが足りなくなった時に適当に要らなそうなやつをkillする機能、vm.panic_on_oom)
  • プロセス毎に 物理メモリに割り当て→ページテーブル(カーネルのメモリ上)作成(mmap)
  • mmap()でページ単位で確保→mallocは内部でそれを切りわけて使っている
  • 無駄なメモリ確保を防ぐデマンドページング(カーネルが初アクセス時に物理メモリへ割り当てる)
  • Copy On Writeとは何か(fork()システムコールの時に仮想記憶が役に立っている、fork後が書き換えられた時にコピーする)
  • OOMの救済にSwap、メモリ↔ストレージのスワップ領域
  • メジャーフォールト(ストレージへのアクセスが発生)←こっちが重い、マイナーフォールト(ストレージへはアクセスしない)
  • ヒュージページ(ページテーブルのメモリを減らす機構、まとめるページ単位を大きくまとめる)
  • トランスペアレントヒュージページ(自動でヒュージページと通常モードを切り替える、Ubuntu16.04ではデフォで有効)
6章 記憶階層
  • ライトバック方式(所定のタイミングでバックグラウンドでメモリに書き込む)、ライトスルー方式(キャッシュラインがダーティになった瞬間にメモリに書き込む)
  • L3キャッシュはCPUで共有してたりする
  • 参照の局所性(近い場所の又近い時間でデータにアクセスすることが多いので基本的にキャッシュが働く)
  • キャッシュでは、物理メモリのページテーブル参照は高速化されない→Translation Lookaside BufferというCPUの機能がある
  • トランスレーション・ルックアサイド・バッファ - Wikipedia MMUがやってるらしい
  • ページキャッシュ(メモリ↔ストレージ)の話、こっちはキャッシュライン単位でなくページ単位で扱う(キャッシュメモリはCPU↔キャッシュメモリ↔メモリ)
  • ダーティページのライトバック周期はvm.dirty_writeback_centisecsパラメータで設定できる
  • or vm.dirty_background_bytesの割合が超えた時ライトバック発生
  • ハイパースレッド機能(よく分からんから後で調べる)
7章 ファイルシステム
  • 容量制限=クォータ(ディレクトリ、ユーザ、サブボリューム等ごとに制限が掛けれる)
  • ファイルシステムの不整合を防ぐ方式→ジャーナリングトランザクションみたいな)、コピーオンライト(アホほどコピーとる)
  • それでも駄目な時はfsck、だけど時間かかる割に望んだ結果にならないことが多い
  • キャラクタデバイス、ブロックデバイスとは?(よく分かってないから後で調べる)
  • tmpfs、メモリ上のファイルシステム、凄そうだけどこれもよく理解できてない
  • ネットワークファイルシステムWindows→cifs、Linuxnfs
  • プロセスの情報は/proc以下にマウントされたprocfsで分かる(top,freeはここから採取)
  • sysfsはprocfsの濫用を防ぐためにできた
  • cgroupでリソース(CPU、メモリ)使用量に制限を掛けられる
  • Btrfs、ファイルシステムのすごいやつらしい
8章 ストレージデバイス
  • I/Oスケジューラ(連続したセクタから読み出す)、先読み
  • SSDは電気的な処理なので読み書きが早い

あとでやる

  • sarの使い方をまとめる
  • ふつうのLinuxを読む
  • OSの作り方を読む

2017年振り返りと2018年の目標

はじめに

最近,何も書いていないなと思ったらもう年末だったので,振り返りでもしようと思います.

2017年の目標と達成度

年始にふんわり立てていた目標と達成度.

  • 競プロ:週に1問 → 問題を解くどころかコンテストにもほぼ出ていない.
  • 英語:TOEIC730点 → TOEICを受けていない
  • その他:機械学習コミケに出す → 機械学習◯、コミケ

2017年の感想

  • 割りと講義とかバイトとか遊び等で忙しくて,思うように動けなかった.
    • 気づいたら年末,年々年を取るのが早くなる
  • インターンにいくつか参加するとともに,比較的暇な学部3,4年生の内にもっと行くべきだったと思った.
    • 修士だと就活を視野に入れてインターンを選ばないといけないし,落ちた時に2回目のチャレンジができないため.
  • 学部生にやってきたことを使って,アウトプットをしていたなぁという感じ.
  • やりたいことを口にしていると協力してくれる人が結構いる.

2018年の目標

1~4月:研究と機械学習の勉強をメインに.

  • 機械学習は何かしらの成果物をブログに上げる.
  • 研究は海外学会発表に行く

5~8月:英語ガチ勢になりたい(夏に海外インターンとか行ってみたいので)

9~12月:研究のまとめとやりたい勉強.

Googleカレンダーを見ながら振り返り

1月

適当な学会に出す論文を書いていた.
あと,卒論も書いてたが,ほとんど前に書いたものを再利用したので,あんまやった気がしない.
卒論の発表にほとんど練習しないで望んだら,ぐだぐだ過ぎて怒られるかと思ったが,大丈夫だった.

そういえば,1~3月ぐらいまで36.8~37.5ぐらいの微熱が続いて辛かった.(医者に数回行ったが原因不明,恐らく副鼻腔炎
それとは別に顎のあたりにしこりがあって,微熱も続くし,死ぬんじゃないかと思った.(実際は,微熱とは関係なくガマ腫というらしい)

2月

毎週遊びの予定が入っているので,遊び呆けていた模様.(微熱が治らなかった原因の1つ)

大阪にも行った.夜行バス+微熱で死にそうだった.

3月

1月に出した論文に一応査読が付いていたので,直し.

先生のコネでF研究所で3週間のインターンシップ
内容は,詳しくはNDAで言えないが,仮想ネットワークの可視化してた.
知識0で行ったら,初日の説明会で知らない単語が無限に出てきてめちゃ焦ったが,割りとなんとかなった.まあまあ楽しかった.

3月末に卒業旅行で初の広島旅行に行った.
外国の方に「お前,日本人なのに広島も行ってないのかよ」みたいなこと言われたくなかったので,僕の希望で広島へ.
夜行バス+微熱で死にそうだった.

4月

何かをしてた形跡がない.3月まで疲れを癒やす1ヶ月.

5月

1月に投稿した奴のポスター発表のために北九州に行った(初めて本州以外の県に行った)
Yandex Algorithmの参加賞でTシャツ貰ってHappy:)

6~7月

インターンに数社落ちて悲しみにくれていた.
面接で落ちるの最高に精神に来る.

8月

コミケに初サークル参加.
友達4人と技術系記事の載った薄い本を書いた.僕はビットコインの仕組みについて書いてた(我ながら先見の明があると思う).
印刷所とか設営とか初めてなことだらけで大変だったけど,刷った30部が完売した時は感動だった.
冬コミも申し込んだけど,抽選漏れでした,残念!

9月

某社でインターン.やってきたことを評価してくれるし,かなり楽しかった.
初めて劇を見に行ったが,面白かった.

10~11月

アルバイトを新しく始めたら忙しくなってしまった.

DISCO presents Discovery Code Contestの本戦に出れた.
Ponanza開発者とプロ棋士の対談を聞きながら,もっと頑張らないといけないなと思っていた.

12月

学内でハッカソンを運営してた.小成功ぐらい.今後,大きくしていきたい.

Q-Learningで迷路を解く

はじめに

強くなるロボティック・ゲームプレイヤーの作り方 プレミアムブックス版 ~実践で学ぶ強化学習~

↑これを読みながら強化学習の基礎と雰囲気を学んでいるのですが,
読んでるだけで飽きてきたので,実際に実装してみました.
chainerRLとか使えば簡単にできるのだろうなと思いつつ,初めてなのでC++で適当に書きました.

Q-Learningとは?

詳しくは本を読むか,色々な人が解説記事を上げているのでそちらに.
ゼロからDeepまで学ぶ強化学習 - Qiita
強化学習で迷路を探索する - Qiita

方針

報酬 R(s_t,a_t)をゴールしたとき1,壁に移動したとき-1,その他0で設定.
探索する時の行動選択にε-greedyを用いていたのですが,上手く行かなかったため,
UCB1アルゴリズム*1を使って探索しました.

UCB1については下記リンク参照.
モンテカルロで二人ゲーム - ustimawのブログ

実装

実行環境
概要

競プロ形式で迷路を標準入力から読み込み.
高さH,幅Wの次の行から,各セルの情報が空白区切りで与えられる.(0:通路,1:壁,2:スタート,3:ゴール)

エピソード数(num_episodes=10000)の学習の後,1回テストが実行されます.

実行結果

テスト実行時の動画です.'x'が現在地を表しています.

Q-Learningの更新式についてメモ

説明できるほど理解できてないのですが一応.(中途半端かつ正確ではないです.)
状態 s_tの時行動 a_tを取った場合の価値関数 Q(s_t,a_t)がある.
 Q(s_t, a_t)を展開すると,期待報酬関数 Rと次ステップの価値関数 Q(s_{t+1},a_{t+1})の漸化式っぽくかける.

Q(s_t,a_t) = \sum γ^tR(s_t,a_t) = R(s_t,a_t) + γQ(s_{t+1},a_{t+1})


これを,Rイコールの式にすると,

R(s_t,a_t) = Q(s_t,a_t) - γQ(s_{t+1},a_{t+1})
となる.


報酬関数 R(s_t, a_t)を近似する関数 \hat{R}(s_t,a_t)と実際の報酬 r_tは,大体一致して欲しい.
そこで,誤差 \Delta R(s_t, a_t) \equiv \frac{1}{2} (r_t - \hat{R}(s_t,a_t))^2と定義し,これを最小化する.


最小化するように Q(s,a)を更新するために,TD法が提案されていて,これは大体勾配法.
TD法では, d = \frac{\partial \Delta R}{\partial \hat{Q}}として, \hat{Q}(s_t,a_t) = \hat{Q}(s_t,a_t) - \alpha dで更新.
 \alphaは学習率.


で, dは下式のように求まるので,
 d = \frac{\partial \Delta R}{\partial \hat{Q}} \propto -r + R(s,a)
近似価値関数は次の式で更新するといい感じになりそう.
 \hat{Q}(s_t,a_t) \leftarrow \hat{Q}(s,a) + \alpha (r_t - \hat{Q}(s_t,a_t) + \gamma \hat{Q}(s_{t+1},a_{t+1}))

(正確にはここまでのQには肩に政策関数 \pi が乗ります.)


Q-Leaningでは
 \hat{Q}(s_t,a_t) \leftarrow \hat{Q}(s,a) + \alpha (r_t - \hat{Q}(s_t,a_t) + \gamma \max_{a'}{\hat{Q}(s_{t+1},a'))}
で更新.

*1:雰囲気実装なので合ってない

IPアドレスを自動でGoogleスプレッドシートに書き込む(Windows10)

背景

学内や社内等のPCに接続したい時,IPアドレスが分からず困ることがしばしばあったので,*1
自動でIPアドレスGoogleスプレッドシートに書き込まれるようにしました.

構成

Windows 10 → Google Apps Script → Googleスプレッドシート
Google Apps Scriptが,Windows10からのGETに含まれるIPアドレスを受け取り,さらにGoogleスプレッドシートに書き込む

手順

サーバ側

まずは,GoogleスプレッドシートをGドライブから作成します.
この時,スプレッドシートのURLの{ここの文字列}部分がスプレッドシートのIDになっています.

https://docs.google.com/spreadsheets/d/{ここの文字列}/edit

次に,Google Apps Scriptを書いていきます.
Gドライブの右上の"新規"→"その他"→"Google Apps Script"で新規作成.

function doGet(e) {
  var id = '{スプレッドシートのID}';
  var sheet = SpreadsheetApp.openById(id).getSheetByName("シート1");
  var ipaddr = e.parameter.ip;
  sheet.getRange("A1").setValue(ipaddr);
}

上記コードでは,GETを受け取った時,"ip"に設定されているパラメータがスプレッドシートのA1セルにIPアドレスが書き込まれます.
そうしたら,"公開"→"ウェブアプリケーションとして導入"→"アプリケーションにアクセスできるユーザーを全員(匿名含む)に変更"→"更新"
として,WebAPIを公開します.

リモートPC側(Windows 10)

こっちがWindowsなので結構面倒くさかったです.
まず,IPアドレスをGETで送るbatファイルを作成しました.

set IPADDRPATH={batファイルがあるディレクトリ}\ipaddr.txt
ipconfig | find "IPv4" > %IPADDRPATH%
set /p myipaddr=<%IPADDRPATH%
curl {作成したWebアプリケーションのURL}?ip=%myipaddr:~38%

結構無駄ありそうですが,こんな感じで.
一度ipaddr.txtにipconfigからfindしたIPアドレスを入れ,そこから再度読み込んで"ip"のパラメータとしてAPIを叩いています.
最初に作成したスプレッドシートを確認すると,A1セルにIPアドレスが書き込まれていると思います.

後は,このbatファイルを定期的に実行するようにタスクスケジューラに登録します.
GUIからできるらしいのですが,上手くいかなかったのでコマンドプロンプトから設定.
ちなみに,/sc hourly /mo 6 で6時間に一回とかになるはず

schtasks /Create /tn "ipsender" /tr "{batファイルがあるディレクトリ}\ipsender.bat" /sc minute /mo 30

これで,30分に1回実行されます.ちなみに消す時はこう.

schtasks /Delete /tn "ipsender" 

感想

作ったもののあんまり学内PCにアクセスする機会がないし,
そもそもIPアドレスが滅多に変わらなくて悲しい.(ネットワーク整備みたいなのしたっぽいし,固定IPになってる節)

そのうち,学内/社内のWindows PCにリモートデスクトップ接続する話を書きます.

*1:DHCPで変わったり等々

ICPC国内予選 2017 G 迷宮を一周

問題

迷路がN*Mのグリッドで与えられる.('.'が通路,'#'は通行不可)
グリッド上の(0,0)地点をスタートとする.
スタート以外の3隅の宝物を回収してスタート地点に戻ってきたい.
しかし,一度通った通路は通れないとする.
https://storage.googleapis.com/icpcsec/icpc2017-domestic/contest/all_ja.html#section_G

考察

まず,宝物は右回りまたは左回りで回収する必要がある.
右下隅の宝物を最初に取ると,右上隅から左下隅への経路が消えるため.

できるだけ,端に沿ってに移動するのが最適そう(証明は知らないっ!)
下図のように塗って,移動経路があればOKみたいなことをした

各端について(上,右,下,左端の通路)
・端の'.'は通行可能
・”端”の'#'と8近傍で連結している'#'を列挙
・列挙した'#'の8近傍で'.'の通路は通行可能


f:id:utsubo_21:20170722102935p:plain

感想

本番では思いついていたのに,組みきれなかった.
悲しい(´・_・`)

#include <bits/stdc++.h>
using namespace std;

int N,M;
bool dijkstra(vector<string>& maze,char number,int sx,int sy,int gx,int gy){

  priority_queue<pair<int,pair<int,int>>> pq;
  vector<vector<int>> dists(N,vector<int>(M,1e9));
  dists[sy][sx] = 0;
  pq.push(make_pair( 0, make_pair(sx,sy)));  
  vector<int> dx = {0,-1,0,1};
  vector<int> dy = {-1,0,1,0};
  maze[gy][gx] = number;

  while(!pq.empty()){
    pair<int,int> p;
    int cost;
    tie(cost,p) = pq.top();pq.pop();
    int x,y;
    tie(x,y) = p;
    if(x == gx && y == gy)return true;
    for(int i=0;i<4;i++){
      int nx = x + dx[i],ny = y + dy[i];
      if(nx < 0 || ny < 0 || nx >= M || ny >= N)continue;
      if(maze[ny][nx] != number)continue;
      int newcost = -cost + 1;
      if(newcost >= dists[ny][nx])continue;
      dists[ny][nx] = newcost;
      pq.push(make_pair( -newcost, make_pair(nx,ny)));
    }
  }
  return false;
}

void fillgrid(vector<string>& maze,char number,int sx,int sy){
  queue<pair<int,int>> q;
  if(number == '1'){
    for(int i=0;i<M;i++){
      if(maze[0][i] == '#')
        q.push(make_pair(i,0));
      else if(maze[0][i] == '.')
        maze[0][i] = number;
    }
  }else if(number == '2'){
    for(int i=0;i<N;i++){
      if(maze[i][M-1] == '#')
        q.push(make_pair(M-1,i));
      else if(maze[i][M-1] == '.')
        maze[i][M-1] = number;
    }
  }else if(number == '3'){
    for(int i=0;i<M;i++){
      if(maze[N-1][i] == '#')
        q.push(make_pair(i,N-1));
      else if(maze[N-1][i] == '.')
        maze[N-1][i] = number;
    }
  }else{
    for(int i=0;i<N;i++){
      if(maze[i][0] == '#')
        q.push(make_pair(0,i));
      else if(maze[i][0] == '.')
        maze[i][0] = number;
    }
  }
  vector<vector<int>> used(N,vector<int>(M,0));
  int dx[] = {0,1,-1,-1,1,0,1,-1};
  int dy[] = {-1,-1,-1,0,0,1,1,1};
  while(!q.empty()){
    int x,y;
    tie(x,y) = q.front();q.pop();
    used[y][x] = 1;
    for(int i=0;i<8;i++){
      int nx = x + dx[i],ny = y + dy[i];
      if(nx < 0 || ny < 0 || nx >= M || ny >= N)continue;
      if(used[ny][nx])continue;
      if(maze[ny][nx] == '.'){
        maze[ny][nx] = number;
      }else if(maze[ny][nx] == '#'){
        used[ny][nx] = 1;
        q.push(make_pair(nx,ny));
      }
    }
  }
}

bool solve(){
  cin >> N >> M;
  if(N+M == 0)return false;
  vector<string> maze(N);
  for(int i=0;i<N;i++){
    cin >> maze[i];
  }
  int vsx[] = {0,M-1,M-1,0,0};
  int vsy[] = {0,0,N-1,N-1,0};
  for(int i=0;i<4;i++){
    int sx = vsx[i],sy = vsy[i];
    int gx = vsx[i+1],gy = vsy[i+1];
    fillgrid(maze,'1'+i,sx,sy);
    // for(int i=0;i<N;i++)cerr << maze[i] << endl;

    if(!dijkstra(maze,'1'+i,sx,sy,gx,gy)){
      cout << "NO" << endl;
      return true;
    }
  }
  cout << "YES" << endl;
  return true;
}

int main(void) {
  while(solve()){}
  return 0;
}

ICPC国内予選参加記 2017

参加まで

忙しいし出なくて良いかーと思っていたのですが*1,先輩の後押しで参加することに.
今年で3回目の参加だったので,登録まではバタバタせずにすみました.(監督・コーチありがとうございました!)

メンバーは去年と同じ同期のメンバーが1人と研究室の後輩1人引き連れて参加しました.
締切ギリギリで参加を決めたので,一度だけ通し練習をして本番へ.

当日

プリンタの不調で問題が10分ぐらい印刷できず,テンパる(ちゃんと印刷確認しましょう)

落ち着いた後は,後輩にA,同期にBを任せて,自分はCを取り組む.

Cは去年,一昨年と面倒くさい実装だったのですが,今年は簡単で余裕があったので,Aのバグ取りを一緒してました.

CよりBの問題の方がパッと見て面倒臭そうだったので,先にPCを使うことに.
バグらせながらゆるゆるとAC.

Bを任せるのが結構不安だったので,問題を読みながらペアプロ
想定よりだいぶ早く解けて(自分が解いてたら焦ってやばかったかも),この時点ではかなり良い順位に.

Dをフローとかじゃん?しばらくやった後,Gも外壁の近くを良い感じに辿るだけでいけそうと思って実装していました.
Gの実装をバグらせてる間にタイムアップ.

69位でした.国内予選落ちです.

感想

3年もやってて4問解けないの情けなさすぎて泣いてました.
Dの場合分けに気づけないの本当に悔しかったです.

Gの実装も上手く行けばワンチャンあったかもしれないのに,それも間に合わなかったので,完全に練習不足でした.

僕は今年で引退ですが,後輩が引き続き参加して,うちの大学も常連校ぐらいまで成長してほしいと思っています.
とりあえず,宣伝・指導をしないと来年から消えそうなので頑張ります.

反省

D問題解きました.Gもそのうち解きます.

#include <bits/stdc++.h>
using namespace std;

// n(<=23)が小さいとき,全探索
int nsmall(int n,int m,const vector<bitset<501>>& bits){
  int ret = 0;  
  for(int i=0;i<(1<<n);i++) {
    bitset<501> used;
    int cnt = 0;
    for(int j=0;j<n;j++){
      if((i>>j) & 1) {
        used = used ^ bits[j];
        cnt++;
      }
    }
    if(used.none()){
      ret = max(ret,cnt);
    }
  }
  return ret;
}
// mが小さいとき,レシピの状態でDP
vector<vector<int>> dp;
int msmall(int n,const int N,int used,const vector<int>& b){
  if(n == N){
    if(used == 0)return 0;
    else return -1e9;
  }
  if(dp[n][used] != -1)
    return dp[n][used];

  return dp[n][used] = max(msmall(n+1, N, used ^ b[n], b) + 1,
             msmall(n+1, N, used, b));
}

bool solve(){
  int n,m;
  cin >> n >> m;
  if(n == 0 && m == 0)
    return false;
  vector<string> vs(n);
  for(int i=0;i<n;i++){
    cin >> vs[i];
  }
  vector<bitset<501>> bits(n);
  vector<int> b(n);
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      if(vs[i][j] == '1'){
        bits[i].set(j);
        b[i] |= (1<<j);
      }
    }
  }
  if(n <= 23){
    cerr << "n:" << n << endl;
    cout << nsmall(n,m,bits) << endl;
  }else{
    cerr << "m:" << m << endl;
    dp = vector<vector<int>>(n,vector<int>((1<<m),-1));
    cout << msmall(0,n,0,b) << endl;
  }
  return true;
}

int main(void) {
  while(solve()){}
  return 0;
}

https://ideone.com/j1M8ea

*1:去年も同じようなことを言っていましたが今年は本当に