Procon29に参加しました

こんにちは、naoppyです。明石高専の競技部門として高専プロコン29に参加しました。

先に結果から書きますが、予選はP6ブロック1位通過できました。

決勝トーナメントは一回戦で敗退しました。惜しくも勝てなかった！(>_<)

大会までの流れ

5月

校内で競技部門に出たいチームが僕らを含め2チームいたので、校内予選に。無事突破。

メンバーは僕(2年)、ecasdqina(2年)、dawning(1年)の3人。それぞれGUI担当、Solver担当、書類担当ということに。(ｺｺ重要)

この頃GitHubにリポジトリを作った。

7月,8月

少しだけ開発をした。レポーヨに追われて迫真のコミットメッセージなのが当時の忙しさを物語っている。

9月

夏休み真っ只中の9月、当然開発は進みますよね？？？いいえ。宿題多すぎて一ヶ月で4日しか開発してません。

大会は10/27日なのに、10月まで何もしてなくない？

そうだよ(震え声)

10月

10/10にSolver以外は一応完成。

10/17には「あれ...? Solver担当からの進捗報告がないな...(フラグ)。一応人力の為にスコアも表示するか」ということでスコア表示実装。

10/26にSolver担当の死を確認し、人力でなんとかなるようにGUIを大幅変更(詳細は後で)

いざ、大会へ～

大会での流れと自分達のプログラム

1日目

僕が司令塔なのは決めていましたが、朝にエージェントへの支持伝達方法を考えて連絡。練習とかはなかった。

練習試合はあのWA_TLEさんのいる北九州高専。そこで

• QRコードの読み取りに手こずると死ぬ
• 敵のエージェントの動作を入力する時間が無い
• トランプで支持を出すのが時間が無くて間に合わない

という3つのことが判明。

QRコードを読むのに2,3ターン使うと、敵の動きが入力できないので当然メインサイクル(自分の行動決定→指示→敵行動入力)が回せない。→人力へ。

練習試合の後半から指差しでエージェントに指示し始める。事前に示し合わせていないのにもかかわらず、めっちゃ伝わる。

ぶっちゃけトランプより早くて正確。トランプいらんやんけ。

そして予選トーナメントへ。

お待たせしました、GUIです。

入力

起動時

敵位置をクリックで入力するとSolverが走って右側に動く方向が表示される

敵の行動をクリックで入力(画像省略)

もう一度Solveを押すと盤面が進んでSolverが走る、以下繰り返し。

ですが、このGUI、練習試合で使えませんでした。

というのは、前述の通り、敵の行動を入力するのは忙しくて不可能だからです。

そのため、Moveボタン(Editモード)によって「動いた結果を入力させる」という方法に予選では切り替えました。

クリックでタイルの色塗り、ドラック＆ドロップでエージェントの移動。

こんな感じで自分の望む盤面を作ってSolverの動きを見るために開発したんですけど、思わぬところで役に立った...

これにより、QRコードの読み取りが遅れたとしても、一瞬で現在の盤面を作成し、スコア計算をしたりSolverを走らせることができるようになりました。

スクリーンに現在のターン数が書いてあったので、ターン数がわからないデメリットは消えました。

やったね！これで戦えるよ！

ところが、Solver担当が作ったSolverが弱すぎて、Solverは人間の脳になりました。(ここ爆笑ポイント)

人間の脳は普通に強くて、予選通過しました。えぇ...。

2日目

前日の反省を生かし、舞台に対して左のチームが青色、右のチームが赤色になるようにGUIを変更しました。

今までは味方が青、としていましたが、現実と違うと頭がバグることを1日目で学んだからです。

そして、決勝トーナメント第一試合

分岐を逆に書いていて現実の色と逆になっていました。頭(Solver)がバグって死亡

夜中に開発するとチェックゆるゆるなのでダメですね...。

Solverについての考察

まず弊チームで候補に出たのは

• ビームサーチ
• モンテカルロ木探索
• 焼きなまし
• 機械学習

ぐらいでした。 このゲームのルールは

1. 敵と味方が同時に動く
2. 終局までのターン数、フィールドのサイズ、各マスの点数、エージェント4人の初期配置が試合までわからない。
3. 1によってエージェントの行動によっては衝突が発生する。
4. 最終的な点数はタイル点＋領域点（囲った点）で決められるということ。

