Java初心者の勉強日記

初心者プログラマーが日々の勉強で思ったことを書いていきます。

DensanCTFに参加しました

チームMaru_Gameで参加して、全完3位でした。 僕はそんなに解いていません。 チームメンバーはtomohiroとtakoです。

Russia:いらすとやさん

2枚の画像が与えられる。どちらも同じように見える画像。 なにかが仕込まれているとのヒントがある。

2枚の内、サイズが大きいほうにFLAGがあると当たりをつける。 同じように見える画像なのでDiffを取りたい気持ちになったが、バイナリのDiffは可視化が難しく、できなかった。 諦めてバイナリエディタで見ると、PNGの終了コードIENDの後にもなにかある。 そこを切り出すと、zipであることがわかるので解ける。

FLAG{f1l31nclud3pn5}

Australia:Word File

wordファイルと言われてファイルが与えられる。

fileコマンドで種類を判定したいが、不明。 ヒントでエンディアンとあるので、エンディアンを逆にするツールを適当に落として適応。 再びfileコマンドを使うと、word2007+とか表示されるので、wordで開いておわり。

ちなみに僕はPCにwordを入れていないのと、OpenOfficeでは開けなかったため、チームメンバーに投げて開いてもらった。

FLAG{B1n4ry_1s_fun}

US:WIP Page

ファイル表示用のページと、暗号化したflagを表示するページがある。

message hereのURLが/message.php?p=linskslsisfjfie.txtという形式になっている。 p=で指定したファイルを表示するとわかる。 message.phpにp=flag.phpを渡すことで、flag.phpファイル自体を覗いて処理を見る。 wer8unvlgkxu84.txtをhashしたものを表示しているようだ。 よってp=wer8unvlgkxu84.txtでもう一度アクセス。

FLAG{dis_is_a_vu1ner4bi1ity}

感想

初心者向けだという印象。そこまで苦戦するようなことはなかった。 RevはCutterというツールを使えば簡単に解けたらしい。

応用情報に合格しました

平成30年秋季の応用情報技術者試験に合格しました。 今更ですが、これから応用を受験する人に向けて応用の受験の流れを書いてます。

応用受験申し込み技術者試験

とりあえず応募しましょう。応募しなければ受験できません。

IPAの試験のTwitterアカウントなどの通知をonにして、申し込み期間中に忘れず申し込みましょう。

対策本を買う

まずは午前対策の本を買いましょう。基本情報に毛が生えた感じで、広く浅くという内容。

個人的オススメは、安心と信頼のキタミ式 Amazon CAPTCHA

注意:このリンクの本は30/31年用の本です。新しく買うなら最新のものを買いましょう。

人に借りる場合は、5年ぐらい古くてもなんとかなると思います。

まずはこれを数周しましょう

受験票が届く

試験の1,2週間前に受験票が届きます。

ここから焦り始めます。あるいは、「あっ申し込みしてたんだった」と気づきます。 正直そこから勉強を始めても受かる人は受かります。

そろそろ午後対策もする時期です。できれば午後の問題集を買ってやるのが理想です。 できない場合も、過去問サイトから直近の午後問題をやった方が絶対にいいです。

  • 午後試験の問題の雰囲気
  • 筆記がどれくらい/どんな感じで出題されているか
  • どのジャンルが自分は得意か

を確かめましょう。

応用起床試験、応用写真貼り付け試験

試験日にちゃんと起きて、試験日までに受験票に顔写真を貼り付ける。

これの合格率が6割ほどです(※要出典)。 これに合格すればもう受かったようなものです。

応用情報技術者試験

寝ない。人を呼ばずに勝手に退室しない(戒め)。

応用受験票保管試験

発表は正午です。午前午後どちらも6割取れていれば合格です。

受験票にある番号で結果の照会をします。 これができないと受かったかどうかわからないまま、合格証が届くのを待つことになり、精神衛生に非常に良くありません。

自分の場合

