2021-07-19

編入試験受験記

農工大の編入試験に合格したので記録を残しておきます。せっかく iPad を買ったので iPad で書いてみます。

受けるまで

あまりに 1 年次の成績が悪くて希望のコース(数理情報コース)に振り分けられませんでした。学科の規定で 2 年次以降にコースを変更することはできないので編入しようと思いました。他の大学を受けようか迷ったのですが、とりあえず難しそうだったしTOEIC の締め切りを忘れたり色々面倒くさかったりしてやめました。

試験対策

農工大編入の試験科目は数学、英語、専門、物理の 4 教科で、それぞれ配点が 200 - 200 - 200 - 100 です。軽くネットで調べるとボーダーは大体 7 割ぐらいみたいなことが書いてあったので、物理を捨てて他の科目で点を稼ぐという戦略で対策をしました。英語以外は過去問が公開されているので適当に読むと、どうやら 1 年次の授業でやった内容がそのまま範囲になっているということがわかりました。そのため数学と専門は 1 年次の授業の教科書を出そうなところを読みんで、出そうな問題を解きました。英語は簡単らしいという情報をネットで得ていたので特に勉強しませんでした。

数学

2 変数関数の極値
広義積分と重積分 ?
逆行列と何か ?
2 階斉次微分方程式

過去問通りという感じでした。広義積分以外はできたので 8 割 5 分ぐらい。

英語

過去問がなかったのでちょっと不安でしたが、見開き 1 ページぐらいの文章を読んで問題に答えるという形式の大問が 2 つと 50 語ぐらいの文をテーマに従って書けという内容でした。特に単語も難しくはなく、時間もかなり余裕がありました。少なくとも 9 割は取れてそう。

物理

力学と電磁気の問題でした。当然分からないので高校物理で埋められそうなところだけ埋めました。よくて 2 割ぐらい。

専門

コンピュータ数学
論理回路
ダイクストラ法(を題材にしたプログラミング問題)
知らない
知らない

専門は大問 1 のみ必答で、大問 2 ~ 4 から 2 問選択するという形式でした。1 と 3 はまあ解けるだろみたいな内容で、2 は論理回路を知っていますか？みたいな内容でした。論理回路を復習したのが効いて多分 10 割。

面接

見たことがある気がする教員 2 人と話しました。着席する前にマナーについてご指導をいただきましたが、そのあとは軽く興味のある分野と試験の手応えについて聞かれ、編入する理由、編入した後の単位の扱いの話をしました。10 分ぐらい話してた気がします。

感想

農工大編入おすすめです。

2018-12-09

JOI2018/2019 予選参加記

結果

ABCDEfの5完506点 DEがやけに簡単だと思いました

始まる前

りゅうおうのおしごと！を見ていたこれ泣いちゃうんですよね

問題

全部GitHubにあります

github.com

D

まあソートしてはいなんですけど、全部0に気づかなくていろいろ実装を直したので汚い

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    i64 n;
    cin >> n;
    vector<i64> a(n);
    for(i64 i = 0; i < n; ++i){
        cin >> a[i];
        if(i != 0 && a[i] == a[i - 1]){
            i--; n--;
        }
    }
    if(n == 1 && a[0] == 0){
        cout << 0 << endl;
        return 0;
    }
    vector<P> sorted;
    for(i64 i = 0; i < n; ++i){
        sorted.push_back(P(a[i], i + 2));
    }
    sort(sorted.begin(), sorted.end(), greater<P>());
    unordered_map<i64, vector<P>> mp;
    i64 cnt = 0;
    for(i64 i = 0; i < n; ++i){
        if(i == 0){
            mp[cnt].push_back(sorted[i]);
        }else{
            if(sorted[i].first == sorted[i - 1].first){
                mp[cnt].push_back(sorted[i]);
            }else{
                cnt++;
                mp[cnt].push_back(sorted[i]);
            }
        }
        if(i == n - 1 && mp[cnt][0].first != 0){
            cnt++;
            mp[cnt] = {P(0, 1), P(0, n + 2)};
        }
    }
    vector<bool> used(n + 10, false);
    i64 tmp, ans;
    tmp = ans = 0;
    for(i64 i = 0; i < cnt + 1; ++i){
        for(i64 j = 0; j < mp[i].size(); ++j){
            i64 num = mp[i][j].second;
            if(used[num - 1] && used[num + 1]) tmp--;
            else if(!used[num - 1] && !used[num + 1]) tmp++;
            used[num] = true;
        }
        ans = max(ans, tmp);
    }
    cout << ans << endl;
}

E