という特徴を持っています。

オリジナルゲームなのでこれまでの対戦事例などはなく、特徴2のことも考えて機械学習は上手くいかないと考えました。

また、焼きなましも実装してからわかった(らしい)のですが、特徴3によって衝突が発生した場合に弱く、あまり強くなりませんでした。

更に、特徴4によって、ビームサーチはそのアルゴリズムの特徴から、長期的な目で「囲う」ということができず、弱いのではないかと思いました。

モンテカルロ木探索は今回のような厳しい時間制限の中でも、効率的に深くまで探索し、またいつ探索を打ち切ってもその時点での最適解がだせるという特徴から、このゲームに向いていると思いました。

まあ実装間に合わなかったんですけどね。

実装したチームは感想教えてくれると嬉しいです。

運営について

最初にQRコードの形式について説明したpdf、唯一載っていたQRコードサンプルが既にそのpdfの説明と矛盾していて「やべーわこれ」と思ったけど間違ってなかった。やばかった。

最初は競技ターン数は60~80ターン、1ターンにかける時間は5~10秒と非常に厳しいものだったが、ターン数は40~80、1ターンの時間は10~20秒に。なんでもっと早く気がつかなかった。絶対運営がやってみて初めてこんな時間じゃできないことに気づいたやつじゃん。

ソースコードはGitHubのリンクで提出することもできます！とか言っておきながらprivateリポジトリをどう提出するのか一切情報はなく、それについての情報を締め切り1日前に公式サイトではなくfacebookで公開するとかいうクレイジームーヴをかましてきた。こいつはやべぇや。

会場のwifi環境は良かった。そのせいか毎年恒例プロコン会場SSID大喜利大会が無かった。悲しい。

予選にて競技フィールドが一方のチームに有利になっていたため再試合。運営はちゃんとルール把握しような。

再試合のこともあってスケジュールは1時間半以上遅れており、全ての試合のターン数が40ターンに。ランダムだからSolver作成に苦しんでるのに結局全部同じになるのかよ。

実はルールには、エージェントが示した方向を無視して移動すると、そのターンの全ての変更は無効になり、ターンだけ進む。というものがあった。つまり貪欲法でスコアが高いものを取っていき、自分達の点が相手の点を超えた瞬間からエージェントが変な行動をすることで必ず勝てる。というものがある。これをするチームは善意により現れなかったが...現れていたらどれだけ悲惨なことになったかは言うまでもない。プログラミングコンテストとは...

結論：運営・ルール共にひどいものだった。

まとめ

阿波踊りっていいですね。

プロジェクトマネジメントが一番大事。

Solver担当君、進捗報告はちゃんとしような！💥

CyberRebeatCTF Write-up

結果：1747点を取って69位でした

以下、解答状況

ぼっち参加にしては健闘したと思いますが、自明問しか解けず実力の無さを実感しました。

解いた問題の解法など載せます

Crypto1:Rotation

与えられたものP4P6S{9RN4RUNPXR45}に対してフラグの形式がCRCTF{}だと考えると、0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZを13文字ずらしたものだとわかります。

Misc1:Readme

以下の画像が与えられます。

日本人以外が読めるフォントとして有名なやつだった気がします。

頑張って読みましょう。

Recon1:Tweet

問題文が読めれば解けます

Recon2:CyberRebeatScripts

GitHub - ennach/CyberRebeatScripts: CyberRebeat's script files

ここにアクセスすると、delete FLAGと書いてあるのでコミット履歴を遡ると文章の中にFLAGが平文であります。

Recon3:ChangeHistory

GitHub - ennach/ChangeHistory: CyberRebeat's scripts 2

ここにアクセスして、前問のようにコミット履歴を漁りますが、見つかりません。

issueを覗くと、Closed Issueが...

FLAGがあるコミットのハッシュがわかったので、URLを

https://github.com/ennach/ChangeHistory/commit/c476614bc439fe1910e494422b3aa207b776d486

のように構築してアクセスすると解けます。

Stegano1:Secret.pdf

隠れているところをCtrl+Cして張り付けるとFLAGがでてきます。

Stegano2:Alpha

