0x19f (Shinya Kato) の日報

主にプログラミング関連の話をします

7/2 ICPC模擬国内予選2017に参加してきた

ICPC模擬国内予選に参加してきた. 結果は4完で学内2位. M1チーム, B2チームと解いた問題数は一緒だったけれど, ペナルティで勝ったみたいな感じ. どっちも予選本番では強敵なので油断はできないですね. なお, 某チームに関してはさすがですって感じ. WA出さなかったことに関してはよかったなぁと.

自分はBを解いたのだけれど, 思いの外実装で手間取って時間をかけてしまった, 反省.

C問題は結構チーム内で「え〜、それほんとにあってる〜？」みたいなやり取りがあったのだけれど, 思い切って投げてみるとAC. ちょっと慎重になりすぎたかも(？).

D問題はペアプロみたいな感じでコーディングしてる横で一緒に考察してた. ぱっと見で二分探索ってことはわかったのだけれど, 「ゲームをクリアできない」状況ってのが理解できてなくて問題の本質をつかむまでに時間がかかってしまった. あと, データセットの解答に-1が多すぎてこれも「いや〜、これほんとか〜？」って言ってたのだけれど, 投げてみたらAC. 普通に歓声をあげて喜んでた.

この時点で残り1hあったのでもう1問解きたかったなぁという感じ. Fを考察していたのだけれど, 最小費用流(？)ってことに気づいたのが残り15分ぐらいでライブラリの準備もしていない状態だったので撤退. 他チームがACしないのを祈ってた. Eの方は幾何のライブラリがあんまり準備してなかったので選ばなかったのだけれど, こっちを選んでもよかったなぁという気持ち. 本番も4完した後にだれてしまう可能性あるので気を引き締めていきたいところ.

いろいろトラブルあって開始時間が遅れたりコンテスト時間が伸びたりしたけれど, 運営さんお疲れ様です.

本番はうちからプリンタ担いでいくぞい.

 

AOJ-ICPC(これで130問)

ARC077(起きたらコンテスト終わってたので, 後から解いた)

  • C: pushpush - AtCoder Regular Contest 077 | AtCoder [解答]
    vectorを二つ用意して, 交互にpushしていく. 全部pushしたら片方をreverseして出力.

  • D: 11 - AtCoder Regular Contest 077 | AtCoder [解答]
    重複する要素の間に挟まれない要素の数を数える. 仮にその数をsとすると, k - 1 <= sのときはcombination(N + 1, k) - combination(s, k - 1)が答え. それ以外のときは, combination(N + 1, k)が答え. というのも, 同じ組み合わせができるときっていうのは重複する要素を含む組が2つできるときだけなので. そういう組の数は, 重複する要素の左右の要素数から(k - 1)個選んで, それに重複する要素を加えた構成になっているはず.

  • E: guruguru - AtCoder Regular Contest 077 | AtCoder [解答]
    Eは自力ではわからなかったので解説を見た. お気に入りを1にしたときの回数を求めておいて, i + 1のときの回数をiのときの回数から計算すると時間制限に間に合う. (i + 1)の回数 = iの回数 + (お気に入りボタンで直接ジャンプしたときに飛ばしていた数) - (iを含む区間の数)で計算できる. 足している部分はi番目ではお気に入りボタン一発で変更ができていたクエリで, i + 1になることでボタンをぽちぽちしないといけなくなる分になっている. 引いている分はお気に入りがiのときにはお気に入りボタンとボタンをぽちぽちしていたクエリで, お気に入りがi + 1になると全て1回分ボタン操作が減る. 後者はimos法で求めてあげればOK. 輪っかみたいになった状況でのimosって初めてだったけれど, M - 1と0の間を跨ぐときは, (A[i], M - 1), (0, A[i + 1])っていう二つのクエリに分割すればよさそう. ちなみにINFの値が小さすぎて1時間WA出し続けた().

 

明日は卒検ですねぇ............ 

7/1 睡眠削る生活やめたい

睡眠削るのって次の日は寝不足で頭回らないなーってぐらいで済むけど, それを補って長めに寝た次の日が全然頭働かなくなる気がする. 起きてるのにずっとぼーっとしてるみたいな感覚. 早くこういう生活やめたいのだけどなぁ...

 

今日で自動車学校の教習は全部終了. 明後日に卒検なのだけれど, 落とされそうで怖いっすね... まぁ, 免許取るには一度地元に帰らないといけないので夏休みになるんですが. 確か豊川の免許センターに行かないといけなかったはず(？). あんまりよくわかってない.

6/30 ハードウェア記述言語しんどい

 昨日は夜寝落ちして, 日付が変わってからVHDL実験のレポートを書き始めた. TeXでカルノー図を書く方法についての知見を得た. めっちゃそれっぽい図がかけるのでおすすめ. あんまり使う頻度高くないだろうけど.

masawada.hatenablog.jp