DPパートが簡単だったのですんなりいったソートをしましょう

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    i64 n, m;
    cin >> n >> m;
    vector<i64> a(n + 10), l(m), r(m);
    vector<P> sorted(m);
    for(i64 i = 0; i < n; ++i) cin >> a[i + 1];
    for(i64 i = 0; i < m; ++i){
        cin >> l[i] >> r[i];
        sorted[i] = P(l[i], r[i]);
    }
    sort(sorted.begin(), sorted.end());
    vector<i64> min_index(n + 10, -1);
    i64 cnt = 0;
    for(i64 i = 0; i < m; ++i){
        cnt = max(cnt, sorted[i].first);
        while(sorted[i].second >= cnt){
            min_index[cnt] = sorted[i].first;
            cnt++;
        }
    }
    vector<i64> dp(n + 10, 0);
    for(i64 i = 1; i < n + 1; ++i){
        if(min_index[i] == -1){
            dp[i] = dp[i - 1] + a[i];
        }else{
            dp[i] = max(dp[i - 1], dp[min_index[i] - 1] + a[i]);
        }
    }
    //for(i64 i = 1; i < n + 1; ++i) cout << i << ": " << min_index[i] << endl;
    cout << dp[n] << endl;
}

感想

今年も本選に行けそうなので嬉しい真面目に精進して春合宿行くぞい

2018-09-09

CyberRebeat CTF Write-up

概要

生活習慣崩壊ズとして出ました全完して同率１位でした f:id:kobaryo222912:20180909113313j:plain

先に↓のチームメンバーのWrite-upを読むことをおすすめします keymoon.hatenablog.com

ecasd-qina.hatenablog.com

僕が解いたのは6問でやるだけ問題を除くと実質2問+αでした f:id:kobaryo222912:20180909113328j:plain ↑zohe君が解いた問題をぼくとkeymoonがそれぞれ１つずつ代理で提出しています(どちらともBinary) 以下に解いた問題を載せます(解いた順、ジャンルの右の数字はdifficulty)

Write-up

Readme(Misc, 100)

f:id:kobaryo222912:20180909035858j:plain 上の画像が与えられますぐっと睨んで感じるとflagが出ます(コツは日本語を忘れることです)

Secret.pdf(Stegano, 10)

黒塗り部分があるpdfファイルが与えられます Ctrl+A Ctrl+C Ctrl+V

Whitepage(Web, 10)

<form action="index.php" method="post">
   <input type="text" name="id" style="visibility:hidden" />
   <input type="text" name="password" style="visibility:hidden" />
   <button>LOGIN</button>
</form>

このままだと入力フォームが見えないのでhtmlを書き換えましょう最初出題ミスでidが"Hiro"じゃなくて"Hero"になっていた少し時間を溶かされた

Alpha(Stegano, 100)

GIMPで

f:id:kobaryo222912:20180909045738p:plain

えいw

f:id:kobaryo222912:20180909045902p:plain

Uploader(Web, 100)

f:id:kobaryo222912:20180909041957p:plain ファイルの検索ページが与えられます

f:id:kobaryo222912:20180909042050p:plain 適当に試すとSQL Injectionっぽいです URLとエラーメッセージからSQLite3っぽいことが分かります定番の

' OR 1=1;

を試すと f:id:kobaryo222912:20180909042210p:plain

secret.zipが出てきますこれを落としてunzipするとパスワードを要求されます guestでログインするとsamle.zipのパスワードが表示されることから、haradaでログインしてパスワードを表示させたくなりますこれにはharadaの(アカウントの)パスワードが欲しくなります最初えかすどがBlind SQL Injectionっぽいと言っていてテーブル名がほしいと言われたので頑張りますこれはSQLiteのマスターテーブルの情報を検索結果の後につけてあげると通って、

' union select name, sql from sqlite_master --";

としてあげると

f:id:kobaryo222912:20180909042253p:plain

と言われるので0でパディングしてあげます

' union select name, sql, 0, 0 from sqlite_master --";

とすると

f:id:kobaryo222912:20180909042500p:plain

とテーブル名とCREATE TABLEしたときの情報が見れますここで冷静に考えるとテーブル名を取る要領でUsersの情報が取れそうなことが分かるので、

' union select userid, password, 0, 0 from Users --";

としてあげるとパスワードが

f:id:kobaryo222912:20180909042313p:plain

出てくるのでログインするとzipのパスワードが分かります解凍すると平文のflagが出てきます (SQL Injectionの問題を初めて解くことが出来たのですごく嬉しかった)

FLAG.encrypted(Crypto, 200)

