TopCoderの設定
TopCoderについての設定や問題の解き方についてのメモです。OSはWindows10です。
登録方法
TopCoderにアクセスし右上の「LOG IN」をクリック、「COMMUNITY LOG IN」をクリックし画面下中央の「join now」から登録します。
名前、国、ユーザー名、メールアドレス、パスワードを入力します。入力したメールアドレスにメールが送られてくるため、メールの認証を行います。
applet
ダウンロード
TopCoderではWeb ArenaかJavaAppletのどちらかを用いて問題の閲覧や提出を行います。ここではapplet版について書きます。TopCoderにログインし、上部中央の「learn」から「Competive programing」をクリックします。「launch appret arena」をクリックするとappletのダウンロードが始まります。
セキュリティ例外
セキュリティ設定によってブロックされたアプリケーションというエラーが表示された場合、TopCoderのAppletを例外に設定する必要があります。スタートメニューから「Java」→「Javaの構成」としてJavaコントロールパネルを表示します。セキュリティタブの例外サイト・リストに「http://www.topcoder.com」を追加することでセキュリティ例外に追加できます。
設定
ここまでくればappletを実行できるはずです。appletを起動しIDとパスワードを入力してログインしてください。まずはフォントサイズの設定をします。画面上部のタブの左から3つめの「Option」から一番下の「Setup User Preferences」をクリックします。
「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 イカサマなサイコロ
トポロジカルソート
トポロジカルソートとは
閉路がない有向グラフの各有向辺が順方向になるようにソートすることをトポロジカルソートと呼びます。DAG(有向無閉路グラフ)にのみ行うことができ、トポロジカルソートが行えればそのグラフはDAGであるといえます。
トポロジカルソートができる⇔DAGである
トポロジカルソート | グラフ | Aizu Online Judge
トポロジカルソートのアルゴリズム
入次数
入次数が0の頂点があれば、その頂点をソート後の結果に追加しその頂点と隣接した頂点の入次数をマイナス1する。これを入次数が0の頂点がなくなるまで繰り返すことでトポロジカルソートをすることができます。計算量はO(V+E)です。
有向非巡回グラフ(DAG)をトポロジカルソートする - マツシタのお勉強メモ
トポロジカルソートした結果の数列が何通りあるか
bitDPでできます。
D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder
ABC041D - ferinの競プロ帳
閉路検出
トポロジカルソートを用いて有向グラフの閉路検出をできます。トポロジカルソートができればDAGであり閉路が存在しません。逆に閉路が存在すればトポロジカルソートは不可能です。入次数のコードで ans.size() == v であればトポロジカルソートができた、そうでなければできなかったと判定することができます。
ABC015-D問題
ABC008-D問題
蟻本で似た問題(P121, Bribe the Prisoners)を見たことがあったので同じように考えて実装しました。機械を動かしたあとその機械で取った金塊で分断された場所は互いに関係しない独立した場所です。なので、ある機械を動かしたときに得られる金塊の数は
(1)機械を動かして得られる金塊
(2)分断されたそれぞれのエリアで得られる金塊
の和になります。それぞれのエリアについて再帰的に考えていけば得られる最大の金塊数を求められます。dp[sx][sy][fx][fy]を左上を(sx, sy)、右下を(fx, fy)としたエリアで得られる金塊としてメモ化再帰で実装しました。境界条件の部分は番兵法つかったほうが良さそう…
範囲内を全て探索しているところを機械がある点に絞れば100点の制約でも間に合いました。
ABC037-D問題
ABC038-D問題
解説読んでもわからなかったBainary Indexed Tree(BIT)ってなんだよ!ってのとソートの方法を指定する方法についてのメモ。
BITについては以下のスライドが分かりやすかったです。和ではなくその区間の最大値を保存することである区間の最大値はO(logN)で求められます。BITは1からaまでの区間についての情報を保持していますが、区間[a, b]について考えたいならセグメントツリーのほうが便利そうです。
http://hos.ac/slides/20140319_bit.pdf
hについて昇順でhが等しかったらwの降順になるようにするソートが必要です。以下のサイトを参考にソートの比較用の関数をつくることで実装しました。他にも構造体で > を定義することで行ったり、ラムダ式を用いる方法でもできそうです。
C++(ソートの補足) - アルゴリズム講習会