画像が与えられるのですが、問題名からアルファ値が怪しいなとなります。

適当なお絵描きソフトの保存画面でアルファ値を全部消したところ、うっすらと中央に文字が...

これでアルファ値があやしいことはわかったのですが、鮮明に見えないので、

汎用ファイルアナライザ「青い空を見上げればいつもそこに白い猫」様よりツールを使わせていただきました。

アルファチャンネルのビット0抽出で解けました。

Trivia1:Monero

coinhiveです。

Trivia2:Crossword

ただのクロスワードなので埋めるだけです。

縦書き文字の簡単な挿入、文字幅の細かい調整などができるお絵かきソフトを使いましょう。

Web1:White page

visibility:hiddenを消しましょう。

Web2:Let's Tweet!

素直にツイートしてそのリンクを送りましょう。本当にやるだけ。

感想

Programingの1はevalに突っ込むだけ、2もやるだけなのですが、サーバーとのやりとりをプログラム中でする方法がわからず解けませんでした。悔しい。

CTFサーバとの自動対話 - nkhrlab~

ここを参考にやってみればいいらしい。

BinaryとCryptoが難しい、なんもわからなくて自分が魚であることを自覚した。

ソロは寂しいですが、全完したときのかっこよさがあるので頑張りたい。

これくらいの難易度のCTFは楽しいです...。

ABC097-C

今回はこの問題 C - K-th Substring の解説をしていこうと思います

問題概要

文字列sの異なる部分文字列のうち、辞書順でK番目に小さいものを出力せよ

この問題文は殆どが部分文字列や辞書順の定義についてで、大事なのは最初の2文です。

この問題文を見た時に、まず「異なる部分文字列」というところから、Setの使用を考えましょう。

Java以外の言語には、配列から重複部分を取り除く操作が用意されていることもあるみたいですが、この問題でそれを使うメリットはありません。

常に重複がない状態の方が扱いやすいからです。

制約

• 文字列長は最大3000
• Kは1~5

明らかにKが小さいです。ここが怪しいと気づければいいですね。

読み飛ばして爆死はやめましょう

解法までの道のり(200点)

異なる文字列→Set、辞書順→Sort　より、TreeSetを使う！とすぐに考えられればいいですね。

まず問題を愚直にやってみることを考えます。

部分文字列の始点をi、終点をjとおきます。

二重forで全て列挙してTreeSetに入れて、K番目を取り出して出力。

これで200点は取れました。

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    int k = sc.nextInt();
    TreeSet<String> set = new TreeSet<>();
    for(int i = 0; i < s.length(); i++) {
        for(int j = i; j < s.length(); j++) {
            set.add(s.substring(i,j+1));
        }
    }
    set.stream().skip(k-1).findFirst().ifPresent(System.out::println);
}

解法までの道のり(300点)

愚直にやると、列挙にO(N²)、TreeSetへの挿入にO(logN)、内部での文字列比較にO(N)なので、O(N^3logN)でTLEします。

制約を考えると、Kがとても小さい値だということを利用できないか考えます。

重要なことですが、計算量を落とすためには

• 探索する範囲を小さくする
• 探索する方法を改善する

という2パターンがあると思っています。これを頭に置いて、考えていきましょう。

Kは最大でも5です、すると、辞書順の定義より解は最大でも5文字だということがわかります。

どういうことかというと、ABCDEFという部分文字列があるのであれば、A,AB,ABC,ABCD,ABCDEという部分文字列も当然あります。

これらを辞書順に並べると、A<AB<ABC<ABCD<ABCDE<ABCDEFとなるので、5文字を超えると辞書順で必ず6番目以降になるので、制約より解ではありません。

これで探索の範囲がぐっと狭まりました。

自分で試してみたところ、これでACしました。

for(int j = i; j < s.length(); j++)

この部分を

for(int j = i, x = 0; j < s.length() && x < 5; j++, x++)

こう変えるだけです。

結論

• 制約をよく見ましょう
• 異なる、辞書順などキーワードからすぐに使うデータ構造などを考える
• 辞書順などの場合、自分で比較関数を作らない、ライブラリの既存のソート関数で問題ない

自分はさらに、一文字目がaの文字列から見ていくなどの高速化をしようとしましたが、結局意味はありませんでした。

