カメヲラボ

主にプログラミングとお勉強全般について書いてます

線形計画法のテスト問題(netlib)を読み込んで解いてみる

背景と概要 去年くらいからLPソルバを自分で書いてみたりしているのだけど、性能を評価するためのテストケースをどうしようかと思ってWeb検索したりAIに相談したりを何度も繰り返して結局どうしてよいかわからないという状況が続いている。どこかで公開され…

競プロ日記013: 日立北大コンの表彰式&意見交換会

表彰式&意見交換会に行ってきました Hitachi Hokudai Lab. & Hokkaido University Contest 2022(日立北大コン)のB問題の成績で(ギリギリ)お呼ばれして、参加することができました。 経緯 意見交換会で発表しませんか? オンラインで視聴できるかなーという…

ショートコーディング完結編

はじめに Fractal X 問題概要 基本的な考え方 main再帰と基本短縮 マクロの出番が来た! Big Fibonacci Number 問題概要 Cにはきつい問題 基本的なアイデア 変数について 計算方法について 周期性を利用できるか 最短コードに向けて まず計算量を落とす 消費…

競プロ日記012: AHC017の解法解説

AHC017 最終50位(暫定49位: 40.3G / 50.0G)の解法 THIRDプログラミングコンテスト2022(AHC017)の解法と,約一週間のコンテスト期間のアプローチについて解説(というか記録)しておきます.ヒューリスティック系コンテストの初心者・中級者や未来の自分の役に…

競プロ日記011: 今年のまとめ

今年からマラソンマッチを本格的に始めました。また、マラソン力強化のためにAtCoderのアルゴにも挑戦してみました。来年以降もしばらく続けてみようと思うので、将来の自分とこれから競プロをやってみようかと思う方々の参考として、これまでのまとめを記録…

Psyhoさんによるヒューリスティック・ボットコンテストのための無料Tips

ある日、マラソン王者のPsyhoさんがつぶやきました。 Let's make a silly experiment.For every like this post receives in the next 24 hours, I will post one tip for heuristic/bot programming contests.I will start posting these as a thread in ~1…

競プロ日記010: MM142に参加しました

TopCoderマラソンマッチ(MM142)に参加しました.最終結果は19位でした. 問題の概要 N×Nのグリッド上にいくつかプレゼントが配置されています.このグリッド上(一番外側)に,一定の確率でエルフが生えます.このエルフたちをN×Nターン操作して,プレゼントを…

競プロ日記009: ABC276

ABCのレーティング2022年11月6日現在 ABC参加8回目 ABC275は一度お休みして,AtCoder Beginner Contest 276に参加しました.ABCDの4問を解きました.E問題に目を通したのが残り10分ちょいでしたがマラソンマッチでよく書くタイプの問題だったので「いけるか…

競プロ日記008: MM141に参加しました!

MM141 seed 1 MM141 TopCoderマラソンマッチ(MM141)に参加しました.この日記を書いているのが10月28日で公式な結果はまだ出ていませんが,PROVISIONAL RANKは25位,最終順位は23位でした. 今回からマラソン参加時に簡単な日記を書くようにしてみたので,今…

競プロ日記007: ABC274も終わったしマラソンマッチをやるのだ!

ABCのレーティング2022年10月23日現在 ABC参加7回目 キーエンスプログラミングコンテスト2022(ABC274)に参加しました.ABCDの4問を解きました.D問題を提出したのが終了2分前くらいだったので後は何もできず….ACした時間を見返してみると [A]21:09:05 [B]21…

競プロ日記006: 今日も割とやらかす

ABCのレーティング2022年10月16日現在 ABC参加6回目 パナソニックグループプログラミングコンテスト2022(ABC273)に参加しました.ABCの3問を解いて,Dを愚直な方法で書いたあとTLEにならずにREになった1ので,なんでやろーと思っている間に時間切れでした.…

おもしろい台形の話

こんなツイートを見かけました. 不思議な台形を見つけました! pic.twitter.com/yjpzvUYpwA— ポテト一郎 (@potetoichiro) 2022年10月8日 要するに,台形の面積が上底と下底を文字列的に繋いだものと一致する場合があって面白いねっていう話です.面白そうと…

競プロ日記005: ABC272と息抜きコードゴルフ

ABC参加5回目 ABCのレーティング2022年10月10日現在 土曜日の朝から鼻水大洪水でしたが,走れば治るやろの精神でABC272に参加しました.ABCDの4問を解いて,Eを愚直な方法で書いたあと時間内に収めるための方法を考えている間に時間切れというかんじ.Eは後…

競プロ日記004: AHC014の反省

AHC014の復習(反省?) AHC014では長期コンなのに頑張り切れなかったので,ちょっとだけ復習しておくことにしました.私の場合,MMとかAHCではとりあえずA*を実装することが多いです.よくあるパターンはpriority queueを使ってA*→良さげなら深さ毎にpriori…

競プロ日記003: AHC014とABC271

AHC014 AHCのレーティング2022年10月2日現在 AHC014終わりました! AHC(長期)の締め切りって日曜日の19時が多い気がするので,今回もそうだと思ってたら前日の土曜日だったんですね.締め切り20分前に気が付いて,とりあえずちゃんと動作しそうなものを提出…