ここまで書きましたが、僕がやったことじゃないです。(は?

午前はキタミ式を買ったはいいものの、半分も読まず放置。 受験票が届いて焦る。キタミ式を3周する。この時点で試験前日。 過去問サイトで午前の過去問を40問解く。午後問題なにそれ?で受験会場へ。 午前が終わった後の休憩時間で午後の過去問を雰囲気だけ見る。 合格。

f:id:naoppy_ac:20181229164545p:plain
結果

当たり前ですが午後がギリギリですね。午後は選択なので、とりあえず全てに目を通して、解けそうな問題から解いていきましょう。

まとめ

すいません。だいぶネタ記事です。

気負わずにいきましょう。

GitChallenge10に参加しました

mixiの主催するGitChallengeというイベントに参加してきました。

GitChallengeとは、Gitに関係した様々な課題がリポジトリ単位で与えられるので、そのリポジトリの課題を解決する技術を競うというイベントです。 難しい課題は点数が高くなっており、2人ペアで点数を競います。まさに競技という感じでした。

当日までを振り返ってみます。

応募

息を吸うようにTwitterをしていると、交通費支給のイベントがあるぞ!ということでTLが盛り上がっていました。 mixiのマイページから早速応募。

応募するときに聞かれたことは、Gitを使った経験やGitをどれくらい使えるか、などなどです。 僕は「高専プロコンでGitを使ったけど一人だけで、複数人開発はしたことないのでやってみたい」みたいなことを書きました。今思えばイベントの趣旨に沿ってたのかもしれないですね。 その時の技術レベルは「git add, commit, push, branchがわかるよ、SourceTree上でポチポチしながらgit flowを使ってるよ」ぐらいのよわよわでした。

当落発表

パソコン甲子園の前日にmixiマイページに連絡がきました。倍率とかはわからないんですけど、すごい喜びました。

行けることがわかってから、gitの勉強を始めました。何をやったかというと、progit.pdfの日本語版を読みました。

github.com

ここからpdfをダウンロードしましょう。

不運にも、GitChallengeの前がテスト期間だったせいで、progitは読み終わりませんでした。

当日

会場まで

5時起床、新幹線で渋谷まで。当日は渋谷のmixiオフィスに11時集合だったので時間が余る。

渋谷の啓文堂書店で時間をつぶすことに、ここは技術書もまあまああり、駅から近いのでオススメです。 www.keibundo.co.jp

Kotlin イン・アクションを衝動買いしました。面白い本です。 Kotlinイン・アクション | マイナビブックス

会場

会場に入るとすぐにチーム番号(あらかじめ決められている)を言われたので、その席に行くと、もう誰かいる...。 おかしい...おかしい....。

どうやらチーム番号のエルとアイを間違えて伝えてしまったようです。いきなり焦った。

無事、自分の席へ。なんと相方は香川高専のMackysonさん。限界オタク同士で助かりました。

競技まで

11時からモンスターストライクの開発にgitがどう使われているか~というような内容のLTがありました。

昼食は用意して頂きました。ありがとうございます。 おいしいカレーでした(語彙力)。

競技

競技内容は次に参加する人のために言ってはいけないんですが、ざっくりいうとCONFLICT HELLです。

.gitの中身とかまで覚えて来る必要はありません。それは高難易度問題だけです。それぐらいの難易度です。

あと、僕はSourceTree(gitのGUIクライアント)を使えば見やすいからいけるやろ!と思っていたのですが、役に立ちませんでした。 というのも、GUIは起動や再描画に時間がかかり編集結果がすぐに反映されなかったり、おかしいデータをはじめから表示しなかったりと、使い物になりませんでした。 MackysonさんからtigコマンドというCUIクライアントを教えていただきました。使うならこれです。

競技終了

真ん中ぐらいの順位でした。相方のMackysonさんのおかげです...。

その後は問題解説を数問したのち、LTを2つ挟んで懇親会でした。懇親会は終電の関係上最後までいられませんでした。8時ぐらいまでしてたみたいです。

余談

競技開始前に限界オタク数人でやる気スイッチをポチポチしました。タノジイ!!

香川高専のお二人から名刺を頂きました。実は高度に偽装された香川の特産品紹介カードでした。流石タカマツ族。

参加者層の年齢は高2~学部4年ぐらいでした。多分僕が最年少でした。

まとめ

GitChallenge楽しかったです!!!!!

普段経験できないようなことを経験でき、自分のgit力に何が足りないのか把握できました。 弊学からも次からどんどん行ってほしいですね。強くなくても向上心さえあればすごい刺激になる場所です。

こんな素敵なイベントに呼んでくださったmixiに圧倒的感謝...

ABC115-D解説

お詫び

ここに書いてあった記事は naoppy-jyoken.hatenablog.com移転しました

この記事ではD問題の思考経緯などを書いていきます。

D - Christmas

問題

D - Christmas

思考経緯

法則性を見つける問題かなと思い、まずは問題文通りパティを P、バンを B で表すを実装していきます。

public class Dstr {
    public static void main(String[] args) {
        for (int i = 0; i < 5; i++)
            System.out.println(makeBG(i));
    }

    private static String makeBG(int level) {
        if (level == 0) return "P";

        return new StringBuilder("B")
                .append(makeBG(level - 1))
                .append("P")
                .append(makeBG(level - 1))
                .append("B")
                .toString();
    }
}

まずはレベル0~4までのバーガーを文字列化して出力してみました。

出力結果
P
BPPPB
BBPPPBPBPPPBB
BBBPPPBPBPPPBBPBBPPPBPBPPPBBB
BBBBPPPBPBPPPBBPBBPPPBPBPPPBBBPBBBPPPBPBPPPBBPBBPPPBPBPPPBBBB

左右は対称だということが問題文からも、結果からもわかりました。 バーガーを下から食べていく。という問題文は上から、と読み替えてもいいですし、バーガーを横にして左から(あるいは右から)、と考えてもいいことがわかりました。 問題からノイズを取り除いて、本質だけを見ましょう

ここからわかることは、nが50の時、バーガーは非常に長くなるであろう、ということです。 愚直にすることができないことがわかりました。 じゃあ、どれくらい長いの? というわけで、次はそれを求めていきます。

バーガーの長さ
public class Datsusa {
    public static long[] AtsusaDP = new long[51];

    static {
        AtsusaDP[0] = 1L;
        for (int i = 0; i < 50; i++) {
            AtsusaDP[i + 1] = 3L + 2 * AtsusaDP[i];
        }
    }

    public static void main(String[] args) {
        for (int i = 0; i < 51; i++)
            System.out.println(AtsusaDP[i]);
    }
}

厚さの漸化式はlevel_0で1、level_iで3+2*level_(i-1)です。これは問題文から自明だと思います。 よってレベルが低い方から求めていくと、順番に求まります。

では、出力結果を見てみましょう。

1
5
13
29
~~省略~~
2251799813685245
4503599627370493

レベル50のバーガーの厚さは4503599627370493ということがわかりました。一枚ずつシュミレーションしながら食べていっても、間に合いそうにはないですね。

この辺りから、バーガーを一気に食べられると楽だなという気持ちになってきます。 問題文は何枚食べるかが与えられます。もし、あるレベルのバーガーを一気に食べても、まだ食べられる余力がある(あるレベルのバーガーを食べた後のあと何枚食べるか >= 0)なら一気に食べたいです。そして、無理ならばバーガーを細かく分解して食べていきます。ただ、その時いくつのパティを求めたかがわからないと問題が解けません。

なので次はレベルごとのバーガーに含まれるパティの数を求めていきます。

public class Dpcount {
    public static long[] P_CountDP = new long[51];

    static {
        P_CountDP[0] = 1;
        for (int i = 0; i < 50; i++) {
            P_CountDP[i + 1] = 1L + 2 * P_CountDP[i];
        }
    }

    public static void main(String[] args) {
        for (int i = 0; i < 51; i++)
            System.out.println(P_CountDP[i]);
    }
}

パティの個数の漸化式はlevel_0で1個、level_iのとき1+2*level_(i-1)です。これも問題文から自明ですね。

出力結果は省略します。

これらあるレベルのバーガーの厚さや含まれるパティの数は一瞬(たった50回のループ)に求まりました。

では、一気に食べるOR分解する動作を実装してみましょう。

実装

再帰関数を使いながら食べていきます。 再帰関数には今食べている部分的なバーガーのレベル、そして残りの食べるべき数を渡します。 今までに食べたパティの総数は渡さなくていいの?と思うでしょうが、それはグローバル変数ansに記録していきます。 関数名はeatBGとします。

バーガーを一気に食べられる場合

/**
 * @param level ハンバーガーのレベル
 * @param rest  残りの食べるべき数
 * @return 新しい残りの食べるべき数
 */
private static long eatBG(int level, long rest) {
    if (rest >= AtsusaDP[level]) {
        rest -= AtsusaDP[level];
        ans += P_CountDP[level];
        return rest;
    }
}

できました。次はelse節を書いていきます。 else節には何を書けばいいでしょうか? rest >= AtsusaDP[level]がfalseな場合、つまり今の部分的なバーガーのサイズではその途中までしか食べられない場合です。 その場合、バーガーを分解していきましょう。 食べている途中でrestが0になるでしょう。そのとき、もう食べる必要がないのに食べて、今までに食べたパティの総数を増やしてしまわないように気を付けましょう。

} else {
    rest--;// B part
    if (rest > 0) rest = eatBG(level - 1, rest);// n-1 BG part
    if (rest > 0) {// P part
        rest--;
        ans++;
    }
    if (rest > 0) rest = eatBG(level - 1, rest);// n-1 BG part
    rest--;// B part
    return rest;
}

