しがない元高専生の競プロ日記

AtCoderとかいろいろ解いてく

豊橋技科大GAC 知能情報　一般受験　面接内容

2年前に受けたやつだけどメモとして残ってたのでそのまま放流

待機場所

全体で集められてから各学科の棟に移動

外国人枠は外国人だけのグループ(待機場所は同じ)

今年は日本人枠11人外国人4人(一人づつ欠席)

テーブル2つ置いてあって6-9で囲む

留学生と喋って仲良くなる(2人筑波受ける(その1人は工芸も受ける)らしくまた会おうって言う)

後留学生TOEIC高すぎ(915と975)

日本人枠は550〜810辺りで690〜700辺りが平均だと思う

後スピーキングはできる人少なそうな印象

(TOEIC頑張って盛ってるみたいな話をしてた)

聞かれた内容

受験番号名前

豊田→家から来た？

志望理由を教えてください

院に進む予定は？

アドミッションポリシー知ってる？

(サイトを見たが覚えてませんで終わった)

口頭試験(ホワイトボードに考えてる事書いて)

確率(ここで絶望する)

問題が日本語英語で両面刷り(外国人枠も同じ問題らしい)

赤2青2から2個取り出して1:1の確率は？

→4/6=2/3(赤青マーカー使う人初めて見たって言われる)

赤3青3から2個取り出して1:1の確率は？

→9/15=3/5(9+3+3を12って書いてしまい、笑われる)

赤n青nから2個取り出して1:1の確率は？(n→∞)

→n/2n-1=1/2(最初2(n-1)と書いてしまい指摘される)

英語

Please introduce yourself.

How do you contribute to the society by using your skills?

(これはどこかのブログで書かれてた面接の内容と同じだったので準備できた)

What's your favorite algorithm?

(専門とか卒研の内容を詳しく聞いてくる)

What's your opportunity to study English?

以上で面接を終わります。

お疲れ様でした。

終わったらそのままバス待って帰宅

結果

合格

入学後に話を聞くとTOEICじゃんけんで全て決まるわけではなくあくまで出願資格の確認であり、面接内容と小論文の出来次第で結果が変わるなぁという印象を受けた。 (同校の750オーバーでも落ちてる人は落ちてた)

確か受け入れ枠の2倍の人数が合格になってたので少し安心して欲しい(それでも倍率2倍だったからやべ〜になったけど)

豊橋技科大GAC 知能情報　一般受験　面接内容

2年前に受けたやつだけどメモとして残ってたのでそのまま放流

待機場所

全体で集められてから各学科の棟に移動 外国人枠は外国人だけのグループ(待機場所は同じ) 今年は日本人枠11人外国人4人(一人づつ欠席) テーブル2つ置いてあって6-9で囲む 留学生と喋って仲良くなる(2人筑波受ける(その1人は工芸も受ける)らしくまた会おうって言う) 後留学生TOEIC高すぎ(915と975) 日本人枠は550〜810辺りで690〜700辺りが平均だと思う 後スピーキングはできる人少なそうな印象 (TOEIC頑張って盛ってるみたいな話をしてた)

聞かれた内容

受験番号名前 豊田→家から来た？ 志望理由を教えてください 院に進む予定は？ アドミッションポリシー知ってる？ (サイトを見たが覚えてませんで終わった) 口頭試験(ホワイトボードに考えてる事書いて) 確率(ここで絶望する) 問題が日本語英語で両面刷り(外国人枠も同じ問題らしい) 赤2青2から2個取り出して1:1の確率は？ →4/6=2/3(赤青マーカー使う人初めて見たって言われる) 赤3青3から2個取り出して1:1の確率は？ →9/15=3/5(9+3+3を12って書いてしまい、笑われる) 赤n青nから2個取り出して1:1の確率は？(n→∞) →n/2n-1=1/2(最初2(n-1)と書いてしまい指摘される)

英語 Please introduce yourself. How do you contribute to the society by using your skills? (これはどこかのブログで書かれてた面接の内容と同じだったので準備できた) What's your favorite algorithm?(専門とか卒研の内容を詳しく聞いてくる) What's your opportunity to study English?

以上で面接を終わります。 お疲れ様でした。

終わったらそのままバス待って帰宅

結果

合格

入学後に話を聞くとTOEICじゃんけんで全て決まるわけではなくあくまで出願資格の確認であり、面接内容と小論文の出来次第で結果が変わるなぁという印象を受けた。 (同校の750オーバーでも落ちてる人は落ちてた)

確か受け入れ枠の2倍の人数が合格になってたので少し安心して欲しい(それでも倍率2倍だったからやべ〜になったけど)

異世界転生したらつよつよとKaggleチーム組むことになってそのまま銀メダル取った話

