ferinの競プロ帳

競プロについてのメモ

ARC022 B問題-細長いお菓子

arc022.contest.atcoder.jp

重複した数が存在しない最大の領域を求める問題です。重複した数が存在するかどうかの判定ををunordered_setで行いました。unordered系のデータ構造はじめて使ったんですが衝突さえしなければO(1)でできるの便利ですね… 解いているときに開かれていたCFでunorderedを殺すテストケースがあったそうなので最初にメモリをちゃんと確保しておくように気をつけたい。
バケツサイズを変えたりや挿入する値のXORを取る必要があるらしい。 
nitcoder000.hatenablog.com


TopCoderの設定


TopCoderについての設定や問題の解き方についてのメモです。OSはWindows10です。

登録方法

 TopCoderにアクセスし右上の「LOG IN」をクリック、「COMMUNITY LOG IN」をクリックし画面下中央の「join now」から登録します。
f:id:ferin_tech:20170222230210p:plain
名前、国、ユーザー名、メールアドレス、パスワードを入力します。入力したメールアドレスにメールが送られてくるため、メールの認証を行います。

applet

ダウンロード

 TopCoderではWeb ArenaかJavaAppletのどちらかを用いて問題の閲覧や提出を行います。ここではapplet版について書きます。TopCoderにログインし、上部中央の「learn」から「Competive programing」をクリックします。「launch appret arena」をクリックするとappletのダウンロードが始まります。
f:id:ferin_tech:20170222230242p:plain
f:id:ferin_tech:20170222230310p:plain

Javaの更新

 ダウンロードしたAppletを実行した際、Javaのバージョンが最新でない場合はJavaのインストールが必要だと言われます。画面の手順通りにJavaの更新をしましょう。

セキュリティ例外

 セキュリティ設定によってブロックされたアプリケーションというエラーが表示された場合、TopCoderのAppletを例外に設定する必要があります。スタートメニューから「Java」→「Javaの構成」としてJavaコントロールパネルを表示します。セキュリティタブの例外サイト・リストに「http://www.topcoder.com」を追加することでセキュリティ例外に追加できます。

設定

 ここまでくればappletを実行できるはずです。appletを起動しIDとパスワードを入力してログインしてください。まずはフォントサイズの設定をします。画面上部のタブの左から3つめの「Option」から一番下の「Setup User Preferences」をクリックします。
f:id:ferin_tech:20170222230406p:plain
「Editors」、「Problems/Messages」、「Challenge」、「Additional Fonts」タブにsizeの設定があるので適当な大きさに設定しましょう。(自分は18です。)次にデフォルトの言語を指定しましょう。「Editors」タブの「Default Language」で使う言語を指定します。

プラグインの導入

何も設定していない状態だとTopCoderのappletに付属しているエディタでコーディングすることになります。問題に沿ったテンプレートの作成やサンプルのローカルでの実行、普段のエディタでのコーディングをできるようにプラグインを導入しましょう。
以下のページから「CodeProcessor」「TZTester」「FileEdit」をダウンロードします。
About TopCoder - Overview
「Option」タブから「Editor」を選択します。Common ClassPathに「TZTester.jar」「FileEdit.jar」のパスを追加します。
Addボタンを押してダイアログに以下のように入力します。
 Name - CodeProcessor
 EntryPoint - codeprocessor.EntryPoint
 ClassPath - CodeProcessor.jarのパス(Browseから選択)
CodeProcessorをクリックし、Configureを押して設定を開きます。
画面上部の「Editor EntryPoint」にfileedit.EntryPointと入力して「Configure」をクリックします。
画面上部の「Enter directory to read/write problems to」にソースを置きたいファイルパスを書きます。
問題を開くとこの問題にあったソースファイルがこのパスに生成されます。普段競プロの問題のソースコードをおいているフォルダを選択しましょう。
「Code Template」タブに切り替え、Languageを使用する言語に変更しテンプレートを編集し、「Save」ボタンをクリックしてください。include文やREPマクロなどを使いたい場合はこのテンプレートを編集します。
「CodeProcessor Script」に tangentz.TZTester と書き「Verify」をクリックします。
一回appletを再起動するとこのプラグインが反映されます。

