AtCoder Beginner Contest 032 C 列 （しゃくとり法）
C++始めると言ったのに最近精進できていない。D問題に解けるものが無く一つの壁に来た感じがある（典型アルゴやれ）
問題
https://beta.atcoder.jp/contests/abc032/tasks/abc032_c
部分列に含まれる全ての要素の値の積が、K 以下であるようなものの最長列を求める。
解法
しゃくとり法が手っ取り早い
コード（Python）
微調整を繰り返したので、釈然としないしゃくとり法になった。
他にもどこをインデックスとして回すかは問題に依るので、もっと柔軟に書けるようにしておく必要がある。
n,k = map(int,input().split()) sl = [] for i in range(n): sl.append(int(input())) left = 0 right = 0 kouho = 0 seki = 1 for i in range(n): if sl[i] == 0: break right = i if i == 0: seki = sl[left] else: seki = seki * sl[right] if seki <= k: kouho = max(kouho,right-left+1) continue else: while left <= right and seki > k: p = left seki = seki / sl[p] left = left + 1 if 0 in sl: kouho = n print(kouho)
AtCoder Beginner Contest 054 C One stroke pass
問題
https://beta.atcoder.jp/contests/abc054/tasks/abc054_c
無向グラフについて、一筆書きの経路が有るかを判定する。
やった方法
節点の数が少ないので、今回は深さ優先探索を行った。
コード
簡単な部分について、内包表記を少しずつ取り入れるようにしています。
n,m = map(int,input().split()) H = [[0 for _ in range(n)] for _ in range(n) ] for _ in range(m): a, b = map(int,input().split()) H[a-1][b-1] = 1 H[b-1][a-1] = 1 l = [0 for _ in range(n)] ans = 0 def dfs(node,visited): global ans if visited.count(0) == 0: ans += 1 return 0 else: visited[node] = 1 for node_,edge_ in enumerate(H[node]): if edge_ == 1 and visited[node_] != 1: visited[node_] = 1 visited[node] = 1 dfs(node_,visited) visited[node_] = 0 dfs(0,l) print(ans)
AtCoder Beginner Contest 030 C-飛行機乗り
問題
https://beta.atcoder.jp/contests/abc030/tasks/abc030_c
条件を満たしつつ飛行機をうまく乗り継いで、最善で往復した場合にどれだけ往復できるかを試す。
試していないが、毎回、今いる空港の次にいる空港で、条件を満たすもので最小の便を探した場合、TLEすると考えられる。
今回は、簡単な工夫ではあるものの、delを用いて探索要素を減らすことで解決しようとした。
最善をつくすと言う意味で貪欲法？になるのだろうか。
コード
Pythonを用いた。
次の空港に乗り継ぐ表現として、今回は二次元配列の2番目に0,1を用いた。
改善できる部分は多そう。。。
a,b = map(int,input().split()) x,y = map(int,input().split()) a_port = list(map(int,input().split())) b_port = list(map(int,input().split())) all_d = [] for i in range(len(a_port)): all_d.append([a_port[i], 1]) for j in range(len(b_port)): all_d.append([b_port[j] , 0]) all_d_s = list(sorted(all_d, key=lambda x: x[0])) counts = 0 times = a_port[0] here = 1 while times <= max(b_port): jj = 0 countsbefore = counts for j in range(len(all_d_s)): if times < all_d_s[j][0]: if all_d_s[j][1] == (here + 1) % 2 and all_d_s[j][1] == 0 and all_d_s[j][0] - times >= x : here = (here + 1) % 2 times = all_d_s[j][0] counts += 1 jj = j elif all_d_s[j][1] == (here + 1) % 2 and all_d_s[j][1] == 1 and all_d_s[j][0] - times >= y : here = (here + 1) % 2 times = all_d_s[j][0] counts += 1 jj = j else: pass else: continue if here <= jj: del all_d_s[here:jj] if counts == countsbefore: break print((counts +1 ) // 2)
改善点あればコメント頂けると大変嬉しいです。。。
AtCoder Beginner Contest 019 C
問題
https://beta.atcoder.jp/contests/abc019/tasks/abc019_3
2の倍数の種類を数え上げる。
単純に行う、つまり例えば、リストをソートして小さいものから順に二倍して探索するなどした場合、TLEしてしまう。
やった方法
2で割り続けて発生する、異なる奇数を全て数え上げれば良い。おおよそlog(max(a))で終わる見込みが持てる。
コード
n = int(input()) a = list(set(map(int,input().split()))) al = [] while True > 0: for i in range(len(a)): if a[i] % 2 == 1: al.append(a[i]) a[i] = 0 elif a[i] != 0 : a[i] = a[i] // 2 else: None b = list(set(a)) if 0 in b: b.remove(0) if b == []: break else: a = b print(len(list(set(al))))
改善点があれば教えて頂けると幸いです。
NAIST 情報科学研究科冬入試に合格しました
このブログはエンジニア周りのことについて書いていく予定です。
3/9にNAIST情報科学研究科、冬入試の合格発表があり、合格していました。
おそらく冬入試に関しての情報が不足していることと、他の人の合格体験記を参考にさせていただいたこと、後、単純にアクセス数が欲しいなどの理由から、いきさつを記していきたいと思います。
3/7に行って、3/9に合格発表という非常にタイムリーな感じです。
忘れないうちに、書いていきたいと思います。
冬入試の情報
第一回、第二回の情報はかなり記事があるかと思いますが、第三回についてはそこまで無いという認識です。
テストの内容などは他の人が書かれているとおりです。倍率について、控室を見た感じ、20人程度の方が出願していたように思われます。
プレゼンについては、私は理系出身ですが、情報科学分野以外からの出願でした。
TOEICは915で提出し、数学は２問とも解くことが出来ました。どちらも大学1年生程度の基礎があれば解けるかと思います。
プレゼンで聞かれたことについて
個人的に、どのプレゼンでもそうだと思いますが、暗誦は意味がないと思います。練習は入念に行っておく必要があります。
面接官の方が３人いらっしゃったので、そのすべての人と目を合わせるように意識しつつ、アドリブも交えながら反応を見てプレゼンを行いました。小論文については、専門外からの志願とはいえ、やりたいことを明確化するように意識しました。やりたいことを具体化する場合、現在どこまで出来ていて、何が課題であるのかを認識し、本番でもそれを伝える必要が有ります。ですので、先行文献の調査はかなり本気で行っておく必要があります。小論文を提出した後、日立でインターンがあったのでしばらく放置していましたが、３月頭からまた文献調査を再開し、前日は徹夜で臨みました。（ゲストハウスせんたんに泊まっていたので、最後まで粘ることが出来ました。）
本番は椅子が合ったのですが、椅子だとプレゼンしづらいので立ってプレゼンしたいと申し出たところ、笑顔でOKと承諾してくださいました。
聞かれたことについて書いていくと、
- 小論文の内容を説明して
→アドリブも交えつつ答えました。 - 小論文にはこう書いてあるけども、現実では、もうここまで出来ていることは知っているの？（＝文献調査の不足を指摘された）
→○○の方では現状の課題は○○だと自信を持って言えます、しかし××の課題までは調査は及んでいませんでした。今後調べていきますと解答 - なんでこのタイミングでエンジニアになりたいと考えたの？
→自分の生い立ちと経歴を交えつつ解答。 - 将来やりたいことは？
→同上 - プログラミングはどの程度出来る？
→２月にも自然言語処理のインターンに行った。他にも別の会社で自然言語処理関連のインターンをしている。ただし、オブジェクト指向を使いこなせるレベルではないので、今後磨いていきたいと解答。 - 数学、英語は、入ったらガチることになりそうだようね、正直、さっきの問題は簡単だった？
→談笑の雰囲気だったので、苦笑しつつ「ノーコメントです...」と答えたところ、全員に笑っていただいた。ここでベルがなり、あっけなく終了。
見られているのは、大学の成績とプレゼン力、どこまで調べてきているか、この人には研究を遂行する基礎力があるかだと感じました。
3/9 の１０時に合格発表があり、日本人枠（？）では３人だけ合格していました。
正直、駄目だったら休学すれば良いぐらいのスタンスで受けていたので、リラックスして受験することが出来ました。
経歴について
東京大学で物理を学んでおり、修士でも物性を研究していたのですが、研究内容に魅力を感じることが出来ずにいました。また、かなりの多くの（主にエンジニアの）方とメールで進路相談や、キャリアパスの相談に乗っていただいてアドバイスを頂きました。
かつ、夏のインターンで、伝統的な大企業に行かせて頂き、その時点で、japanese traditional big companyに対するミーハー的憧れのようなものは粉砕されました。その後、未経験からエンジニアになるべく、数々の会社に無給で良いので働かせて欲しいと頼み込み、一社受け付けていただいたベンチャーが合ったので、泊まり込みでフロント周りをやらせていただきました。
そこで出会ったエンジニアの方がかなり特殊な（？）方で、エンジニアとはなんぞやと言ったことや、キャリアについて様々なアドバイスを受けました。その会社には今でも感謝しきれないのですが、やはり自分がこれまで培ってきた数学、物理の知識を活かしつつ研究周りのことを行いたいと考え、自然言語処理周りのインターンをまた無給で良いのでと志願し、別の会社に移りました。この辺りで、一回松本先生とも面談しました。
最終的に、自分のやりたいこととミスマッチがあり、松本研とは別の研究について小論文に書きました。ただ、自然言語処理に対しての興味はありますので、研究内容についてはこれから決めていきたいと考えております。
追記(2018-04-28)
開示で198/210, 合格最低点も記載されており150らしいです。
これで寮に入れないのはおかしい。。。おかしくない？？と思いましたが、早くに「気づく」ことができ夏入試を受けること自体も能力の一つ、と受け止めています。入試に限らず、優秀な人は早くに動き出せる人だからです。
