精進

勉強したこととか

ICPC国内予選2015

つくばプログラミングサークルからチームYUMEYAで参加

結果


まとめ

tkbctf3 Write-up

tkbctf3にチーム(1人)R08gVE8gVEhFIEZVVFVSRQで参加し，Web103とMisc250が解けた．

Web103 From the Northern Country

指定されるアドレスを開くと北朝鮮からのアクセス限定だと表示された．

Internet in North Korea - Wikipedia, the free encyclopedia

によると，北朝鮮のIPv4のアドレスの範囲は175.45.176.0–175.45.179.255らしいので，この範囲のアドレスをcurlコマンドでX-Forwarded-Forヘッダに指定して実行したところフラグ

KEY{공격전이다}(攻撃前だ？)

が表示された．
f:id:Lay_ec:20140505115216j:plain

Misc250 15-Puzzle

指定されたアドレスのポートに接続すると15パズルが表示され，解が存在するなら最小ステップ数を，存在しないならNOを送信する問題だったので，ググって出てきたツール

１５パズルを解く for Windows

で得た解を入力していったら9～10問ぐらい解いたところでフラグが表示された(フラグが何だったか忘れた).
この問題はサーバー側でトラブル(？)があって途中まで正答者が居なくて，復旧後の丁度良いタイミングでフラグを提出したようで，2番目の正答者になり8%の追加ポイントが貰えた．

結果

373ポイント 21位

Codeforces 235 Division2

AとCが通った．Bは終了直前まで正しく問題文理解できてなくて間に合わなかった．

A - Vanya and Cards

http://codeforces.com/contest/401/problem/A

概要

1000以下の正整数nとx，絶対値がx以下の整数がn個与えられる．
そのn個の数の和に絶対値がx以下の整数を加えて0にしようとするとき，最小で何個の整数を加えれば良いか求めよ．

解法

入力の合計値の絶対値をxで何回引くと0以下になるか数えた．
単にxで割ったのを切り上げれば良いのに終了後に気づいた．

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <functional>
#include <set>

using namespace std;

int main()
{
	int n,x,sum;
	cin>>n>>x;
	sum=0;

	for(int i=0;i<n;i++){
		int tmp;
		cin>>tmp;
		sum+=tmp;
	}

	sum=abs(sum);
	int res=0;

	while(sum>0){
		sum-=x;
		res++;
	}

	cout<<res<<endl;

	return 0;
}

C - Team

http://codeforces.com/contest/401/problem/C

概要

n個の0とm個の1を用いて，0は2つ以上並ばず，1は3つ以上並ばない数列を作れるか．
作れるならばそれを，作れないならば-1を出力せよ．

解法

数列中に現れる"0"の数，"1"の数，"11"の数について連立方程式を立て，全てが正の解が得られれば，"0"，"1"，"11"を適切に並べたものが解となる．
解のパターンとしては，

  • "0"で始まり"0"で終わる
  • "0"で始まり"1"か"11"で終わる("1"か"11"で始まり"0"で終わる)
  • "1"か"11"で始まり"1"か"11"で終わる．

が考えられるので，全てのパターンでダメならば-1を出力する．
提出したコードだと落ちるケースがあるような気がするけど通った．

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <functional>
#include <set>

using namespace std;

int main()
{
	long long zero,one;
	cin>>zero>>one;

	long long a,b;
	if(one-zero>=0 && 2*zero-one>=0){
		a=2*zero-one; b=one-zero;

//		cout<<"case1"<<endl;

		for(long long i=0;i<a;i++) cout<<0<<1;
		for(long long i=0;i<b;i++) cout<<0<<11;
		cout<<endl;
	}
	else if(one-zero+1>=0 && 2*zero-one-2>=0){
		a=2*zero-one-2; b=one-zero+1;

//		cout<<"case2"<<endl;

		for(long long i=0;i<a;i++) cout<<0<<1;
		for(long long i=0;i<b;i++) cout<<0<<11;
		cout<<0<<endl;
	}
	else if(one-zero-1>=0 && 2*zero-one+2>=0){
		a=2*zero-one+2; b=one-zero-1;

//		cout<<"case3"<<endl;

/*
提出時(AC)
		if(a>zero){
			for(long long i=0;i<a-1;i++) cout<<1<<0;
			for(long long i=0;i<b;i++) cout<<11<<0;
			cout<<1<<endl;
		}else{
			for(long long i=0;i<a;i++) cout<<1<<0;
			for(long long i=0;i<b-1;i++) cout<<11<<0;
			cout<<11<<endl;
		}
*/

		for(long long i=0;i<a-1;i++) cout<<1<<0;
		for(long long i=0;i<b-1;i++) cout<<11<<0;

		if(a==0) cout<<11<<endl;
		else if(b==0) cout<<1<<endl;
		else cout<<1101<<endl;

	}
	else{
		cout<<-1<<endl;
	}
	return 0;
}