まぁ, そんな感じでレポート書いてたんだけれど, 明け方ぐらいにネットリストがなんかおかしいことに気づく. ん？入力1ビットしかなくね？ どうやら印刷するときにミスったみたい. 仕方ないので, 午前中に実験室に行ってネットリストを印刷. 試問はいろいろ質問されたけどそんなに困ることはなかった. ただ, 「構造記述もできればやってきてね〜, そっちの方が採点が楽だから.」とTAさんに言われてしまう. TAも上からの不思議な力で強いられてるんだなぁ〜と. あと, ステートマシンのハザードは状態の振り方を工夫すると無くせるらしい(？)

 

AOJ-ICPC(最近課題に追われてやれてなかった)

 

夜中からずっと起きてるんでしんどいっす.

6/28 言語処理系のレポート倒した

言語処理系のレポート終わった〜. かなり手強かったですねぇ. とりあえず, 必須の課題に加えて配列と除算/剰余を実装しておいた. 本当は最適化も少ししたかったけれど疲れたので諦めた. 結構ちゃんとしたプログラムも書けるコンパイラになっていたので, 配列使った例としてエラトステネスのふるいでの素数列挙と剰余の例としてユークリッドの互除法での最大公約数を求めるプログラムを実行したりしてた.

 

そういえば, 昨日は特筆することないって書いたけれど, SoC設計技術AでSSDの話聞いてきたのがおもしろかったのを思い出した. 特性上書き込んだ領域は一度消さないと書き込みができないらしく, 上書きの時は空いている領域に新しく書き込んでアドレス変換テーブルにそのアドレスを記録しているとのこと. 領域が足りなくなったらガーベージコレクションをして, 消したい領域にまだ有効なデータがあったら空いているところに移動させるらしい. あとよく言われる書き込み回数の上限は1000回程度なのだけれど, こんな感じで特定のアドレスにアクセスが集中するのを分散しているから, かなりハードな書き込み量で5年ほど使っても平均書き込み回数は200回程度にしかならないらしい. なるほど.

 

全然関係ないけどニコニコでゼロの使い魔が無料で配信されてるので見てる. 初めて見たけど2期のOPで「これ聞いたことある〜」ってなったよね. 残念ながら1期の無料期間は今日で終わりなのだけど, 2期は7/3までらしいので.

ch.nicovideo.jp

 

来週が教習所の卒検なのだけれど, それ以前に効果測定に合格できる気がしねぇ......

6/27 特筆することなし

なんか授業を受けていたら1日が終わった. 本当に特筆することがない. 強いて言うなら言語処理系の課題に苦戦していることぐらい. 配列を実現しようとしたら鬼実装量が多くて厳しかった. もう少し楽にならないもんですかねぇ...

6/26 レポート用のTeXのテンプレートを整理した

レポート用のTeXテンプレートに少し手を入れた. 今回の大きな成果としてはプログラムリストを外部ファイルから読み込んで表示する方法を学んだこと. TeXでソースコードを埋め込む - Qiitaを参考にした.あと, 図表式の番号が一括で振られるようにした(2年生の子に教えてもらいました, 本当にありがとう). その他で個人的に他に欲しいなと思うのはCSVファイルを表として埋め込む機能とかですかね. できる限り整理して実験レポートの作成に苦しむであろう後輩たちに残していきたいなと. あれをWordで作るのはただの苦行でしかないので.

github.com

 

話は変わって, 『リーン･スタートアップ』という本を読んでいるという話. 内容をかいつまんで説明すると, ｢時間をかけて"完璧"な製品を作って世の中に送り出したのに全く売れなかった｣というほどの無駄はないので, 必要最小限の製品を売り出して顧客の反応を見ながら売れるものは何かということを検証しようというもの. 思い立ったらまず作り始めてしまうタイプの技術者には少し耳が痛い. まぁ, スタートアップは顧客が何を求めているのかすら分からない状況で製品を作らなければならないのだから, おっしゃる通りといった感じ. まだ途中までしか読んでいないが, 2章からは検証のサイクルを短くするための方法が述べられる模様. こういうプロジェクトにこそアジャイルの真価が発揮されるんじゃないかなと.

 

AtCoderの国内ランキングなるものを教えてもらった. 以外と国内で400番ぐらいだったりするらしい. まだまだ精進が必要ですね...

 

言語処理系の課題が思っていた100倍ぐらい大変そうでしんどい. レポートのテンプレートは整えたけれど, レポート本体はほとんど進んでないです(). いや, 配列の実現とか除算の実現とか絶対にしんどいでしょ.

6/25 TOEIC受けてきた

タイトルの通り, TOEIC受けてきた. しばらくサボっていたのでListeningはなに言ってるのか全然わからなかった. 「ここは日本だぞ, 日本語でしゃべってくれ」という気持ちになった. Readingはなんとなく前より読むの楽になった(？). 最近必要に迫られて英語のドキュメント読んだりする機会が増えたせいかな. まぁ, スコアが上がるかどうかはわからないんですが.

 

部屋の片付けをしたのだが, あんまり片付いてない. 届いたまま放置してあるプリンターとか設置するつもりだったんだけどなぁ.

 

 AOJ-ICPC

 

なお, 本日は課題の進捗ありません. 今のところの残りは, SoC, 言語処理系, ハードウェア記述言語, (ソフトウェア制作). 今週死ぬ未来が容易に想像できますね.