"これくらいなら通る"という計算量の推定がまだまだ甘く、無駄な実装に時間を取られてしまったので反省です。

Javaでの二分探索、lower_boundとupper_boundの実装

こんにちは、naoppyです。 AtCoderでこの問題 C - Snuke Festival を解いているときに、Javaの二分探索が能力不足だと感じた為、自作することにしました。

Javaの二分探索

Collections (Java Platform SE 8) これを見ればわかるのですが、Javaの二分探索は引数にlist、key、Comparatorをとります。

戻り値はintで、見つかった場合はkeyのインデックス（複数のkeyがリストに含まれている場合、どれが返るかは保障されない）

見つからなければ(-(挿入ポイント) - 1)が返ります。

(-(挿入ポイント) - 1)、これはどういうことかというと、見つからなければ必ず戻り値は0未満、負数になるので、見つかったかどうかがわかります。

ここから挿入ポイントを復元するには逆の操作、(-(戻り値+1))をしてやればいいです。

もう少し考えてみましょう。1足してマイナスにする＝1足して2の補数を取る＝1足してbit反転してから1を足す＝bit反転だけでいいことになります。

よって(-(挿入ポイント) - 1)から挿入ポイントを得るには~value（~はbit反転）でいいことがわかります。

lower_bound、upper_boundとは

C++のstd::lower_bound、std::upper_boundのことです。 lower_bound関数は指定した値以上の要素が最初に現れる位置を返し、upper_bound関数は指定した値より大きいの要素が最初に現れる位置を返します。

実装の方針としては、二分探索の引数の3番目、Comparatorを自分でうまくかくことで、比較的簡単に書こうと思います。

ラムダ式を使うことでさらに簡単に書けます。

実装

まず、Comparatorだけの実装をお見せします。

Comparator<Integer> lower = (x, y) -> x.compareTo(y) >= 0 ? 1 : -1;
Comparator<Integer> upper = (x, y) -> x.compareTo(y) > 0 ? 1 : -1;

これをCollections.binarySearch(list, key, Comparator)の第3引数にわたしてあげれば、それぞれlower_bound、upper_boundになるわけです。

ですが、このComparatorを渡したbinarySearchは必ず負数を返すことになります。よって値が存在したかどうかはわかりません。

戻り値は必ず~を付けてbit反転しましょう。

使用例

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class binarySearch {
    final static int[] array = { 2, 2, 3, 4, 4, 4, 6, 6 };
    final static List<Integer> list = int2List(array);

    public static void main(String[] args) {
        //lower_bound
        int lowerResult = ~Collections.binarySearch(list, 4, (x, y) -> x.compareTo(y) >= 0 ? 1 : -1);
        System.out.println(lowerResult);// => 3
        //upper_bound
        int upperResult = ~Collections.binarySearch(list, 4, (x, y) -> x.compareTo(y) > 0 ? 1 : -1);
        System.out.println(upperResult);// => 6
    }

    //int配列をList<Integer>に変換するヘルパーメソッド
    static List<Integer> int2List(int[] arr) {
        List<Integer> list = new ArrayList<>();
        for (int i : arr) {
            list.add(i);
        }
        Collections.sort(list);
        return list;
    }
}

最後に

• ~が見にくい。見落としやすくバグを生む危険がある。

• binarySearchの引数に直接ラムダ式を渡すのは、可読性の面から良くない。 Comparatorを作って、それを渡す方が良い。

• 値の存在を確認するのは、普通のbinarySearchを使って戻り値が正かどうかを見るしかない。

など、気を付けるべき点がいくつかある。

それなりに綺麗にかけたので満足。

AtCoderで水色になるまでにやったこと

naoppyです。4/21にAtCoderで水色になることが出来ました。 一つの節目として、やってきたこととかをまとめます。

レート変移

これを見てわかるのは、まあ僕に特別な才能や強い考察力がないことぐらいでしょう。 31回も参加してます。

水色時点での自分

実力と言っても色々パラメーターがあるので、難しいですが、僕のスペックを並べます。

• プログラミング歴1年、Java使い
• 競プロ歴は始めたのが去年(2017)の7月中旬、それなりに本気でやり始めたのが12月ぐらいです
• 1月ごろに300点問題は完全に安定、水色になった時点で400点が半分解けるぐらいの実力