競プロ日記002: ABC270とMM140とAHC014

ABC参加3回目 この1週間は前半MM140,後半AHC014ということで大変ハードでしたが,こういうのはとにかく続けないとダメなのでトヨタ自動車プログラミングコンテスト2022(ABC270)に強行参加しました. 今回はABCと3問解いて残り時間が1時間ちょい,あと1~2問…

競プロ日記001: ABC269

ABC参加2回目 先週の初参加に続いてUNICORNプログラミングコンテスト2022(ABC269)に参加しました.MM140とAHC014が始まっていてかなりハードではありますが,やると決めたので気合で参加です. 方針 言語の選択 初参加のときは最初Pythonで書いていて途中でC…

競技プログラミングの鉄則

はじめに 『競技プログラミングの鉄則』という書籍が9月16日に発売されます.「これは!」と思ったので,少しの紹介と個人的な感想を書きます.尚,書籍の紹介に関しては特に依頼されたわけではありません.単純に一人の読者として感想ですのでご了承くださ…

競プロ日記000: ABCはじめました

ABC(AtCoder Beginner Contest)に初参加しました 以前から気になっていたもののスケージュールの都合とか体調の問題で参加を見送っていましたが,重い腰をついに上げユニークビジョンプログラミングコンテスト2022 夏(ABC268)に参加しました.理由は2つあっ…

何が何でもTopを取りたかった話(1)

はじめに POJ 1000 Status この画像は,AIZU ONLINE JUDGE(AOJ)やAtCoderが誕生する前から稼働しているオンラインジャッジシステムのPKU Judge Online(POJ)にある,一番最初の問題「A+B Problem」のStatus画面です. この問題は非常に単純なもので,2つの整…

POJ3786: 隣接するビットを数えよう(ゴルフあり)

隣接するビットを数えよう はじめに この記事は、北京大学のオンラインでプログラミングの問題を解くサービスPKU JudgeOnline(POJ)の問題をピックアップし、解法の解説と、C/C++/Python等による実装例に加えて、少し短いCでの実装を紹介します。後半は完全に…

きれいなPythonプログラミング

久しぶりに本出ます きれいなPythonプログラミング作者:Al Sweigartマイナビ出版Amazon なんとPython本です。Pythonに魂を売りました。ウソです。2月15日発売だそうです。 なんでPython本? 昨年なんとなく見て、面白かったので日本語版があると良いかなーと…

大学院生になりました

大学を卒業してから20年以上経ちますが、ようやくちゃんと勉強したいという気持ちが生まれました(遅) というわけで、事後報告になりますが2020年から再び学生になりました。学位論文が無事に完成するまで、もしかしたらものすごく時間がかかるかもしれないの…

256【解説】

本稿はCodeIQで2016年7月12日~2018年4月25日に出題された 【実力判定:Cランク】256 という問題の解答例と簡単な解説です。 本稿におけるコードは単なる解答の1例に過ぎません。「もっと良い解法があるよ!」とか、「こう書いた方がわかりやすいよ!」とか…

「2人組作って!」【解説】

本稿はCodeIQで2014年9月4日~2014年9月16日に出題された プログラミング言語★総選挙 予備選挙「2人組作って!」 という問題の解答例と簡単な解説です。 本稿におけるコードは単なる解答の1例に過ぎません。「もっと良い解法があるよ!」とか、「こう書いた…

最大の攻撃を繰り出せ!【解説】

本稿はCodeIQで出題された 第1回プロコン:【鬼】最大値をたたき出す攻撃を繰り出して鬼を倒そう という問題の解答例と簡単な解説です。 本稿におけるコードは単なる解答の1例に過ぎません。「もっと良い解法があるよ!」とか、「こう書いた方がわかりやすい…

「MENMA」を探そう【解説】

本稿はCodeIQで出題された 第1回プロコン:【猿】偏食の猿の好き嫌いを見極めよう という問題の解答例と簡単な解説です。 本稿におけるコードは単なる解答の1例に過ぎません。「もっと良い解法があるよ!」とか、「こう書いた方がわかりやすいよ!」とか、「…

少ない重りで重さを量ろう【解説】

本稿はCodeIQで出題された 第1回プロコン:【雉】くそ生意気な雉を黙らせよう という問題の解答例と簡単な解説です。 本稿におけるコードは単なる解答の1例に過ぎません。「もっと良い解法があるよ!」とか、「こう書いた方がわかりやすいよ!」とか、「他の…

接待じゃんけん【解説】

本稿はCodeIQで出題された 第1回プロコン:【犬】自信を無くした犬に自信を取り戻させよう という問題の解答例と簡単な解説です。 本稿におけるコードは単なる解答の1例に過ぎません。「もっと良い解法があるよ!」とか、「こう書いた方がわかりやすいよ!」…

CodeIQ過去問集40:欲張り団子

本稿はCodeIQで出題予定だったものの事情があって出題できなかった 【実力判定:Sランク】欲張り団子 という問題です。 Sランクとありますがだいぶヌルいです。 欲張り団子 【問題】 正方形のマス目があります。 マス目のいくつかには団子があります。 この…