この記事は TUT Advent Calendar 2021 4日目の記事かつ豊田高専 Advent Calendar 2021 4日目(1本目)の記事です。

ちなみに今自分は卒業研究で絶賛大炎上しています。何故こうなったんや...

で、アンタ誰

TTです。豊田高専->技科大の地元引きこもり型高専生あるある街道真っ最中です。

うまくいけば来年は正規√から外れそうですが...

競プロer(最近はゆるふわ)でありながら年間N×1e6円を音ゲー(SDVX)にかける変態です。

けんきうはSGY研で画像系のことをやってます。

ぐわ〜トラックに轢かれて気付いたら大変なことに!?!?(Kaggleコンペ参加の経緯)

~今年の春~

B4になってから研究室配属いくぜ！！！！！！！！！

・

・

・

SGY研　配属者:　TT　(1名)

🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔

ということがありつつもなんだかんだ研究開始。

なんとか画像繋がりで隣の研究室の同級生+強い人で深層学習系の勉強会をすることに。

それから夏になってコンペ出てみたいね〜でなんとなくSIGNATEに参加するも結局何もしないで放置してしまい、こりゃあかんとなった。

そんな中でTLのFFer(院試関連で知り合った強い人)が、

競プロerでML初心者で集まってKaggleやりたいんですけど誰かやりませんか

やります！！！！！！！！！！

...ということでノリと勢いで参加決定。

その後集まったメンバーを見ると、

🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔

というわけで競プロerからKagglerに異世界転生したらチームメンバーが全員ガチプロで最強にになりました。

タイトル回収ですね。

そして今見たらメンバー4/5が同級生という偶然で草。

コンペ参加開始

今回参加するのはVentilator Pressure Prediction。昨今のCovid-19の背景から患者の肺の気圧情報その他諸々から今後の患者の肺気圧情報を予測するtabular data&時系列予測系コンペ。

Kaggleのコンペとしては入力も少ないしタスクは軽めのコンペで完全に初心者でも楽しめるタイプのコンペでうってつけ。

画像は計算資源ゴリゴリゲーだしNLPは独特の知見や手法(別コンペで痛い目を見た)が必要で大変。

初心者はテーブルデータ系で出るとモデル構築もできるしオススメかも。

後で知ったがこのコンペには日本人がめっちゃ参加してたらしい。

チームメンバーとしては主催者の人がコンペ経験者、残り全員が初心者という偏った編成。

卒業研究で機械学習をやってるのは主催者と自分だけで後の人は少し知ってるという感じ。

Slackでチャンネルを立ててKaggleコンペにjoinした後チーム結成。

チーム名はflag_of_gabbonに。(国旗の色がチームのAtCoderレート色になっているため)

コンペ参加開始。主催者(めんどいので次からリーダーで)の指示でまずはCodeやDiscussionで現在のコンペの主流な解法の把握から開始。

どうやら双方向LSTMを使ったモデルがいい感じらしい。Transformerを使うのはイマイチ?PytorchよりもTensorflowの方が強いからTensorflow1択。前処理はどんなことをやってる?

こんな感じのことをまずは調べ始める。わからない人にはLSTMのQiitaの記事をぶん投げたりする。

そんなこんなしてるとリーダーが学習の動くコードを実装してGitHubにあげてくれた。天才すぎて頭が上がらん。

というわけでローカルGPUを持っている自分とリーダーが学習担当で色々いじることに。

何もわからんのでとりあえずクソデカepochでゴリゴリ回すぜ!!!!をしていたらリーダーのコードに学習を監視するスケジューラーがちゃんと組み込んであって学習が習熟したら勝手に止まるようになってた。何ですかこれは...(頭上がらん)

そんなこんなしてたら社会人erがColab proに課金して急にGPU強者に。社会人すげ〜〜〜〜〜〜

というわけでモデルをガチャガチャしたり適当にパラメータを変えて遊びながら中身を理解していった。

そして学習ない組は前処理などの学習以外の部分を担当することに。

与えられたパラメータから計算して新しい特徴量を作ってみたり、作った特徴量が学習にどれだけ効いてるかを図示してみたりで地味ながら大事な作業を担当。あとはNotebookやDiscussionを監視したりもしてた。

ちなみに実行環境はKaggle内にColabみたいなNotebookを作って実行できるKaggle Notebookがあるのでそれでやってたっぽい。

そんなこんなで...

その後、特徴量やモデルが馬鹿みたいにデカくなってローカルで学習を回すと2日間CPUの7割とGPUメモリ全てを食い尽くされて何もできんしそもそもbatch size削ってやっとみたいなことが増えてきたのでKaggle NotebookでTPU使って回す方針に変更。

これにより全員が同じ環境で学習を回せるようになり知見の交換やコードの共有、移植が簡単に。(最初からこうしても良かったかも)