結果

oxo-- = 1404pts, 1102nd/2691,
Rating:1341->1382(+41)

TopCoder SRM 611 Division 2

250

http://community.topcoder.com/stat?c=problem_statement&pm=13038&rd=15844

"123"のような数を挟んでいないような入力でも"Interesting"を返すようなコードを書いてて落ちた

//終了後通したコード
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <functional>
#include <set>

using namespace std;

class InterestingNumber
{
public:
	string isInteresting(string x){

		for(int i=0;i<10;i++){
			int count=0;
			for(int j=0;j<x.size();j++) if(i+'0'==x[j]) count++;
			if(count!=0 && count!=2) return "Not interesting";
		}

		for(int i=0;i<x.size();i++){
			char s=x[i];
			for(int j=i+1;j<x.size();j++){
				if(s==x[j]){
					if(j-i-1!=s-'0') return "Not interesting";
				}
			}
		}
		
		return "Interesting";

	}
};

500

http://community.topcoder.com/stat?c=problem_statement&pm=13040&rd=15844

テストケースのgcdとlcm眺めて適当に書いたら通った

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <functional>
#include <set>

using namespace std;

long gcd(long a, long b){
	if(a%b==0) return b;
	else return gcd(b,a%b);
}

long lcm(long a, long b){
	return a*b/gcd(a,b);
}

class LCMSetEasy
{
public:
	string include(vector <int> S, int x){

		vector<long> v;
		v.push_back(1);
		v.push_back(1);

		for(int i=0;i<S.size();i++){
			if(S[i]==gcd(S[i],x)) v.push_back(S[i]);
		}

		long l=lcm(v[0],v[1]);
		for(int i=2;i<v.size();i++) l=lcm(l,v[i]);

		if(l==x) return "Possible";
		else return "Impossible";

	}
};

1000

http://community.topcoder.com/stat?c=problem_statement&pm=12931&rd=15843
解いてない

チャレンジ

return 1;しかやってないのを1つ撃墜

結果

xo- +1/-0 317.14pts 157th
Rating: 659->759

SECCON 2013 CTFオンライン予選に参加しました

SECCON 2013 CTFオンライン予選にチーム6p7p7#3|=L|7L|I23でぼっち参加しました．結果，フォレンジックス100，プログラミング・crypt200，その他100が解けて計400点で115位でした．

tkbctf2,年越しCTF x86-64.jp大会 2014に続いて3回目のCTF参加でしたが，楽しかったです．やっとWrite-upが書けそうな結果だったので書いてみます．

 

その他100 練習問題

答えは、「SECCON」です。

 SECCONと入力して終わり．

 

フォレンジックス100 ここはどこ？

Forensicist.datが渡されるのでバイナリエディタで開くとメールっぽい(断定)．適当に読むとtif形式でbase64でエンコードされたの添付ファイルがあるらしい．それっぽいところをコピペしてデコードするとパンダの画像が出てきた．この画像のExif情報のGPS情報をGoogleMapに投げれば良かったんですが，Exifに対応してるのはJPEGだけだと思い込んでいて，tiffの規格読み始めたりして時間がかかりました．

 flagは台北市立木柵動物園でした．他の方のWrite-upを見るとTaipei Zooでも良かったらしいです．

 

プログラミング・crypt200 数「毒」ちゃれんじ★

問題文を保存するのを忘れましたが，問題サーバーに接続すると送られてくる1マスがXで可変となった数独の盤面と複数のXの値が送られてくるので，解の個数をそれぞれ入力するのを6盤面について，それぞれ3分以内に入力するとflagが送られてくるという問題でした．

[数独 解析]等でググると

数独解析 

http://www5e.biglobe.ne.jp/~jyokun/sudoku_analyser/

 というページが見つかったので，これを使って解の個数を入力していきました．最終的に

Congratulations! Flag is 'iitai-koto mo ienai konna yononaka-ja!'

 

と表示され，これがflagでした．使用させて頂いたページでは解が多いと全部表示できないので，この解法だと運ゲーだったようです．

 

フォレンジックス400 QRコードの断片を読み取れ(途中で断念)

左半分が焼けたQRコードが写った画像が与えられるので復元する問題でしたが，

f:id:Lay_ec:20140126230529j:plain

ここまで復元して断念しました．