自己紹介かよ

使えるアルゴリズムとテク

• 一次元累積和
• エラトステネスの篩
• 最小公倍数と最大公約数
• bit全探索
• BFS
• DFS
• 二分探索
• UnionFind
• 重み付きUnionFind
• ワーシャルフロイド
• ダイクストラ
• ベルマンフォード
• nCr

これだけです、こうして見ると少ないですね。 僕は何をしていたんだ

ちなみにDPはできません！！！DPできなくても水色にはなれます。

ただDPの考え方は知っておくべきかもしれないです。

Twitterがやめられない

何度ツイ禁しようとしても辞められません。 ひたすらに時間が吸われます。

結局ツイ廃状態のまま水色になれましたが、青になるにはそれなりにTwitterから離れた方がいいのは自明です。

精進方法

AtCoderProblemsで過去問を解く

誰もが使っているであろう AtCoder Problems

水色になった時は殆どABCしか埋めていませんでした。

ABCのCは80%、Dは23%ほど埋めていました。

TwitterのDMで優しい人に聞きまくる

普通に迷惑なのですが、優しい方に詰まっている問題の考察過程などを教えていただきました。 感謝しかありません。

まあこんな具体的なこと書いても誰の参考にもならないのでまとめると、優しい人(そこら中にいるはず)に特に考察過程を聞きましょう。

考察力は自分ではなかなか伸ばしにくいスキルです、精進への近道だと思います。考察力は大事です。

チーター本を読む

蟻本、チーター本等を読みましょう。チーター本は特に初心者におすすめです。

ちなみに蟻本は持ってないので、どなたか買ってくれる人を募集中です。

スライドやQiitaの記事を読む

学びたいアルゴリズム、解説を見たら知らないアルゴリズムだったときは、アルゴリズム名でググりましょう。

強い人のスライドや記事がでてくるはずです。ありがたい...。

思いつくのはこれだけですね、人によってはバチャったり教育的良問を教えてもらって解くなどしているみたいですが、僕はしませんでした。

解くときのテク

まず問題文をよく読みましょう。ある程度アルゴリズムを知っていると、問題からどのアルゴリズムを使えばいいかというのがぱっとわかる問題は多いです。

例を出すと、

• 平面上での迷路→BFS

• 頂点を結ぶ→グラフ系のアルゴリズムかDFS

• Yes、Noの明確な境界がある→二分探索

などですかね。

もしあからさまな典型がでればライブラリをコピペして終わりなのですが、それ以外の時、どうすればいいかというと、まず計算量を推測します。

nlogn、nなら通るけど、n²は通らないな...、など、ある程度分かれば大丈夫です。

次に、問題のネックとなっている部分はどれか(そこさえわかれば解ける場所)を自分の中でしっかり把握します。

そして

• 制約が簡単な場合を考える、そこから発展させる。

• サンプルを手でシュミレーションしてみて、自分が考えた過程をそのままプログラムに落とす

• 式を立てて、変形させる

• サンプルから、規則性やルールを探し出す

などをすれば、きっとACできるはずです(自己暗示)

まとめ

DPできなくても大丈夫。

海外コン出たこと無くても大丈夫。(無論出た方がいい)

ずっと早解き3完でも大丈夫。

ツイ廃でも多分大丈夫。

これを見て、「俺でもできそう」となれば幸いです。

Brainfuckを中間言語に変換するやつ

最近、自作言語を作ってみたというような人々をよく見る

僕もBF系のクソ言語作るか～ということで、その前準備として中間言語に変換するやつを作ってみた

言語仕様？は+、-、>、<、は末尾に連続して続く数を付ける、ドット、カンマ、[、]、はそのまま、という感じです

あと無駄なコードは最適化されます

+++--は+1、>>><<>は>2といった感じ

内容

こんなBFコードが

+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.++
+++++..+++.>-.------------.<++++++++.--------.+++.------.--------.>+.

こうなる

+9[>1+8>1+11>1+5<3-1]>1.>1+2.+7..+3.>1-1.-12.<1+8.-8.+3.-6.-8.>1+1.

フォルダ階層