ということでコンペも終盤戦に入り、残りの時間はチームメンバー全員同じ環境の並列5セット学習が可能に。

ここからやることは...そう、アンサンブルです。

機械学習における「アンサンブル」は、複数のモデル（学習器）を組み合わせることで精度の高いモデルを作成する手法を意味します。

簡単な説明がu++さんのブログにあったので興味があったらぜひ。

ということでこれまで積み上げてきた知見と特徴量を基にモデルの学習をしてみんなのモデルをアンサンブルして提出！！！！！！

f:id:honehaniwa:20211204035349p:plain

f:id:honehaniwa:20211204035410p:plain

そしてほんの少しだけ改善してコンペは終了し、運命の最終スコア発表へ。

Kaggleではコンテスト中に見れる公開順位表でのスコアデータとは全く別の非公開順位表が存在し、最終順位は非公開順位表に基づく。

つまり最後に大逆転優勝も敗北もあり得る状態...

UTC+0の24時ピッタリにコンペが終了するので日本時間だと翌日の朝9時、最終結果は...

コンペ結果

銀メダル獲得しました！！！！うおおおおおおおおおお！！！！！

ちなみにあと1つコンペで銅以上のメダルを取ると晴れてKaggle Expertになれます。

詰まるところリーチ状態。

チームメイトに...感謝...ッ!

完走した感想

チームを組むことによるモチベーションの維持と進捗の発生具合は最高でした。

特にAtCoder青以上という地頭おばけのメンバーなので何としてでも追いつくために！でこれ以上ないモチベーションで取り組むことができて本当に最高でした。

ちなみにチームメイト全員ガチで強かったです。

後は休日の自由時間を消費して競プロやっているような人間で固まった為、平日休日関わらず当たり前のようにコンペに取り組む習慣が全員に定着していたので毎日何かしらの進捗やらイベントが発生してSlackが活発に動いていた(特に深夜)ので毎日わちゃわちゃして楽しかったです。

あとはチームのタスク管理をissueとGitHub Projects紐付けでやったらめっちゃいい感じになったのでオススメです。

最後に

みんなもKaggle、やろう！！！！！！！！

豊橋技術科学大学　GACコースについて現役生が語るやつ

これは何

GACの内情についてB4(学部4年)の自分が書くやつ。

入学前の編入生(1年入学生)あたりが入る前に実情知りたいやろ?のやつです。

なお筆者は3系(情報系)なので他の系とは大きく異なる部分があるかもしれませんがGACに限ってはあんまり変わらないと思います。

TUT GACコースとは

www.sgu.tut.ac.jp

簡単に言うと留学生と共同生活を送りながら𝑮𝑳𝑶𝑩𝑨𝑳 𝑪𝑶𝑴𝑴𝑼𝑵𝑰𝑪𝑨𝑻𝑰𝑶𝑵をするやつです。

実際どうなん

究極を言えば、ほぼ日本語で生きていけます。

留学生は大体日本語をある程度勉強してからきてたり高専に留学->TUTに来てるみたいな人が大体なので日本語めっちゃ上手いです。

自主的に英語を話そうとすれば無限に機会があるしネイティブな英語を浴びまくれるけど避けようと思えば避けられます。

(月1回の学年別ミーティングとか一部は避けられなかったりもする)

まあ英語に自信なくても耐えます。

じゃあGACに入るメリットは?

圧倒的に寮です。

TUTの一般寮に比べてGAC寮は留学生に沢山入ってもらうためか力を入れまくってます。

一番古い棟でも5年以内(詳しい数字忘れたけどそんくらい)に新設され、退去してもちゃんとクリーニングされてから向かい入れられるので入るときはめっちゃきれいです。

(なお公共スペースは住人のキレイ好き具合に依存します)

後インターネット回線がクソ早いです。

f:id:honehaniwa:20210911021141p:plain
こういうこと

正直一般寮はあまりよろしくなさそう(住んだことないので分からんが)なのでG棟(GAC生が入るとこ)が必要最低限の人権だと思います。

ちなみに一般学生もG棟に入れますが定員が決められてるので確実に入れるGAC生は基本的人権が保障されてます。

デメリットは?

GACカリキュラム関連の拘束がそれなりにあります。

年1~2回は1日拘束のワークショップと月1くらいの夜2時間拘束のPeer Meeting、ユニットリーダー担当月は追加2時間拘束があります。

それらを引き換えに快適な環境が手に入るのと上部での𝑮𝑳𝑶𝑩𝑨𝑳人材になれるのでお得だと思います。

俺は英語を本気でやりたいんだ！

J-Talk | TUT 国際交流クラブ CALL 豊橋技術科学大学