できました。しかしまだこれで終わりではありません。動かせばわかるのですが、level-0のところまで分解されると、level-(-1)に分解しようとしてしまいます。 よってlevel=0のときの処理を関数の先頭に書いてあげます。

if (level == 0) {
    if (rest > 0) {//P part
        ans++;
        return rest-1;
    } else {
        return rest;
    }
}

レベル0まで分解されたら、Pしかないバーガーなので食べれたら食べて終わりです。

では、コードをまとめて見てみましょう。

package ABC115;

import java.util.Scanner;

public class A {
    public static long[] AtsusaDP = new long[51];

    static {
        AtsusaDP[0] = 1L;
        for (int i = 0; i < 50; i++) {
            AtsusaDP[i + 1] = 3L + 2 * AtsusaDP[i];
        }
    }

    public static long[] P_CountDP = new long[51];

    static {
        P_CountDP[0] = 1;
        for (int i = 0; i < 50; i++) {
            P_CountDP[i + 1] = 1L + 2 * P_CountDP[i];
        }
    }


    public static long ans = 0L;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long x = sc.nextLong();

        eatBG(n, x);
        System.out.println(ans);
    }

    /**
     * @param level ハンバーガーのレベル
     * @param rest  残りの食べるべき数
     * @return 新しい残りの食べるべき数
     */
    private static long eatBG(int level, long rest) {
        if (level == 0) {
            if (rest > 0) {//P part
                ans++;
                return rest-1;
            } else {
                return rest;
            }
        }

        if (rest >= AtsusaDP[level]) {
            rest -= AtsusaDP[level];
            ans += P_CountDP[level];
            return rest;
        } else {
            rest--;//B part
            if (rest > 0) rest = eatBG(level - 1, rest);// n-1 BG part
            if (rest > 0) {//P part
                rest--;
                ans++;
            }
            if (rest > 0) {//n-1 part
                rest = eatBG(level - 1, rest);
            }
            rest--;//B part
            return rest;
        }
    }
}
最後に

