大学院生のぼうびろく

自分の思考の記録とアウトプットがコンセプトです.留学/研究/プログラミング/統計/機械学習

Slackのアカデミックプランに申請しました.

本年度から研究室でSlackを運用しています.
Slackのアカデミックプランに申請し,受理されたので書ける範囲で記録を残しておきます.
get.slack.help


審査項目
HPには以下の様に記載されています.

Slack は誰にでも使えますが、すべてのオーガナイゼーションが本プログラムの資格要件を満たせるわけではありません。Slack では資格要件に関するガイドラインを設けて、オーガナイゼーションの資格を独自の基準で審査しています。当社は、いかなる時にも、いかなる理由においても、オーガナイゼーションの申請または参加を承認または拒否し、当社の資格ガイドラインを追補または変更する権限を留保します。

そのため,自分のケースの場合に要求された書類が全ての団体に当てはまるとは限りません.


提出内容
1) 自分の情報が記載されている大学HPのURL
2) 大学ドメインメールを用いたメールの送信
3) 所属の研究機関から公認されたグループであることの証明書
4) 3)のグループと自分の関係が確認できる在職証明書(最近の日付が必要)

1), 2)はやるだけでしたが3)と4)はやり方が分からなかったのでダメ元で大学の支援室で事情を説明したらすぐに発行していただけました.
大学によってはこの書類の発行に時間がかかるかもしれないですね..


まとめ
○ 思ったよりも自分の場合はスムーズにいきましたが所属機関に左右されそう.
○ これだけの処理で85%オフは大きい.

diverta 2019 Programming ContestにPythonで出場しました

表記の通り企業コンに出場しました.特にdivertaが何の企業なのかは知りません.
少し調べましたが創業者が元一休.comの方っぽかったのでいつもお世話になっていますとだけ.
www.ikyu.com


A問題ーC問題まで解けてD問題は解けませんでした.
400点問題のC問題が解けたので嬉しいはずなんですけど結構みなさん解けていますね..笑
全体的にWAを生やしまくったので今後注意していきたいです.

A問題 AC
B問題 1WA
C問題 2WA

A問題
やるだけ

N, K = map(int,input().split())
print(N-K+1)

B問題
Bもやるだけ.3変数にすると間に合わないので制約を考えて2変数で対応.
Pythonでなぜか通らなかったのでPyPyで提出したらなぜか通った.


R, G, B, N = map(int,input().split())
count = 0