C:/～/BFPREPROCESSOR/    
├─bfsource/
│      helloBF.bf
│      
├─bin/
│      FirstOptimize.class
│      
├─middleLang/
        helloBF.mbf

使い方

java bin/FirstOptimize helloBF.bf

のように打つとmiddleLang/にhelloBF.mbfというファイル名で変換される

実装

いつものコードコピペの垂れ流しである...

import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.Deque;

public class FirstOptimize {
    static Deque<Character> deq = new ArrayDeque<>(200);
    static BufferedWriter bw;

    public static void main(String[] args) {
        if (args.length < 1) {
            throw new IllegalArgumentException("needs sourcefile name");
        }
        String input = args[0];
        String filename = getFileName(input);
        try {
            bw = new BufferedWriter(new FileWriter("middleLang/" + filename + ".mbf"));
        } catch (IOException e) {
            e.printStackTrace();
        }
        System.out.println("start");
        conversion(input);
        System.out.println("end");
    }

    static String getFileName(String input) {
        String s;
        int dotPlace = input.lastIndexOf(".bf");
        if (dotPlace == -1) {
            throw new IllegalArgumentException("this file is not bf file\nfilename example: helloworld.bf");
        }
        int srasyu = input.lastIndexOf("/");
        srasyu = Math.max(srasyu + 1, 0);
        s = input.substring(srasyu, dotPlace);
        return s;
    }

    static void conversion(String source) {
        try (FileReader r = new FileReader(source)) {
            char c;
            int i;
            while ((i = r.read()) != -1) {
                c = (char) i;
                addStack(c);
            }
            write();
            bw.flush();
            bw.close();
        } catch (Exception e) {
            System.err.println("ファイル読み込み中にエラー発生");
            e.printStackTrace();
        }
    }

    static void addStack(char c) {
        char[] validChars = { '+', '-', '>', '<', '.', ',', '[', ']' };
        boolean flag = true;
        for (char okC : validChars) {
            if (c == okC) {
                flag = false;
                break;
            }
        }
        if (flag)
            return;

        if (!deq.isEmpty()) {
            char lastItem = deq.getLast();
            if (c == '+' && lastItem == '-') {
                deq.pollLast();
                return;
            } else if (c == '-' && lastItem == '+') {
                deq.pollLast();
                return;
            } else if (c == '>' && lastItem == '<') {
                deq.pollLast();
                return;
            } else if (c == '<' && lastItem == '>') {
                deq.pollLast();
                return;
            } else if (c == lastItem && (c == '+' || c == '-' || c == '<' || c == '>')) {
                deq.offerLast(c);
            } else {
                write();
                deq.offerLast(c);
            }

        } else {
            deq.offerLast(c);
        }
    }

    static void write() {
        char c = deq.getLast();
        try {
            if (c == '[' || c == ']' || c == '.' || c == ',') {
                bw.write(String.valueOf(c));
            } else {
                bw.write(String.valueOf(c) + deq.size());
            }
        } catch (IOException e) {
            System.err.println("ファイル書き込み中にエラー");
            e.printStackTrace();
        }
        deq.clear();
    }
}

一応解説

最初はファイル名をえいえいする部分、後は一文字ずつ読んでいく

読んだ文字がBFの有効な8文字なら、スタックに積む

スタックの最後が+で今から積むのが-、など、最適化できるところは最適化する

違う種類が入れられると、ファイルに書き出す

簡単だね、次は中間言語からJavaバイトコードを生成したいけど、ちょっと自分の実力じゃダメそう...

Javaの競プロ？用ライブラリを置いておく

これはgitを使えない人がライブラリをオンラインでどう保管するか考えた結果、記事にコピペするに帰着したクソなので、読むこと見ることを想定していません