こういうのがあるので参加するといいと思います。

全員英語に対する意欲が高いのでおススメです(知り合いの言ってる人みんな意識高い)。

後留学生日本人問わず友人が増えてコネクションが増えるので参加するのは強そうです。

友人はそこで留学生の年上彼女をゲットしてました。許せん。

GACで入学する後輩へ向けて

GACは人数少ないんで仲間意識が強めなのか、同じ学科の友達はできるし助け合いも頻繁に起きる。

留学生ともそれなりにつるめるので楽しみにしててくれ。

非GAC学生はTwitter使うなりで輪を積極的に広げた方が良い。失敗すると過去問が手に入らずボッチになって、実験でチームができて仲良くなるまで悲しいことになる。

グローバルハウスはとりあえずベッドと机、椅子が常設されていないので絶対買った方が良い。

後、これで電気とエアコンのリモコンを遠隔で操作すると優勝できるのでおススメ。

Amazon.co.jp: SwitchBot スイッチボット スマートホーム 学習リモコン Alexa - Google Home IFTTT イフト Siriに対応 SwitchBot Hub Mini : ホーム＆キッチン

後はWi-FiルーターがないとWiFi使えないので早めに買っとくことを強く推奨。

最悪先輩から一時的に借りて速攻Amazonで適当なものを買おう。

TUTの生活(GACあんま関係ない)

GACは英語で授業受けないといけないと思ってませんか?

残念、非GAC生も漏れなく英語のスライドで授業を受けます。カス。

詳しく書くと、不親切な先生は英語のスライド日本語で授業という誰も救われない形式で授業して、優しい先生は過去に使ってた日本語スライドや日本語版の教科書もあるものを準備したりという感じです。

後、単位は3年で取れるだけ取っておくと4年で授業で取得する単位0が達成可能です。おススメ。

まあできなくて4年でチキチキ留年ダービーをやったんですけど。

ちなみに必修落としても4年で再履修できて耐えるので頑張れ。4年で落とすと卒業に必須の実務訓練に参加できなくて留年です。

アルゴリズムとデータ構造が必修で地雷なので競プロやってる友人を見つけて全力で教えて貰いましょう。

競プロerの同士はテスト前に演習問題を軽くやるだけで問題ないので大丈夫です。

後はGPA上げておくと卒研GPAバトルに勝てたり筑波辺りに推薦で院進できたりします。

先輩っぽい3系の3年後期に国語系の中から選択で取れる授業があるんですけど、スライド発表の講義が最高に楽しいので取り得です。

これくらいかな?

最後に

まあTUTは悪い所ではないので良いキャンパスライフを。

なんか聞きたいことあったら@TT_beginnerにリプかDM飛ばしてくれれば対応します。

駄文を読んでいただきありがとうございました。

豊橋技術科学大学　大学院入試　筆記試験　合格体験記

これは何

学歴コンプをこじらせた元高専生が大学院ロンダリングに失敗して結局学内進学した敗北者の末路の体験記。

自分が欲しかった時にエントリが見つからなかったので書くことに。

筆者の経歴としては、 ｱｲｰﾁの高専(情報工学科)->TUT(GACコース, 3系)->TUT大学院(3系 予定)

TUTの編入敗北学歴コンプ後輩への安心材料になると信じて残す。

※ちなみに大体の学生は推薦(紙ペラ数枚作文無受験料アリ)で大学院に進めるので筆記で受けるのは併願をする学歴コンプerしかいないです。

TUTの院試(情報系)

科目は、

以上。

微積と代数がくっついてるのは同じ大問の中に複合した問題が出てくるから。

ガウス積分させるためにヤコビヤンで申し訳程度の代数を解かせたり、行列微分方程式を誘導付きで出したりみたいな感じ。

確率は統計の範囲までは出てこず、出ても期待値と分散を手計算させたりベイズの定理するくらいで正直他大学院を受験するなら鼻で笑ってないと話にならないレベル。安心してください。

アルゴリズムは頻出のソートアルゴリズムとオブジェクト指向プログラミングの初歩が出る感じ。

ソートアルゴリズムは全部さらっておいてオブジェクト指向系を少し復習するくらいで十分(競プロやってたら尚更)

TOEICはGAC以外の内部生が400点もないひとばっかなので400位でいいのではないでしょうか?

まあ寝不足で爆死した730のTOEICを送り付けて終わり。

やった対策

過去問2年解いただけ。

過去問は郵送か現地に行かないともらえません。ケチ。

内部生は3年以上前の過去問貰える?っぽいけど研究室の先生が印刷機のなんちゃらをちゃんとやってなくて印刷させてくれなかった。カス。

京大知能情報を併願1本にしてたのでそっちの勉強で全部カバーされてたのでTUT単体で勉強した時間は試験時間×2個分しかないです。