めっちゃ丁寧に解説したので、D問題初めてやる人とかの足がかりになればいいな。 論理的な意味を重視したコードを書いたので冗長な部分は多々あります。

こんなクソ長い記事を読んでいただきありがとうございました。

Procon29に参加しました

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

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

f:id:naoppy_ac:20181030212447p:plain

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

f:id:naoppy_ac:20181030212632p:plain

大会までの流れ

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です。

入力

f:id:naoppy_ac:20181030230648p:plain

起動時

f:id:naoppy_ac:20181030231728p:plain

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

f:id:naoppy_ac:20181030231744p:plain

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

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

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

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

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

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

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

f:id:naoppy_ac:20181030233303p:plain

これにより、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位でした

以下、解答状況

f:id:naoppy_ac:20180909154747p:plain

f:id:naoppy_ac:20180909154839p:plain

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

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

Crypto1:Rotation

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

Misc1:Readme

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

f:id:naoppy_ac:20180909155640p:plain

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

頑張って読みましょう。

Recon1:Tweet

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

f:id:naoppy_ac:20180909155910p:plain

Recon2:CyberRebeatScripts

GitHub - ennach/CyberRebeatScripts: CyberRebeat's script files

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

Recon3:ChangeHistory

GitHub - ennach/ChangeHistory: CyberRebeat's scripts 2

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

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

f:id:naoppy_ac:20180909160440p:plain

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

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

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

Stegano1:Secret.pdf

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

Stegano2:Alpha

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

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

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

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

f:id:naoppy_ac:20180909161205p:plain

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

Trivia1:Monero

coinhiveです。

Trivia2:Crossword

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

f:id:naoppy_ac:20180909161418p:plain

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

Web1:White page

f:id:naoppy_ac:20180909161642p:plain

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(N2)、TreeSetへの挿入にO(logN)、内部での文字列比較にO(N)なので、O(N3logN)で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の文字列から見ていくなどの高速化をしようとしましたが、結局意味はありませんでした。

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