基本こっから書く 自動テスト？知らない子ですね...(汗

import java.util.Scanner;

public class Base {
    public static void main(String[] args) {
        final Scanner sc = new Scanner(System.in);
        System.out.println();
    }
}

ベルマンフォード法

import java.util.Arrays;
import java.util.Scanner;

public class Bellman_ford {
    public static void main(String[] args) {
        final Scanner sc = new Scanner(System.in);

        System.out.println();
    }
    //辺を表すクラス
    static class Edge {
        int from;//出発元の頂点
        int to;//到達先の頂点
        int cost;//距離
    }

    static int V;//頂点の数
    static int E;//辺の数
    static Edge[] edges;

    static int[] d;//頂点毎の暫定的な最短距離

    static int INF = Integer.MAX_VALUE / 2;

    /*
    * 始点を指定して各頂点の最短距離を取得する
    * @param sv 始点とする頂点
    */
    static void bellman_ford(int sv) {
        //最短距離の初期化
        d = new int[V];
        Arrays.fill(d, INF);
        d[sv] = 0;

        //更新が終わるまで頂点を繰り返し操作していく
        while(true) {
            boolean update = false;
            for(int i = 0; i < E; i++) {
                int u = edges[i].from;
                int v = edges[i].to;
                int c = edges[i].cost;
                //もし、始点からuまでの最短距離 + uからvまでの距離cが始点からvまでの距離より小さいなら更新する
                if(d[u] + c < d[v]) {
                    d[v] = d[u] + c;
                    update = true;
                }
            }
            if(!update) {
                break;
            }
        }
    }

    static boolean bellman_ford2(int sv) {//負の閉路検出用
        //最短距離の初期化
        d = new int[V];
        Arrays.fill(d, INF);
        d[sv] = 0;

        //更新が終わるまで頂点を繰り返し操作していく
        for(int count = 0; count < V; count++) {
            for(int i = 0; i < E; i++) {
                int u = edges[i].from;
                int v = edges[i].to;
                int c = edges[i].cost;
                //もし、始点からuまでの最短距離 + uからvまでの距離cが始点からvまでの距離より小さいなら更新する
                if(d[u] + c < d[v]) {
                    d[v] = d[u] + c;
                    if(count==v-1) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

キューを使ったダイクストラ(正直仕組みわからん)

import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

//http://nishiharayuugo.blog.fc2.com/blog-entry-15.html

public class Dijkstra {//頂点数V、辺の数Eに対し、O(E log V)
    public static void main(String[] args) {
        final Scanner sc = new Scanner(System.in);
        System.out.println();
    }

    //候補クラス
    static class Candidate implements Comparable<Candidate> {
        int d;//距離
        int v;//頂点

        public Candidate(int v, int d) {
            this.d = d;
            this.v = v;
        }
        //距離が短いほど優先する
        @Override
        public int compareTo(Candidate o) {
            return this.d - o.d;
        }
    }

    //辺クラス
    static class Edge {
        int to;//どの頂点へ伸びているか
        int cost;//距離

        Edge(int to, int cost) {
            this.to = to;
            this.cost = cost;
        }
    }

    static List<List<Edge>> G;//隣接リストで表現したグラフ

    static int[] dist;//最短距離(仮定も含む)

    static int INF = Integer.MAX_VALUE / 2;

    /*
    * @param sv 始点となる頂点
    */
    static void dijkstra(int sv) {
        //初期化
        Arrays.fill(dist, INF);
        dist[sv] = 0;

        //候補の優先キューを用意
        Queue<Candidate> candidates = new PriorityQueue<>();
        candidates.offer(new Candidate(sv, 0));//最初に始点と距離0の候補を入れておく

        while(!candidates.isEmpty()) {
            //候補を取り出す
            Candidate c = candidates.poll();
            int v = c.v;
            int d = c.d;

            //意味の無い情報を捨てる
            if(dist[v] < d) {
                continue;
            }

            //確定した頂点から伸びている各辺についてみていく
            List<Edge> edges = G.get(v);
            for(Edge e : edges) {
                if(dist[e.to] > dist[v] + e.cost) {
                    dist[e.to] = dist[v] + e.cost;
                    candidates.offer(new Candidate(e.to, dist[e.to]));
                }
        }
        }
    }
}

UnionFind、簡単だけど改造するの大変そうだね(他人事)

import java.util.Scanner;

public class UnionFind {
    static int[] par = new int[100000];
    public static void main(String[] args) {
        final Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i = 0; i <= n; i++) {
            par[i] = i;
        }
        System.out.println();
    }
    static int root(int x) {
        if(par[x]==x) {
            return x;
        } else {
            return par[x] = root(par[x]);
        }
    }
    static boolean same(int x, int y) {
        return root(x)==root(y);
    }
    static void unite(int x, int y) {
        x = root(x);
        y = root(y);
        if(x == y) return;
        par[x] = y;
    }
}

nCr mod(10⁹+7)を計算するやつ、逆弦かなんか使っててThe・数学なので理解する木はない ちょっと洗練されてないね...、木が向いたら手直ししよ

import java.util.Scanner;

public class nCr {
    public static void main(String[] args) {
        final Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long r = sc.nextLong();
        //nCr = n!/r!(n-r)! = n ~ r / (n-r)!
        long n_r = n - r;
        System.out.println(String.format("n:%d\nr:%d\nn-r:%d", n, r, n_r));
        long a = 1, b = 1;
        int mod = 1000000007;
        for(int i = 1; i <= n_r; i++) {
            a = a * (r + i) % mod;
            b = b * i % mod;
        }
        long ans = a * func(b, mod - 2, mod) % mod;
        System.out.println(ans);
    }
    static long func(long a, long b, int mod) {
        if(b == 0) {
            return 1;
        }
        if(b % 2 == 0) {
            return func(a * a % mod, b / 2, mod);
        } else {
            return a * func(a, b-1, mod) % mod;
        }
    }
}

最小公倍数、最大公約数を求めるやつ。コード短いのすごいよね

public class lcm_gcd {
    static int gcd(int a, int b) {//最大公約数を求める
        if(b == 0) return a;
        return gcd(b, a%b);
    }
    static int lcm(int a, int b) {//最小公倍数を求める
        int g = gcd(a, b);//まず最大公約数を求める
        return a / g * b;//ユークリッドの互除法により
        // a*b = (aとbの最小公倍数) * (aとbの最大公約数)
        //式変形して  a / (aとbの最大公約数) * b = (aとbの最小公倍数)
        //これで最小公倍数が求まる
    }
}

エラトステネスの篩。この名前覚えられない

import java.util.Scanner;

public class エラトステネスの篩 {
    public static void main(String[] args) {
        final Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();//入力された数までの素数を判定
        int wantUpper = n;
        int furui[] = new int[wantUpper+1];

        for(int i = 2; i <= wantUpper; i++) {
            furui[i]=i;//篩に2~nまでの値を入れる
        }
        for(int i = 2; i <= Math.sqrt(wantUpper); i++) {
            for(int j = i+i; j <= wantUpper; j+=i) {//iの倍数は篩落とす
                furui[j]=0;
            }
        }
        //篩の0ではない値が全て素数
    }
}

a^b (mod p)、一生使わないだろうね(数学すぎる)

static long func(long a, long b, int mod) {
    if(b == 0) return 1;
    if(b % 2 == 0) return func(a * a % mod, b / 2, mod);
    else return a * func(a, b - 1, mod) % mod;
}

stackでのdfs、コードじゃなく雰囲気を書きます コードは２次元平面上でのdfsですが、基本的にコメントのように実装するとグラフでも動く

ArrayDeque<Point> deq = new ArrayDeque<>();
deq.push(start);//キューに突っ込む
while(deq.size()!=0) {//キューが空になるまで
    Point p = deq.poll();//まず先頭取り出し
    if(p.equals(goal)) {//終了条件チェック
        System.out.println("Yes");
        return;
    }
    if(p.x >= h || p.x < 0 || p.y >= w || p.y < 0) {//異常チェック
        continue;
    }
    if(map[p.x][p.y] == '#') {//異常チェック
        continue;
    }
    map[p.x][p.y] = '#';//通ったという記録
    for(int i = 0; i < 4; i++) {
        deq.push(new Point(p.x + x[i], p.y + y[i]));//他のところへ遷移したのをキューに突っ込む
    }
    //モノによってはここで通ったという記録を消す
}
System.out.println("No");

bit全探索、実装結構軽いよね

int ketasu = 4;//桁の数 4なら0000 ~ 1111まで
for(int i = 0; i < (1<<ketasu); i++) {

    for(int j = ketasu-1, k = 0; j >= 0; j--, k++) {
        if(((i>>j) & 1) == 1) {//左からj番目のbitが立っている(1)かどうか

        }
    }

    for(int j = 0; j < ketasu; j++) {
        if(((i>>j) & 1) == 1) {//右からj番目のbitが立っている(1)かどうか

        }
    }
            
}