京大のやつを含めると、 数学はマセマ(微積代数統計)を本誌演習含め全部やりました。

アルゴリズムは、アルゴリズムイントロダクションのソートとか出そうなところの疑似プログラムを眺めて仕組みの復習をした程度。

後は卍プログラミング力卍でねじ伏せる。

後会場に編入試験徹底研究持ってきてる人いたけどあんま使えない(と思ってる)んで大人しくマセマやればいいと思います。

本番

微積代数は楕円をいい感じにする問題。急に高校範囲になって焦ったが本番中に発明してまあいい感じに。

確率はまあ。という感じ。サイコロ2個振った時の分散を手計算で求めさせるな。

アルゴはいつも通り。語句問題が記号で出たのは新しかった。

マジでガウス積分とΓ関数とかいう大学院入試頻出が京大に続いてスカされて悲しくなる。

面接

情報科棟(F棟)でやります。GACの面接と同じところ(分からんか)。

募集要項には、"既修得単位に対する口頭試問"とそれっぽいこと書いてますけど実情は卒研についてと大学院でどんな研究をやるかくらいの質問位。

覚えてる面接内容だと、

  • 志望先の研究室の確認(提出書類に書く欄があるので本当に確認だけ)

  • 現在の研究内容(院試勉強に全振りしてたのでやべ～となったが京大の提出書類でまとめてたので耐えた)

  • 大学院でやりたい研究(そんなん知らんわ。適当に答えたので微妙な答えに)

  • 大学のサークルや課外活動で頑張っていること(GAC内でそれっぽい活動やってました的なことを言った。ない人は準備しといたほうがよさそう)

  • 趣味はなんですか(は?となったが競プロで(元)水色だったりAHC最近やってますというとウケが良かった)

覚えてるのはこれくらいで、話の流れで学内の留学制度に興味がありますと言ったらただの進路指導タイムになって草だった。

逆に別の研究室の留学制度使った先輩の様子を聞けてためになった(面接とは...)

GAC生と留学と競プロという面接と関係ない所で盛り上がった面接だった。

後は待ち時間が長い可能性があるので本とか持ってくといいです。(自分は隠れてTwitterしてたけどあまりよくないので)

結果

合格でした。

筆記試験本番は既に別大学に合格した勝者が空席になってて辛くなった。

受けた人大体受かってると思われる。(去年とかのデータを見ると全員受かってたので)

ちなみに受験会場はA棟のそこそこの部屋で1~3系が一斉に受ける感じ。(4, 5系は面接だけなので別会場)

時計がないので注意

結論

もし他大学院に受験を考えている人(TUT生)がいるならば挑戦するのもいいのではないでしょうか。

よほど爆死しなければTUTは受かるので最低限の進路は確保されていると思ってチャレンジしてみてください(と言いつつ落ちたけど)。

コンプをこじらせたやつの今後の進路予定

IMLEXという海外留学制度がありまして、それで卍海外大学院卒卍の最強学歴を手に入れて優勝しようと思ってます。

TTさんの次回作にご期待ください。(また選考なので胃に穴が開かないか心配)

それも死んだら京大冬入試と仮面浪人京大再受験します。

AtCoder Heuristic Contest 001に参加しました

atcoder.jp

参加しました。

初めてRustを書いたのですがめっちゃ怒ってくれるのでありがたいですね。

マラソンに関してはC++教から改宗してRust信者になります。

後作ったコードはここに置いときます。

github.com

概要

10000 * 10000の中に点がたくさんある。

各点を丁度1個含む長方形を点の数だけいい感じに作る。

各点にはこれくらいの面積が欲しいという指標があってその指標に近ければ近いほど点が高い。

結果

46G届いたやったね！

各提出ごとのメモ垂れ流し

初回提出

方針: 愚直に長方形を置くだけ

in: 76,402,184

judge: 1,466,059,961

place: 444

2回目提出

方針: 愚直に長方形を置くだけ+psが取れるなら確実にとる

in: 初回の10倍くらい(取り忘れ)

judge: TLE

place: ---

3回目提出

方針: 初期解をpsを囲む1*1の四角に変更(初期解生成を高速化), 四角を広げる/縮めるで得点を伸ばす方針に 愚直更新なので局所解で死ぬ

in: 608,209,485

judge: RE(なんで～～～～～～～)

place: ---

4回目提出

方針: index-out-of-rangeのバグを直した:angry_face:

in: 817,702,176

judge: RE(うるせ～～～～～～～～～しらね～～～～～～～)

place: ---

5回目提出

方針: index-out-of-rangeのバグを直した, やきなましをしようとした(うまく収束せず-1量産で一旦諦め)

in: 503,326,678