とりあえず暗号文と公開鍵を見てみます暗号文は特に特徴は無いですが、公開鍵をopenssl public-key.pemとかして出してみると明らかにeの値が大きいことが分かりますググるとeの値が極端に小さいor大きい時に使えるWiener's attackというものが出てきます

github.com

GitHubにサンプルがあるので落とします適当に書き換えてあげるとdが出てきますあとはpow(C, d, n)とすると出てきます最初暗号文を取り違えていてつらかった

番外編

f31337(Binary, 200)

99%zoheが解きますただ出てきたflagが不正解になるので見てみます

CRCTF{y0ur_m4chine_1s_v3ry_f3st!!}

天才なので見た瞬間に'f3st'の違和感に気づきますまあダメ元で出してみるかと思い

CRCTF{y0ur_m4chine_1s_v3ry_f4st!!}

としてあげると通ります

Signature(Crypto, 200)

問題文を見ます PHP AND md5という検索クエリを脳に投げるとあんぐすとろむCTFでsei0oプロが解いていた問題を思い出したのでWrite-up

scrapbox.io

を見ますただし問題が全く異なっていたので関係なくて悲しいな〜と思いながら眺めていると "cryptoをちょくちょく学んでいたためか伸長攻撃かな？と一瞬思ったが、そもそもハッシュが与えられないのでそれは違った。" という1文を見つけますこれをチームメンバーに投げて少し考えて2時間ほど寝るとチームメンバーが解きます

感想

問題が基本的に簡単なのが100%原因ではあるけどプロのチームと同じ順位ですごく嬉しい
解いている問題が被る(特にkeymoon 死んで詫びるつもりは無いけどごめんなさい)ことはあったけどいい感じに協力しつつ解けてよかった特にぼくのWrite-upの最後の4問は本当にチームワークだった(f31337は違うけど)
PPCをえかすどがすぐ倒してzoheがRevを一人で倒してkeymoonもSignature以外は一人で回答数が少ない問題を倒しまくっててこわかったチームを追い出されないように頑張りたい
sei0oを崇めよ

2018-06-15

SuperCon予選

やったこと

眺めているとすごく難しそう
まあ考えていると(0, 0)からDFSではいができることに気づく
実装する
自明に「今までの距離 + 現在地から原点までの最短距離 > n」が成り立つ時はアなので枝刈り
DFSはstackを使ったほうが速いらしい
これは罠で実装が出来なかった
inlineをつけると1.5倍ぐらい早くなった
原点の4近傍の点が障害物もしくはもう通った点で埋まっていれば戻ってこれないので枝刈り
ここらへんで高速化のアイデアが尽きる
少し考えると答えがm<= 2ぐらいまでなら埋め込めることに気づく
さらに考えると原点からの距離がn / 2以上の障害物は関係ないのでmの値を減らせる
答えを埋め込む
ここでバグりまくる
最終的に添え字の"[]"の位置が間違っていることに気づく
とりあえず m = 0, 1(0というのは答えに関係のある障害物が無い時)の答えを埋め込む
m = 2の時を埋め込む
死ぬほどつらいのでn = 20, m= 2の時に絞る
i7-6700が頑張る
3,40分で答えが出る
埋め込む
応募用紙を書く
提出する

テストケースの実行結果

Ans= 133662, time=19

ソースコード

#include "sc1.h"
#include "stdio.h"
#include <iostream>

using namespace std;

int dx[4] = {0,1,0,-1};
int dy[4] = {-1,0,1,0};

int ans = 0, cnt = 0, cnt1;
int index2[20];
bool mas[100][100], flag[100][100];
const int offset = 50;

int index[21][21] = // 2*10^6 以上あるので省略

inline void dfs(int x, int y, int l){
    if(mas[51][50] && mas[49][50] && mas[50][49] && mas[50][51]) return;
    if(scN - l < abs(offset - x) + abs(offset - y)) return;
    mas[x][y] = true;
    for(int i = 0; i < 4; ++i){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(!mas[nx][ny]) dfs(nx, ny, l + 1);
        if(l + 1 == scN && nx == 0 + offset && ny == 0 + offset) ++ans;
    }
    mas[x][y] = false;
}