for i in range (N//R+1):
    for j in range (N//G+1):
        if (N - i*R - j*G)%B == 0 and (N - i*R - j*G)>=0:
            count += 1
print(count)

C問題
C問題も400点のわりには一瞬で基本方針は固まりました(最後のWA取り除くのに時間かかりましたが).
方針1: ABが含まれている個数をカウントする(以下,ABカウント).左側が'B'の個数をカウントする(以下左B).右側が'A'の個数をカウントする(以下右A).
ABカウント+min(左B,右A)を出力 →最後4つがWA

方針2: 左Bと右Aが同一文字列に含まれている場合にカウントがおかしくなる(e. g. BZZZZA, BXXXXA, BDDDDA により出力される答えは2のはずなのに方針1では3になってしまう).
上記問題を解決する.→AC

N = int(input())
count_A_right = 0
count_B_left  = 0
AB_count = 0
same_count = 0

for _ in range (N):
    S = input()
    temp = 0
    if S[0] == 'B':
        count_B_left +=1
        temp +=1
    if S[-1] == 'A':
        count_A_right +=1
        temp +=1
    if temp ==2:
        same_count+=1
        count_A_right -=1
        count_B_left  -=1
    for i in range (len(S)-1):
        if S[i:i+2] == 'AB':
            AB_count +=1

if same_count-1>=0:
    AB_count += same_count-1#一つのBAに変更して加える
    count_A_right +=1
    count_B_left  +=1
    if count_A_right==1 and count_B_left ==1:
        print(AB_count)
    else:
        print(AB_count+min(count_A_right,count_B_left))
else:
    print(AB_count+min(count_A_right,count_B_left))

追記
unratedらしいですねー.残念.

AGC033Aが解けませんでした.

AGC033Aが解けなかったのでメモ書きです.


atcoder.jp

方針
迷路問題→多点幅優先探索が思いつきませんでした.
そもそも幅優先探索を実装したことがありませんでした.
問題文の制約からしてO(HW)で解けることだけは分かりましたがそれ以外は何も分かりませんでした.
while文で行う実行回数をTとした場合のO(THW)の回答を提出してTLE.

幅優先探索に関するメモ
幅優先探索アルゴリズムの一種で迷路問題で使われる場合が多いそうです.
こちらのURLが幅優先探索深さ優先探索のイメージを掴むのにはちょうど良いかも.
qiita.com

計算量は多点にした場合も変わらないため*1O(HW)の計算量で通るそうです.
幅優先探索の練習には以下の問題が良さそうです(幅優先探索という名前ですし).
abc007.contest.atcoder.jp

実装はそこまで難しくないです.幅優先探索だとFIFOキュー,深さ優先探索だとLIFOキューを使うのが計算量を落とすためのキモだと思うんですがdequeを使うとFIFOLIFOの両方とも可能?なのでpythonではdequeを使っている人が多いという認識をしています(間違えていたらすみません).


Pypyについて
Pythonで通らない場合にPypyを使ったら通ることがある」というのは知識としては知っていましたがやったことがありませんでした.約5倍程度早くそうです.一番良いと感じた点は「学習コストが非常に低いこと」でnumpyが使えないなどの一部の例外以外はpythonのコードをそのままPypyで提出するだけで良いそうです.以下のサイトによると以下のようなケースでもPypyだと通るそうです.

N=5000N=5000でO(N2)O(N2)の解答はPythonだと無理ですがPypy3だといけます。

自分の提出コードがTLEだったので最初はdequeが原因かと思いましたが通っているサンプルもあるんですよね..
qiita.com

nadareさんのコード. deque使っていますね.
Submission #5258725 - AtCoder Grand Contest 033

ちなみに自分のTLEした結果は以下のサブミッションです.
TLEが取れないのでひとまず放置します.
Submission #5288891 - AtCoder Grand Contest 033

*1:正確には変わりそうですが多点にしても探索するパターン数に変化がないため

AGC033Aが解けませんでした.

AGC033Aが解けなかったのでメモ書きです.

atcoder.jp

方針
迷路問題→多点幅優先探索が思いつきませんでした.
そもそも幅優先探索を実装したことがありませんでした.
while文で行う実行回数をTとした場合のO(THW)の回答を提出してTLE.

幅優先探索に関するメモ
幅優先探索アルゴリズムの一種で迷路問題で使われる場合が多いそうです.
こちらのURLが幅優先探索深さ優先探索のイメージを掴むのにはちょうど良いかも.
qiita.com

計算量は多点にした場合も変わらないため*1O(HW)の計算量で通るそうです.
幅優先探索の練習には以下の問題が良さそうです(幅優先探索という名前ですし).
abc007.contest.atcoder.jp

実装はそこまで難しくないです.幅優先探索だとFIFOキュー,深さ優先探索だとLIFOキューを使うのが計算量を落とすためのキモだと思うんですがdequeを使うとFIFOLIFOの両方とも可能?なのでpythonではdequeを使っている人が多いという認識をしています(間違えていたらすみません).


Pypyについて
Pythonで通らない場合にPypyを使ったら通ることがある」というのは知識としては知っていましたがやったことがありませんでした.約5倍程度早くそうです.一番良いと感じた点は「学習コストが非常に低いこと」でnumpyが使えないなどの一部の例外以外はpythonのコードをそのままPypyで提出するだけで良いそうです.以下のサイトによると以下のようなケースでもPypyだと通るそうです.

N=5000N=5000でO(N2)O(N2)の解答はPythonだと無理ですがPypy3だといけます。

自分の提出コードがTLEだったので最初はdequeが原因かと思いましたが通っているサンプルもあるんですよね..
qiita.com

nadareさんのコード. deque使っていますね.
Submission #5258725 - AtCoder Grand Contest 033

ちなみに自分のTLEした結果は以下のサブミッションです.
TLEが取れないのでひとまず放置します.
Submission #5288891 - AtCoder Grand Contest 033

*1:正確には変わりそうですが多点にしても探索するパターン数に変化がないため

エンジョイ勢でAtCoder合宿を開催しました.

せっかくのGWなので?!AtCoder合宿*1を開催しました.

なぜやったのか

  • 蟻本をちょうど購入したので一気に勉強したかった(一人でやるのシンドイ).
  • 別で開催しているPRML勉強会のメンバーが参加可能な日程が2日あった.

目的

  • 蟻本の初級問題を一通りやる.
  • GWの思い出をつくる.

参加者
@pondelion1783 @tellmoogry @oyoroco45 +2人 の合計5人*2

スケジュール概要
初日(5/3) 10:00-21:00 動的計画法+α (7題)
2日目(5/4) 10:00-21:00 データ構造,グラフ問題+α (7題)
主に蟻本初級から問題を抜粋した(以下のQitta記事を参照した).
qiita.com
2日目の最後は疲れすぎたので問題を以下のQitta記事から選定した.
AtCoderの問題を分類しました - Qiita




まとめ&気づき

  • DP/Union-Find木/プライオリティーキューの概要を2日間で掴むことができた.
  • 一人では(まだ)できない問題を複数人で考察することができた.
  • GWにキャンプをすることができた.
  • ホワイトボードは必要.
  • AOJに登録することができた(AtCoder合宿なのに?!).

反省点

  • 参加者の層に対して問題の選定が難しすぎた (参加者のボリュームゾーンが灰色-緑)
  • キャンプで泊まったせいで2日目のパフォーマンスが明らかに落ちた

問題一覧&考察(以下メモ書きです)

初日 10:00 - 21:00

1問題目: A - おつり
atcoder.jp
貪欲で解く.
Submission #5238673 - 第7回日本情報オリンピック 予選(オンライン)

2問題目: コイン問題
judge.u-aizu.ac.jp
貪欲かな?と思うが反例があるので動的計画法で解く.
(テストケースの1 2 7 8 12 50で貪欲をすると出力が3になってしまう(1, 2, 12)を選んでしまう.)

3問題目: A-東京都
atcoder.jp
区間スケジューリング問題.左から全探索してtokyo/kyotoが出たタイミングでカウントしていけばOK.
Submission #5240179 - 京都大学プログラミングコンテスト2015


4問題目: 0-1ナップサック問題
judge.u-aizu.ac.jp
0-1ナップサック問題.はじめてのナップサック問題だったので間違えて「重複ありナップサック問題」のコードを書いていた.

5問題目: Longest Common Subsequence
judge.u-aizu.ac.jp
問題文の理解に時間がかかる.2次元DPで回答した.


6問題目: ナップサック問題
judge.u-aizu.ac.jp
4問目でこちらの実装をしていた.漸化式を注意.

7問題目: 高橋君ゲーム
arc057.contest.atcoder.jp
難しすぎる...まだACできていない.

2日目 10:00 - 21:00
 
8問題目: C-Factory
code-thanks-festival-2017-open.contest.atcoder.jp
プライオリティーキュー(優先度つきキュー)の練習問題.以下の説明がわかりやすかった.

  • データも持ち方
  • heapqの使い方
  • heapqの計算量のオーダー(O(logN))

は理解した.(実装も自分でやりたいがまだやっていない)
medium.com

Submission #5249408 - CODE THANKS FESTIVAL 2017(Parallel) | AtCoder


9問題目: 連結/ Connectivitiy
abc049.contest.atcoder.jp
Union-find木の練習問題.
問題文が理解できなかったが「また、すべての都市はそれ自身と道路で連結しているとみなします。」という文章を見逃していた.
Union-find木は以下のサイトをみて勉強した(まだ実践で使えるレベルには到底達していない.)

www.slideshare.net
at274.hatenablog.com


10問題目: C- 3 Steps
atcoder.jp
ゲロ難しかった.

必要な考察:

  • 「ちょうど3本必要な頂点間を結ぶ」を「奇数長離れている場合は橋を結ぶことができる」と言い換えることができる.
  • 二部グラフと完全グラフの場合で場合分けする
  • それぞれの判定結果に応じて結果を出力する.

分かったこと

  • 二部グラフ/完全グラフの概念および判定方法

分からなかったこと

  • そもそも場合分けにどうやって気づくのか.

以下のサイトが参考になりそう...
https://1kohei1.github.io/code-fes-2017-c

11問題目: A-高橋君と青木君の好きな数
atcoder.jp
10問目で心が折れたので簡単な問題.やるだけ.
Submission #2438477 - AtCoder Beginner Contest 032


12問目: C-Skip
atcoder.jp
X-DとX+Dの場合分けが問題をややこしくする. 実は-D+2DはDと等価なので正の場合だけ考えるので良い.あとは累積和でO(N).

13問目: D-Match Matching
atcoder.jp
DPの問題.二次元DPでdp[i][j]は「i本のマッチを使ってj番目までの数字を使った場合の整数の最大値」として漸化式をつくる.
(jは降順でソートしておく必要がある.)まだ実装できていないので時間があればやる.


14問題目: C-柱柱柱柱柱
atcoder.jp
1次元DPの問題.初期条件をdp[0]とdp[1]だけ定義してdp[i+2] = max(dp[i+1]+abs(移動コスト), dp[i]+abs(移動コスト))で解ける.
以下のQitta記事の影響か「渡すDP」のほうが自分に合っている気がする.
qiita.com

21:00 - AGC出場

*1:競技プログラミング勉強合宿 in 大阪CPSCO2019とは別です.

*2:最後2人は一部参加

ABC 125にPythonで出ました

緑になってから初めてのABC(+平成最後のABC)でした.

atcoder.jp

今回はC問題が難しかったのでD問題に取り組みました.

あとgcdは以下の点に注意しながら取り組みました(結局解けなかったけど).
結構有名な話だと思っていたんですが以外と知らない人いるみたいですね.
(一つ一つの言語のバージョンアップデートするのは大変でpythonだけが古いわけではないらしいです,,,がユーザーも多い言語なので対応してくれてもよさそう...)


A問題
問題文には「0.5秒後」などの表記がありますが無視して普通に解く.

A,B,T = map(int,input().split())
print((T//A)*B)


B問題
V[i]-C[i]>0の場合のみ選抜する天才?解法に気づかずに愚直に解く.
Bまでで8分かかっているのは時間かけすぎ.

N = int(input())
V = list(map(int,input().split()))
C = list(map(int,input().split()))
result = []
for i in range (N):
    temp = V[i]-C[i]
    result.append(temp)
    
ans = 0
for j in range (len(result)):
    if result[j]>=0:
        ans += result[j]
print(ans)


D問題
D問題は簡単でしたね(コンテスト中にD解けたの初めてor2回目).
方針1. AiとAi+1の符号反転させた場合とそうでない場合で比べてスコアが大きくなる方に変更
→ うまくいかないケースに気づいたのでやめる
方針2. マイナスが偶数個の場合は全部消せる/奇数個の場合は1つだけ以外消せることに気づく
→場合分けして実装

DPを勉強しすぎたせいで無理やりDPしようとして逆に失敗しましたね....
(DPで解けるのは解ける)


import numpy as np
N = int(input())
A = list(map(int,input().split()))

if sum((np.sign(A) ==-1)*1)%2 == 0:
    print(sum(abs(np.array(A))))
else:
    print(sum(abs(np.array(A)))-min(abs(np.array(A)))*2)

Tenka1 Programmer Beginner Contest 2019にPythonで出場しました

タイトルの通りTenka1コンテストに出場しました.
atcoder.jp

なにやら通常のコンテストとは違う企業コンテストなので色々あるらしいですが
雲の上の対決をしている人以外には無関係だと思うので普通にいつも通り解きました.

いつもと違う点としてはABCの配点が100-200-300-600だったので
ARC出た方がレート的にはお得なのでは?と考えた点です.

結局,Cが解けなかった場合のストレス値が閾値を超えそうだったのでいつも通りABC(正確にはTenka1 Programmer Beginner Contest 2019)を解きました.

結果はABCの3完 (Cで3WA)

A問題
やるだけ..といいつつ前回A問題でREを出したので今回は慎重にテストケースは全て通しました.
A, Bに大小関係の制約がなく.A<=C<=B とB<=C<=A の両方のパターンを考える必要がある点を見逃しそうでした.

A, B, C = map(int,input().split())

if (C >=A and C <=B) or (C <=A and C >=B):
    print('Yes')
else:
    print('No')

B問題
K番目の文字を抽出して場合分けでリストにK番目の文字or'*'をappend

N = int(input())
S = input()
K = int(input())

good_no = S[K-1]
ans = []
for i in range (N):
    if S[i] == good_no:
        ans.append(good_no)
    else:
        ans.append('*')
print(''.join(ans))

C問題
AもBも簡単でCも簡単そうだったのでA, B, C早解きしか考えていなかった自分としては焦りました(実際にはCで苦戦しました).
最初の方針
1. 左から探索して最初の'#'を見つける.それ以降の'.'を全てカウント.
2. 右から探索して最初の'.'を見つける.それ以降の'#'を全てカウント.
3. 1と2の最小値を出力

だと考えていましたがもう一つのケース
4. 左を全て白,右を全て黒にする方法の中で一番コストが少ないパターンを探索
が抜けていました.
4. の実装に以下のような実装を組んでTLE.

white_black = 10**6
for i in range (N):
    temp = S[:i].count('#') + S[i:].count('.')
    if temp<= white_black:
        white_black = temp


最終的にはO(N)で計算する方法を思いついたので以下のように提出したらACしました.
(相変わらず変数名が意味不明).

N = int(input())
S = input()
first_black = 0
count = 0
for i in range (N):
    if first_black == 0 and S[i]=='#':
        first_black = 1
    if first_black == 1 and S[i]== '.':
        count +=1
        
first_white = 0
white_count = 0
for i in range (N):
    if first_white == 0 and S[N-i-1]=='.':
        first_white = 1
    if first_white == 1 and S[N-i-1]== '#':
        white_count +=1

white_black = 10**6

black_count_left = 0
white_count_right = S.count('.')
ans = black_count_left + white_count_right

for i in range (N):
    if S[i] == '#':
        black_count_left+=1
    elif S[i] == '.':
        white_count_right-=1
    if ans >= black_count_left+white_count_right:
        ans = black_count_left+white_count_right
        
print(min(count,white_count, ans))

追記:
本コンテストでパフォーマンス 1402となり緑になりました.
緑色までにやったことは過去問を解いたり本番のコンテストに出ることのみです.
アルゴリズムの勉強はほとんどしていません(これが緑になるのが遅れた原因だとも思います).

解けなかったD問題を復習しなかったり
アルゴリズムの勉強しなかったりしているので今後は丁寧に解いていきたいと思います.
水色目指して頑張ろうと思います.