judge: RE(うるせ～～～～～～～～～しらね～～～～～～～)

place: ---

6回目提出

方針: run.shでin内全部回してバグを見つける。random generator嫌いになりそう

in: 613,761,431

judge: 30,512,002,092

place: 344

7回目提出

方針: pointの更新を1点にして高速化、焼きなまし(嘘)の遷移を消して山登りに

in: 654,662,382

judge: 30,512,002,092

place: 344

8回目提出

方針: 更新時の得点計算を高速化

in: 忘れ

judge: 37,853,983,860

place: 401

9回目提出

方針: 全く触られていなかった点に対して0.1秒かけてランダムを回し続けた。ダメ。

in: 702225411

judge: 37,266,198,805

place: 472

10回目提出

方針: 焼きなましをそれっぽくした&面積をいい感じにすべく縦を揃えたら横は面積以下になるようにして よしなにする

in: 773~778くらい

judge: 42,862,187,666

place: 401(順位が変わってない...:cry:)

10回目提出

方針: 四角を伸び縮みする方針に変更

in: 847,720,305

judge: 44,936,295,721

place: 354(点数はめっちゃ伸びたのに順位が伸びない...全人類強すぎる)

10回目提出

方針: 伸び縮みする幅を-10 ~ 10に変更

in: 847,720,305

judge: 45,014,611,474

place: 391(400点台を回避できてｳﾚｼｲ...)

11回目提出

方針: 伸び縮みする幅を-25 ~ 25に変更, TLを4.75secに拡張(頑張れ)

in: 905,998,522

judge: 45,653,976,336

place: 304

13回目提出

方針: 温度関数をいじった

in: 920,053,357

judge: 45,936,069,295

place: 305(46G乗らね~~~~~)

ここらへんでジャッジのコンパイルオプションと手元実行のオプションが違うことに気付き、直す。ローカルでの点数が合う。

最終提出

(サボりまくってたら最終日!?あたしどうなっちゃうの～～～)

方針: 雑に点数が低いやつを伸ばした

in: 945くらい

judge: 46,227,785,092

place: 490(人類強すぎ)

学び

上位の人を見ると焼きなましじゃなくて山登りで貪欲にやっててビビった。

クソデカ広告をいっぱいに広げてから削る方針もあってほえ～となった。

今回の自分の立ち回りで気付くべきは四角を伸ばしたら接触"した"方の四角を削るといい感じになるということだった。

後結果だけをビジュアライズするやつしか配られないときは自分で自作するのは結構いい方針ということも学んだ(急がば回れの精神)。

完走した感想

長期間コンテストは生活習慣崩壊するので注意！(6時寝常習犯)

後めっちゃ楽しかったけどまだ下手なので手詰まり感がすごいけど頑張って成長したいね

おまけ

Vtuber杯2021全問題解説記事

VTuber杯2021とは

atcoder.jp

www.youtube.com

1/14のあーだこーだーのゲストとして競プロ系VTuberの

蟹江もなみさんときりみんちゃんさん、坂道輪さんがゲストとして呼ばれた際の企画として行われたLockout方式のコンテスト。

youtube.com

www.youtube.com

www.youtube.com

で、これは何

すべて既出の問題で推定パフォーマンスは灰~茶。

後発で受肉した&緑上位コーダーとして解かねば！ということでそれを解く配信をしたのですが...

















www.youtube.com








https://pbs.twimg.com/media/D0LACAaU8AAuE6m.jpg

















30分で解けるでしょ~とか思ってたら1時間15分弱かかってしまい、配信も気づいたら1時間半経ってました...

戒めのためにブログ形式で各問題の解説を残しておこうと思います。

なお、解答はすべてPythonの予定です。(C++はACした提出先リンクを張っておきます)

[追記]

また、YouTubeの私のチャンネルにてVTuber杯の全問題の解説動画を投稿しました。

もしよければ見て頂けると幸いです。

youtu.be

A - Crane and Turtle

atcoder.jp

鶴と亀の足の本数がそれぞれ2本、4本で動物の総数と足の総数が与えられるので正しい鶴と亀の組み合わせが存在するかを判定する問題。

鶴と亀の合計の数は決まってるのでその条件の中で足の数が合うかを全探索すればよいですね。

配信中では2重ループで鶴と亀の足を全探索しましたが1重ループでいいことに気づきました。

解答コードは以下の通りです。

Python解答コード

x, y = map(int, input().split())
# 鶴をa, 亀をbとしています
for a in range(x+1):
  b = x - a
  # 足の本数が一致しているか
  if 2*a + 4*b == y:
    print('Yes')
    exit()
print('No')

atcoder.jp

C++解答コード

atcoder.jp

B - Easy Linear Programming

atcoder.jp