int main(){
    scInput();
    for(int i = 0; i < 100; ++i) for(int j = 0; j < 100; ++j){
        mas[i][j] = false;
    }
    for(int i = 0; i < scM; ++i){
        if(abs(scB[0][i]) + abs(scB[1][i]) > scN / 2) continue;
        mas[scB[0][i] + offset][scB[1][i] + offset] = true;
        cnt1 = i;
        index2[cnt] = i;
        ++cnt;
    }
    if(cnt == 0){
        scOutput(ans0[scN / 2 - 7]);
        return 0;
    }
    if(cnt == 1){
        scOutput(ans1[scN / 2 - 7][index[scB[0][cnt1] + 10][scB[1][cnt1] + 10]]);
        return 0;
    }
    if(cnt == 2 && scN == 20){
        int ax = scB[0][index2[0]], ay = scB[1][index2[0]];
        int bx = scB[0][index2[1]], by = scB[1][index2[1]];
        int a = index[ax + 10][ay + 10], b = index[bx + 10][by + 10];
        if(a > b) swap(a, b);
        scOutput(ans20_2[a][b - a - 1]);
        return 0;
    }
    mas[offset][offset] = true;
    dfs(0 + offset, 0 + offset, 0);
    scOutput(ans);
}

感想

正直定数倍高速化コンテスト感が強かった

チーム名はaldas(リパライン語で雷雲の意)です　かっこいいね(@sashimiwiki さんに付けて頂きましたありがとうございます！)

2018-06-04

JOI2017/2018 本選

今更ですが書いておきます

忙しくても反省は見たほうがいいかも知れません

１日目

秋葉原に(多分最速で)到着します

秋葉原

最速かな? (@ 秋葉原駅 in 千代田区, 東京都) https://t.co/1YE9obBQpf pic.twitter.com/9N3YhR2Y5m
— 絶対零度(1) (@6Lgug) February 10, 2018

ウニを1人でしました

pic.twitter.com/6m9H7Q7LNR
— 絶対零度(1) (@6Lgug) February 10, 2018

激エモスポットに行きました

I'm at コミックとらのあな秋葉原店B - @tora_akiba_b in 千代田区, 東京都 https://t.co/ss9LZ9ZjkA pic.twitter.com/4uHBGaCF3a
— 絶対零度(1) (@6Lgug) February 10, 2018

みんなでごはんを食べました

I'm at 雁川 - @gansen0141 in 千代田区, 東京都 https://t.co/yuqm7W4U1C pic.twitter.com/4l8XTckSFV
— 絶対零度(1) (@6Lgug) February 10, 2018

この後出発します

筑波

お財布を電車に忘れていることに気づきます

practiceに遅刻します(一緒にいた人々と委員会の方々にご迷惑をおかけしました)(申し訳ありません)

もう一度筑波に着きます　走ります

pic.twitter.com/JJ7uHrghIc
— 絶対零度(1) (@6Lgug) February 10, 2018

立食をします

現在 pic.twitter.com/1IWHviJC8x
— 絶対零度(1) (@6Lgug) February 10, 2018

独房で人々(@yfba_ @Kutimoti_T @lumc_ @57tggx)とお話をします

寝ます(28:00)

２日目

起床をします(5:30)

部屋の電気を結局消さなかった...
— 絶対零度(1) (@6Lgug) February 10, 2018

ごはんを食べて会場に行きます

ぞい！
— 絶対零度(1) (@6Lgug) February 10, 2018

えー１問目を15分で解いた後は虚無をしていました
— 絶対零度(1) (@6Lgug) February 11, 2018

帰ります

若干酔った
— 絶対零度(1) (@6Lgug) February 11, 2018

↑結構つらかった

感想

楽しかった　税金でオフ会が出来るのはやっぱり素晴らしい

反省

財布を忘れてPractice Session に遅れるのはやめましょう

ちゃんと前日は寝ましょう

独房の鍵は返しましょう

部分点は自明でも実装したほうがいいですなにか見えることがあるはずです

何が言いたいか

www.pixiv.net

を見ましょう

2017-12-11

JOI2017/2018 予選参加記

競技プログラミング関係

結果

ABCEの4完(400点)でしたうれしいね
コードを晒します

A 鉛筆 (Pencils)

int main() {
	int n, a, b, c, d;
	cin >> n >> a >> b >> c >> d;
	int ap = n / a;
	int cp = n / c;
	if (n % a != 0) {
		ap++;
	}
	if (n % c != 0) {
		cp++;
	}
	if (b* ap > d * cp) {
		cout << d* cp << endl;
	}
	else {
		cout << b * ap << endl;
	}
}

はい

B 双六 (Sugoroku)

int main() {
	int n, a, ans = 0, cnt = 0;
	cin >> n;
	REP(i, n) {
		cin >> a;
		if (a == 1) {
			cnt++;
		} else {
			ans = max(ans, cnt);
			cnt = 0;
		}
	}
	ans = max(ans, cnt);
	ans++;
	cout << ans << endl;
}

Aより実装楽で面白いね

