インターンに参加してきたんだよ!
8月の最終週にいい生活という会社のインターンに参加しました。期間は5日間でLINEのチャットボットを作成するというものでした。
やったこと
1日目
指定の時間に会社に来たらインターン生ぽい人が2人すでに来ていてスーツを着ててやらかしたかと思ったがあとに来た人たちが私服だったので安心した。
この日は講義をうけて作るもの班で決めるみたいな内容だった。あとは環境構築とか。
2日目
午前は実装を始めた。
お昼前に偉い人のお話を聞いてお寿司を食べた。
static 🍣🍣 pic.twitter.com/Y8X5NEvtxj
— ちゃっく@IQ1エバンジェリスト (@chakku_000) 2017年8月29日
美味しかった。
午後も実装してたら進捗が良かったので明日くらいには終わるかなみたいな気持ちになってた。
夜はメンターの人たちと肉食べた。めっちゃおいしかった。
高い🍖 pic.twitter.com/4RTAZ3LBf4
— ちゃっく@IQ1エバンジェリスト (@chakku_000) 2017年8月29日
帰ったら劇場版艦これが届いてて嬉しかった
3日目
キーボードが合わないので持ち込んだ。
この日も実装してた。
班員とのコードの結合が大変だった。返り値のオブジェクトについて話し合いの時点で齟齬が生じてたのが原因。身体が型を求め始めた。
環境がWindowsだったのでmintty上でうまく行かなくpythonでstdin=io.TextIOWrapperとかしてたせいでログが出なくなって原因特定に時間がかかった。
4日目
実装がだいたい終わって細かいバグ潰しと追加機能を実装してた
5日目
午前は実装で午後は発表をした。その後懇親会はこれから。
感想
めっちゃ楽しかった!
1日目に講義があって安心できる。
メンターの人たちはslackで質問したらすぐ答えてもらえて心強いし定期的に進捗確認に来てくれてありがたかった!
いい生活でいい生活を送ってきた!
一番辛かったのは朝の通勤。学生時間に生きてると社会人時間は辛かった。
一応許可は貰ってるのでやばいことは書いてないはず。。。
IntelのPinでSegmentationFaultが発生した
問題
Intel Pinのサンプルを動かす際に
make all TARGET=intel64
でサンプルをビルドして
../../../pin -t obj-intel64/inscount0.so -- /bin/ls
で動作させた場合にプログラムが落ちて
A: Source/pin/injector_nonmac/auxvector.cpp: CopyAux: 291: unexpected AUX VEC type 26 NO STACK TRACE AVAILABLE Detach Service Count: 1 Pin 3.2 Copyright (c) 2003-2016, Intel Corporation. All rights reserved. @CHARM-VERSION: $Rev: 81201 $ C: Injector exited with signal 6 E: Wait for injector failed: No child processes zsh: segmentation fault (core dumped) ../../../pin -t obj-intel64/inscount0.so -- /bin/ls
と表示された.
解決法
どうやらkernelが4.10以上の場合Pinのバージョンによっては対応していないらしく
オプション -ifeelluckyを付けることで対応できるらしい
../../../pin -ifeellucky -t obj-intel64/inscount0.so -- /bin/ls
とすれば動作した
ICPC2017 国内予選
まえがき
このストーリーはrianの書いたストーリー
rian.hatenablog.jp
に出てくるIQ1の物語です.
IQ1視点のサイドストーリーという形になります
前日談
~ チーム登録 ~
icpcたいてっく予選には登録が必要である.そして僕らは待っていれば唐突にコーチが生えてきて全ての登録に必要なことをやってくれると思っていた...しかし,東工大は引き継ぎに失敗していて次のコーチが決まっていなかった...
そう、コーチがいなかったのである
去年はM2のはどろりさん,とこはるさんたちがコーチをやってくださっていた...しかし,先輩方が卒業してしまったいま,東工大M2にコーチをしてくれそうな人がいなかった...そしてこれに気がついたのが6/20だった.登録が6/29あたりまでで焦り始め,とりあえずはどろりさんに助けてーって言う.
そしたらshimomireさん,assyさんがまだ大学にいると教えて頂きtwitterで連絡が取れそうなshimomireさんにコーチをお願いして引き受けてもらう(shimomireさん突然twitterで連絡してすみませんでした.そしてコーチを引き受けて頂きありがとうございます).
~ チーム編成 ~
チーム名はIQ1。メンバーは吹雪(kuwaさん),睦月(すごぷろさん),夕立(ちゃっく)での編成になった.睦月(すごぷろさん)には去年も組んで頂いた.
— 卒論だしたよ!褒めて褒めてー (@chakku_000) 2017年7月9日
チーム内の役割は吹雪ちゃんと睦月ちゃんが問題を解いて夕立はお茶を汲むって感じ
あらすじ
(先に上に書いたりあんのブログを読むことを推奨します) IQ1視点
icpcたいてっく予選は本来,大魔王yosupotにより人間軍は虐殺されてしまうはずだったがyosupotは力を溜めるための眠りについたため,今年は穏やかな時が流れる.そう信じていた...しかし後輩に次世代魔王n_ari(rickytheta)が誕生してしまった...この次世代魔王n_ariの左右には「部分文字列にGODを持つgoodbaton」「忍者の家系ninja」が控えており,人間軍は魔王に立ち向かうことを諦めた.
そして予想される残りの枠は1つ.この枠を巡ってkurukuru-sushiと人間同士の醜い争いが始まる...
国内予選開始前
とりあえずラボで必要な物の印刷を始める.夕立はIQが1しかないので何故か国内模擬用のIDとパスワードを印刷してたことに吹雪ちゃんが気がつく.ビビる.
計算機室でログインしようとしたらログインできなくなってた.理由は不明だが前回はログインできたのに今回はできなかったので,もしかして夕立が計算機室の飲食禁止のルールを回避するために片足だけ計算機室から出して水飲んでたりしたのが理由だろうか...(違うと信じたい)
- 開始3分前 -
計算機室のPCにpython3がないことに気がつく(ワォ).
python3の使用を諦め,python2を使用することにする.
国内予選
とりあえずA問題を夕立が5分ちょいで通しBを吹雪ちゃんがとく.
Bを吹雪ちゃんが解いてる間に僕はDを読み「恐らくDP,ちがったらマッチング」みたいな適当なことを言いながらDPが得意そうな睦月ちゃんに投げる(練習で睦月ちゃんがDPに強そうな気がしてた).夕立はEを読むが全く解ける気がしない.蟻本のSATを眺めてみるがさっぱりできる気がしない.気がついたら吹雪ちゃんがB終わってた(BのFAかと思ったがもっと早い所あった).吹雪ちゃん練習のときはC++使ってたのに本番で突然pythonを使いだしてびっくりした.睦月ちゃんがCを通し終えてDを考えてる間に,吹雪ちゃんにE問題を説明する.構文解析がでたらすぐに吹雪ちゃんに投げる方針だったが構文解析の後が難しそうだった.
睦月ちゃんがD問題を通す.この時点で順位はめちゃくちゃ良くて4位とかだったと思う.
夕立はEを諦めてFを読み始め,吹雪ちゃんと睦月ちゃんにEを頑張ってもらうがEの方針が吹雪ちゃんと睦月ちゃんで衝突してた.
夕立はFをまとめてたらEが完全に沈黙してそうだったので睦月ちゃんにFを相談する.吹雪ちゃんはEをヒューリスティックに解き始める.
kurukuru_sushiと魔王軍(ninjaribaton)に抜かれてて夕立は焦り始める.
この時点で多分残り40分くらい.
睦月ちゃんが考察終了したのが多分残り10分ちょい.Eはペナルティが大きすぎて通しても意味がなさそうなので睦月ちゃんがFの実装に入る.
一度バグってダメかと思ったが残り1分弱でサンプルが合う.大急ぎで提出する.1回目の提出で「接続中」とかではじめてキレそうになるが,なんとかラスト1秒で提出成功してAC
睦月ちゃんかっこよすぎるっぽい~~~!
提出時間2:59:59
懇親会
味庵に行きました.何故か僕だけ子供用に椅子に座ってました.夕立なので...
assyさん懇親会を企画してくださってありがとうございます.
感想
学内3位....やはり魔王軍は倒せなかったっぽいけどkurukuru_sushiにも勝てなかった...でも全体20位なので望みはあるらしいっぽいよ!
夕立は役に立てなかったけど睦月ちゃんと吹雪ちゃんはすごかった~
あと、チームIQ1を応援してるってツイートを見てとってもとっても嬉しかった!
ICPC国内模擬2017
ICPC国内模擬2017にチームIQ1で参加しました
メンバーはkuwaさん,すごプロさん,僕で行動指針としては最初3完してあとは適当にって感じを予定してました
開始前
誰も蟻本を持ってきていない←???
TLE本も持ってきてない←まあしょうがないか
コンテスト
開始直後問題が開けない...
とりあえず印刷してる間に僕がAを読んで通す.その間にkuwaさん,すごぷろさんはB,Cの方針を考えてAが終わり次第B,Cを通す.kuwaさんは僕がAやってる間にD問題を読んでいたっぽい?
kuwaさんがDをやるがなかなか答えが合わない.僕はEを読むが無理.Fを読む.
その間にすごぷろさんにE,Fの相談.Eは完全にすごぷろさんに投げてFは「フローじゃないかなぁ」となり蟻本を眺めたくなるが眺められない.そう誰も蟻本を持ってきていないのである.
kuwaさんがDでバグるので,コーディング交代してすごぷろさんがEの実装を始める.
なんかちょこちょこkuwaさんと交代したりしながらしてた(?).
気がついたら提出障害を乗り越えてkuwaさんがD通してた
僕はF眺めてる間に貪欲でいける気がしてきてサンプル5が貪欲で行けそうだったので完全に間違った方向へ突っ走って「考察は終わりました」とか意味不明なこと言い始める
すごぷろさんはEがバグり残り20分くらいでコーディングを交代しながら書いてったら30分延長した.
30分延長したがFの実装でもバグってサンプルが合わないがデバッグするほどの時間は残ってなかった.
終わってrickytheta氏にFの解法聞いたら貪欲じゃなかった....なんか危険なケースを聞いたけどよくわからない...
感想
Aしか通してないので僕は実質お茶汲み係をしてました
チームIQ1なので勝手に東大のIQ94ってチームを敵視してたが結果としては全く格が違って敵視してたことが恥ずかしい.94倍のIQの差では勝てない...
すごぷろさんが幾何でつらそうにしてたので実体のあるTLE本がほしい...
ライブラリほしい...
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
- 作者: 渡部有隆,Ozy(協力),秋葉拓哉(協力)
- 出版社/メーカー: マイナビ
- 発売日: 2015/01/30
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (6件) を見る
Codeforces #418 Div2 C An impassioned circulation of affection
コンテスト中に解けなかったやつ...
概要
文字列sが与えられる.(sの長さ)
クエリがq個飛んでくる(q)
各クエリはm()と文字cが与えられる.
文字列sの文字のうちm個をcに書き換えた場合,部分文字列でcのみからなるも文字列の最長の長さを求めよ
解法
1.各文字cに対してs[0..i]に含まれるcの個数の累積和を求める.
2.累積和を用いて各文字cに対して,「長さi」のcからなる部分文字列を作るのに書き換える必要のある文字の数を求める
3.各クエリに対して「書き換える必要のある文字の数がm以下になっている最大の長さ」を(2)で求めた結果から計算する
計算量はでギリギリかな
コード
int n; string s; int q; int m; char c; int main(){ cin >> n >> s >> q; vector<vector<int>> cnt(26); for(char c='a';c<='z';c++){ int i = c-'a'; cnt[i] = vector<int>(n+10,0); for(int j=0;j<n;j++){ if(s[j]==c) cnt[i][j+1] = cnt[i][j]+1; else cnt[i][j+1] = cnt[i][j]; } } vector<vector<int>> need(26,vector<int>(n+10,0)); for(char c='a';c<='z';c++){ //26 for(int i=1;i<=n;i++){ //1500 int mn = 0; for(int j=0;j<n;j++){ int s = j; int t = s + i; if(t>n) break; // s[s..t) int num = cnt[c-'a'][t] - cnt[c-'a'][s]; mn = max(mn,num); } need[c-'a'][i] = i-mn; } } rep(loop,q){ cin >> m >> c; int ans = 0; for(int i=0;i<=n;i++){ if(need[c-'a'][i] <= m) ans = i; } cout << ans << endl; } }
ABC060D Simple Knapsack解いたんだよ
dp解
個使用して重さの総和がとなるときの価値の最大値
とする.
ここで重さを直接持つと配列に収まらないのでの代わりにを使用することで配列に収まるようにできる
注意点
内部のループは逆に回さないと同じ荷物を何度も使用できてしまうので注意
コード
ll N,W; ll w[128],v[128]; ll dp[128][512]; int main(){ cin >> N >> W; rep(i,N) cin>>w[i]>>v[i]; ll sum=0; rep(i,N){ ll ww = w[i]-w[0]; // 荷物iを複数回使わないように逆に回す for(int j=i;j>=0;j--){ // 荷物iを含まないでj個 for(int k=sum;k>=0;k--){ // 荷物iを含まない時の重さがk dp[j+1][k+ww] = max(dp[j+1][k+ww],dp[j][k]+v[i]); } } sum += ww; } ll ans=0; for(int i=0;i<=N;i++){ for(int j=0;j<=sum;j++){ if(w[0]*i+j>W) continue; ans = max(ans,dp[i][j]); } } cout << ans << endl; }
感想
想定解を最初に思いついたがdp解で通してるひとが結構いたのでやってみた
想定解のほうが思いつきやすいと思うけどナップサックだからdpのほうがイメージしやすいのかなぁ
C++のmapの最大のキーをとる
C++のstd::mapのキーで最小のキーはbegin()を使用し,最大のキーはrbegin()を使用すればよい.
間違えて最大のキーを取得する際にend()を使ってしまったのでメモ.
endは最終要素の次にアクセスしてしまうので値が不定になる(多分).
未定義動作になるらしいです
map::end - C++ Reference
実際に" It does not point to any element, and thus shall not be dereferenced."とある.
#include <iostream> #include <map> int main(){ std::map<int,int> mp = { {2,20}, {5,50}, {4,40}, }; int minv = mp.begin()->first; int maxv = mp.rbegin()->first; std::cout << minv << std::endl; // 2 std::cout << maxv << std::endl; // 5 int e = mp.end()->first; std::cout << e << std::endl; // 3 (最後の要素の次を指してるので何が入ってるか不明) }
修正
C++のmapの最大のキーをとる - ちゃっくのメモ帳 https://t.co/nEV7G0LB4H
— らりお・ザ・㉅㊛の🈗然㊌㋞㋰㋷㋓ (@lo48576) 2017年6月11日
値が不定というか、未定義動作になる
n3797 (C++14) だと 24.2.1/5 にある: "Results of most expressions are undefined for singular values; 〜"
— らりお・ザ・㉅㊛の🈗然㊌㋞㋰㋷㋓ (@lo48576) 2017年6月11日
上の赤字で示した部分修正受けました.ありがとうございます
ピーー☆━━━━━…‥‥(・_・ヽ) アリガタビーム!!