$1$が書かれたカードが$A$枚、$0$が書かれたカードが $B$枚、$−1$が書かれたカードが$C$枚あり、丁度$K$枚取った時のカードの和の最大値を求める問題です。

基本的に優先順位は$A>B>C$の順番で取ってよく、更に$-1$を取るときは$a+b < k$の時(Cを絶対に取らないといけない)になります。

それ以外の場合、$B$は取っても影響はないので$Aを取る個数 - Cを取る個数$ となります。

Python解答コード

A, B, C, K = map(int, input().split())
if A+B < K:
  # Cを取る個数
  takenC = K - (A+B)
  print(A - takenC)
else:
  # A全部+Bいくらか と Aのいくらか、の条件を忘れずに!
  print(min(K, A))

atcoder.jp

C++解答コード

atcoder.jp

C - Echo

atcoder.jp

$N$文字からなる文字列$S$が与えられます。$S$を丁度半分に分割したときに同じ文字列ができますか?という問題。

Pythonのsliceが便利なのでRTA?中はPythonで通しました。

C++はs.substrがあるのでそれを使えばよいのですが、$N$が奇数の時に死ぬので条件分岐を忘れないようにしましょう(1WAした)。

Python解答コード

n = int(input())
s = input()
print('Yes' if s[:n//2] == s[n//2:] else 'No')

atcoder.jp

C++解答コード

atcoder.jp

D - Digits

atcoder.jp

$N$を$K$進数で表した時の桁数を求める問題。

$K$進数で表すとき、$i$桁以上かどうかは$i$桁全てが$K -1$で埋め尽くされているときの値以上かを考えればよくなります。

例: $N = 700$, $K = 5$のとき、

5進数で4桁以上 -> 4444の10進数表記が700以上かを判定すればよい

(4444)5 =(624)10 < 700

よって700の5進数表記は4桁以上

となる。

※(4444)5は5進数表記の4444という意味です。10進数に直すと624になります。

これを1桁づつ増やして検証していけばOK。

ちなみに$i$桁全てが$K -1$で埋め尽くされているときの10進数の数字は$K^{i} -1$になります。

Python解答コード

N, K = map(int, input().split())
digit = 0
while pow(K, digit) <=N:
  digit += 1
print(digit)

atcoder.jp

C++解答コード

atcoder.jp

E - Kagami Mochi

atcoder.jp

AtCoder Beginner Selectionでも紹介されている1問。

atcoder.jp

餅の半径が$N$個与えられるので鏡餅のように下から上に小さくなる、かつ同じ大きさの餅は選ばないとしたときの最大の段数を求める問題。

配信では与えられた配列の順番を崩してはいけないことに気付かずにLDS(最長減少部分文字列)のライブラリを張ろうとする一幕も。

答えはソートして小さい順に取っていくだけ。

Python解答コード

N = int(input())
A = [int(input()) for i in range(N)]
A.sort()
now = -1
ans = 0
for a in A:
  if now < a:
    now = a
    ans += 1
print(ans)

atcoder.jp

C++解答コード

atcoder.jp

F - Train Ticket

atcoder.jp

$+$, $-$を間に当てはめて答えが$7$になる計算式を求める問題。

Pythonではevalという文字列をそのまま式として評価するやつがあるのでそれで一発でできます。

$+$, $-$を当てはめるのに条件分岐を書きまくるのは賢く見えないのでbit全探索を使うと良いです。

bit全探索についてはけんちょんさんがわかりやすく解説している記事があるのでダイレクトマーケティングしておきます。

けんちょんさんいつもお世話になっております。

qiita.com

Python解答コード

  • bit使うパターン
s = input()
for i in range(8):
  t = ""
  for j in range(3):
    t += s[j] + ['+', '-'][1 & i>>j == 0]
  t += s[-1]
  if eval(t) == 7:
    print(t + '=7')
    break

atcoder.jp

  • bit使わないパターン

Pythonだと文字列のListでそのままfor文に入れる方法もアリなので紹介しておきます。

s = input()
for a in ['+','-']:
  for b in ['+','-']:
    for c in ['+','-']:
      t = s[0]+a+s[1]+b+s[2]+c+s[3]
      if eval(t) == 7:
        print(t + '=7')
        exit()

atcoder.jp

C++解答コード

atcoder.jp

G - Alchemist

atcoder.jp

$N$個の配列$v$が与えられて、任意の2つの要素の平均を求めて使った要素を消して求めた値を$v$の中身が1つになるまで繰り返す。

最後に残った値が最大になるときの値を求める問題。

これは最大値となる値は$v$の1,2番目に小さい値を合成していくことで求めることができます。

Python解答コード

N = int(input())
v = list(map(int, input().split()))
v.sort()
ans = v[0]
# vの1番目の要素から見ていく(0番目じゃないよ!)
for vv in v[1:]:
  ans = (ans + vv) / 2
print(ans)

C++解答コード

atcoder.jp

H - 1-SAT

atcoder.jp

これまでの文字列の中に$S$と$"!"+S$は含まれるかを問う問題。

Pythonならdict型(defaultdict)、C++ならmap<string, int>当で実装できます。

Hashmapだと$\theta(1)$になるとかならないとか...

Python解答コード

from collections import defaultdict
N = int(input())
d = defaultdict(int)
for i in range(N):
  s = input()
  d[s] += 1
for s, v in d.items():
  if d.get('!' + s):
    print(s)
    exit()
print('satisfiable')

atcoder.jp

C++解答コード

atcoder.jp

I - : (Colon

atcoder.jp

今回のコンテストで最難関。

短針と長針の長さ$A, B$、現在の時刻$H, M$が与えられるので時計の長針と短針の位置を求めて頂点同士を結んだ長さを求めてくださいという問題。

数学ができると解けるが自分は競技プログラマーであるが数学者ではないので無理です。死にます。数学を避けてきた人生を悔やみます。

使うのはラジアンと余弦定理。

ラジアンとは(分かる人はスキップ)

ラジアンとは、「円（扇形）の孤の長さ(L)÷円の半径(r)」によって求められる値のことを指すらしいです。(出展)

180度を$\pi$として計算します。つまり360度は$2\pi$だし、60度は$\pi/3$。

余弦定理とは(分かる人はスキップ)

余弦定理は下の三角形$a,b,c$があった時に、

https://upload.wikimedia.org/wikipedia/commons/thumb/4/49/Triangle_with_notations_2.svg/270px-Triangle_with_notations_2.svg.png

$$ c^{2} = a^{2} + b^{2} - 2ab * \cos(\gamma) $$

が成り立つことを指します。つまり、$c$を求めたかったら

$$ c = \sqrt(a^{2} + b^{2} - 2ab * \cos(\gamma)) $$

となります。ほえ～

で、どう使うの?

今回の問題で長針と短針の位置を角度で求めます。求めた後に頂点同士を結んだ長さを求めるのですが、その長さを知るためには余弦定理が必要です。

更に、余弦定理で必須となる$\cos$関数、様々なプログラミング言語で実装されていますが、引数として与えるのはラジアンである必要があります。

つまり、これらの流れを整理すると、

  1. 入力を受け取る
  2. $H, M$を基に針の位置とその間の角度のラジアンを求める。
  3. 余弦定理を用いて$c$を出す
  4. AC

の流れです。

import math
A, B, H, M = map(int,input().split())
Hrad = (H / 12 ) * 2*math.pi
Mrad = M / 60 * 2 * math.pi
print(math.sqrt(A*A + B*B - 2*A*B*math.cos(abs(Hrad-Mrad))))

というわけで...











f:id:honehaniwa:20210114052735p:plain
WA(迫真)
















は???????????????

















これはなぜか、それは、短針は長針にあわせて動くからです。

つまり10:30になったら短針は10と11の丁度間に動いている、ということです。

これらを踏まえたコードを実装するとようやくACです。

Python解答コード

import math
A, B, H, M = map(int,input().split())
Hrad = ((H + M/60) / 12 ) * 2*math.pi
Mrad = M / 60 * 2 * math.pi
print(math.sqrt(A*A + B*B - 2*A*B*math.cos(abs(Hrad-Mrad))))

atcoder.jp

C++解答コード

atcoder.jp

J - Write and Erase

atcoder.jp

一応ボス問、茶色ぱふぉ。

先ほどのH問題でもあったmapやdefaultdictを使う問題。

正直mapやdefaultdictを知っていますか?僕は知っています。をするだけなのでするっと書けます。

被りの要素があったらその要素を±したりmod 2で見ればOK。

Python解答コード

from collections import defaultdict
N = int(input())
d = defaultdict(int)
for i in range(N):
  N = int(input())
  d[N] += 1
ans = 0
for i, v in d.items():
  if v%2 == 1:
    ans += 1
print(ans)

atcoder.jp

C++解答コード

atcoder.jp

完走した完走

RTA配信自体は楽しかった(結果は酷かったけど)

この解説記事、書き終えた現在の時刻は深夜5時40分、長針10、短針4の時の頂点の間の距離は$9.414796255572739$だそうです。

とても疲れた。

結構明日のバイトを破滅させて時間をかけて丁寧に書いたのでたくさん読んでくれたらなぁと思います。

終わりに

Youtubeのチャンネル登録とTwitterのフォローよろしくお願いします！！！

www.youtube.com

twitter.com

ツカモさんにめざせ100人登録って言われちゃったので目指すしかないやんとなってます、今。