C 幹線道路 (Trunk Road)

int main() {
	int h, w;
	int num[25][25];
	cin >> h >> w;
	REP(i, h) {
		REP(j, w) {
			cin >> num[i][j];
		}
	}
	int ans = INF;
	REP(a, h) {
		REP(b, w) {
			int tmp = 0;
			REP(i, h) {
				REP(j, w) {
					tmp += min(abs(i - a), abs(j - b)) * num[i][j];
				}
			}
			ans = min(ans, tmp);
		}
	}
	cout << ans << endl;
}

一瞬迷ったけど普通に全探索

D 水ようかん (Mizuyokan)

わけがわからないよ
bit全探索を書こうとするも書けないので0点

E 森林伐採（Deforestation）

int dx4[4] = {0,1,0,-1}, dy4[4] = {-1,0,1,0};
 
int main() {
	ll dp[31][31];
	dp[0][0] = 0;
	ll a[31][31];
	ll dist[31][31];
	ll h, w;
	cin >> h >> w;
	REP(i, 31) {
		REP(j, 31) {
			dist[i][j] = -1;
		}
	}
	dist[0][0] = 0;
	REP(i, h) {
		REP(j, w) {
			cin >> a[i][j];
		}
	}
	queue<P> que;
	que.push(P(0, 0));
	while (!que.empty()) {
		auto p = que.front(); que.pop();
		int di = p.first; int dj = p.second;
		REP(i, 4) {
			int nx = di + dx4[i]; int ny = dj + dy4[i];
			if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
            ll COST = dp[di][dj] + (dist[di][dj] * 2 + 1) * a[nx][ny];
			if (dp[nx][ny] == COST && dist[nx][ny] > dist[di][dj] + 1) {
				dist[nx][ny] = min(dist[nx][ny], dist[di][dj] + 1);
				que.push(P(nx, ny));
			}else if (dist[nx][ny] == -1 || dp[nx][ny] > COST) {
				dp[nx][ny] = COST;
				dist[nx][ny] = dist[di][dj] + 1;
				que.push(P(nx, ny));
			}
		}
	}
	cout << dp[h - 1][w - 1] << endl;
}

拡張Dijkstraっていう分類の問題らしい
BFSをして特定のマスまでのコストとそのときの(0, 0)からの距離を持つだけ
なんでAC出来たんでしょうか僕にも分かりません

追記

上のコードが限界だったのでちょっと手直ししました(2018/11/26)

int dx4[4] = {0,1,0,-1}, dy4[4] = {-1,0,1,0};
 
int main() {
    // 入力
    ll dp[31][31], a[31][31], dist[31][31];
    ll h, w;
    cin >> h >> w;
    REP(i, 31) {
        REP(j, 31) {
            dist[i][j] = -1;
        }
    }
    REP(i, h) {
        REP(j, w) {
            cin >> a[i][j];
        }
    }

    dist[0][0] = 0; // (0, 0)までの距離は0
    dp[0][0] = 0; // (0, 0)までのコストは0
    queue<P> que;
    que.push(P(0, 0)); // (0, 0)からスタート

    while (!que.empty()) {
        auto p = que.front(); que.pop();
        int x = p.first; int y = p.second; // もともといたマス

        REP(i, 4) {
            int nx = x + dx4[i]; int ny = y + dy4[i]; //四近傍で回す
            if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue; // 領域内か判定
            ll cost = dp[x][y] + (dist[x][y] * 2 + 1) * a[nx][ny]; // https://twitter.com/6Lgug/status/1066718346509348864

            // 行っていないマスもしくは行っているけど現在のコストのほうが少ないなら更新
            if (dist[nx][ny] == -1 || dp[nx][ny] > cost) {
                dp[nx][ny] = cost;
                dist[nx][ny] = dist[x][y] + 1; // 距離は前のマスまでの距離+1なので
                que.push(P(nx, ny));
                continue;
            }

            // コストが同じでも距離が短いなら更新((nx, ny)以降のマスまでの最小コストが減りうるので)
            if(dp[nx][ny] == cost && dist[nx][ny] > dist[x][y] + 1) {
                dist[nx][ny] = dist[x][y] + 1;
                que.push(P(nx, ny));
            }
        }
    }
    cout << dp[h - 1][w - 1] << endl; // 出力
}

F L番目のK番目の数 (LthKthNumber)

全探索しようとしましたが書けませんでした

感想

3完+部分点しようと思っていたので嬉しい
が部分点も取れない実装力の無さには萎えました
(本戦行けるといいなあ...)

追記

本選行きます
0完太陽☼にならないようにがんばるぞい