practice(過去問)

画面上部の「Practice Room」タブからSRMを選択し、解きたい問題セットを選択してください。選択すると問題のページに移動します。「Select one」から解く問題を選択すると問題が開かれます。問題を開くとプラグインで指定したパスにテンプレートとなるファイルが生成されます。エディターでこのファイルを開き、コーディングし、ローカルで実行することでサンプルが実行され、正解か不正解かが表示されます。提出する際は画面下部の「Compile」をクリックし「Submit」をクリックすることで提出できます。上のタブの「practice option」を選択して「Run System Test」をクリックすると、そのコードに対するジャッジがされます。

TopCoder Arenaで「セキュリティ設定によってブロックされたアプリケーション」の解決方法 - tshitaの備忘録Ⅱ
TopCoderでCodeProcessor+TZTester+FileEdit - Gulfweed

yukicoder No.58 イカサマなサイコロ

No.58 イカサマなサイコロ - yukicoder

モンテカルロ法をはじめて使ったのでその記録です。
モンテカルロ法とは乱数を用いてシミュレーションを行う方法です。この問題では次郎君の試行として1から6までの範囲の乱数をN回求め、太郎君の試行として4から6までの範囲の乱数をK回、1から6までの範囲の乱数をN-K回求めます。これを10^6回試行し、(太郎君が勝った回数)/(試行回数 = 10^6)を計算することで答えを求めました。

トポロジカルソート

トポロジカルソートとは

閉路がない有向グラフの各有向辺が順方向になるようにソートすることをトポロジカルソートと呼びます。DAG(有向無閉路グラフ)にのみ行うことができ、トポロジカルソートが行えればそのグラフはDAGであるといえます。
トポロジカルソートができる⇔DAGである
トポロジカルソート | グラフ | Aizu Online Judge

トポロジカルソートのアルゴリズム

入次数

入次数が0の頂点があれば、その頂点をソート後の結果に追加しその頂点と隣接した頂点の入次数をマイナス1する。これを入次数が0の頂点がなくなるまで繰り返すことでトポロジカルソートをすることができます。計算量はO(V+E)です。
有向非巡回グラフ(DAG)をトポロジカルソートする - マツシタのお勉強メモ


DFS

全ての点から深さ優先探索を行い、その帰りがけ順がトポロジカルソートの結果になります。計算量はO(V+E)です。
Topological sort


トポロジカルソートした結果の数列が何通りあるか

bitDPでできます。
D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder
ABC041D - ferinの競プロ帳

閉路検出

トポロジカルソートを用いて有向グラフの閉路検出をできます。トポロジカルソートができればDAGであり閉路が存在しません。逆に閉路が存在すればトポロジカルソートは不可能です。入次数のコードで ans.size() == v であればトポロジカルソートができた、そうでなければできなかったと判定することができます。

ABC015-D問題

abc015.contest.atcoder.jp

ナップザック問題でk個のみつかえるという制約を加えたような問題です。ナップザック問題で持つ状態に加えて今までに使用したスクリーンショットの枚数を状態として持つことで解けます。まずメモ化再帰で実装しました。

次に動的計画法で実装しました。

ABC008-D問題

abc008.contest.atcoder.jp

 蟻本で似た問題(P121, Bribe the Prisoners)を見たことがあったので同じように考えて実装しました。機械を動かしたあとその機械で取った金塊で分断された場所は互いに関係しない独立した場所です。なので、ある機械を動かしたときに得られる金塊の数は
(1)機械を動かして得られる金塊
(2)分断されたそれぞれのエリアで得られる金塊
の和になります。それぞれのエリアについて再帰的に考えていけば得られる最大の金塊数を求められます。dp[sx][sy][fx][fy]を左上を(sx, sy)、右下を(fx, fy)としたエリアで得られる金塊としてメモ化再帰で実装しました。境界条件の部分は番兵法つかったほうが良さそう…

 範囲内を全て探索しているところを機械がある点に絞れば100点の制約でも間に合いました。